Archives for: 2004

Take a look at a few images and movies of our Lego Robot, Grimace. Its a simple differential drive robot with light sensors and bumpers.

Enter the Gallery to take a look at its construction, and clips of Grimace in action as he tries to find light while avoiding obstacles

Continuing on, on my Mobile Robotics assignment, in the current lab we use simple path planning techniques to get from point A to point B.

Using a map built by exploring a world (as mentioned in the previous article) the code plans a path (not necessarily optimal) from the starting position to the goal position.

The "wavefront" path planning algorithm is simple, but quite effective. It is able to find a path through free space, avoiding obstacles and all locations not explored as yet.

Notice how the path planned "hugs" the wall. This is a consequence of the simplicity of the path planning algorithm and will cause undesired (duh!) collision with obstacles. We can however get over this problem very easily by "growing" the obstacles by the size of the robot.

In the following images, the obstacles are "grown" by a few cells (the areas marked in light pink) before planning is done. This guarantees a safe path that the robot can take.

In one of my courses, "Mobile Robotics," we're supposed to program "lego robots" that have various sensors (light, sonar etc) to do funky stuff. First however, we simulate our robots using the PlayerStage environment.

In one of my recent labs, I had to build a map of the robot's world using only its laser sensors to detect obstacles. The laser sensors typically have a span of 90 degrees, with a laser ray emitted at every degree. By measuring the time taken for the ray to hit an obstacle and return, the distance to the obstacle can be measured. Of course, the robot is constantly moving, and the laser sensors aren't perfect, so they don't always return the most accurate readings!

Take a look at the world I used. The robot's starting orientation is arbitrary (in this case it starts off at the bottom left corner at an angle to the horizontal).

The robot is programmed to move to a goal position, avoiding obstacles using the "force potential" method. A resultant vector (direction) is calculated by considering all obstacles in the robot's immediate vicinity as exerting repulsive forces, and the goal position as exerting a strong attractive force.

The software maintains an internal representation of the world using a large 2 dimensional array. Each cell represents a 10cm x 10cm grid position in the world. Cells that are occupied are coloured black, empty cells white, and cells that have not yet been explored are marked grey.

The goal is to map as much of the world as possible in the shortest time. In addition, I didn't want to complicate matters and decided against using any path planning algorithms.

The problem is challenging, and my solution isn't optimal, however it does produces reasonable results. When the robot's laser sensors detect an obstacle, the corresponding cell in the internal map representation is marked as occupied. In addition, all cells in the line segment connecting the robot to the obstacle are marked as unoccupied.

That works well, but we want the robot to explore areas that it hasn't visited yet! The world occupies just 1/9ths of the robot's internal map representation. Can we just pick a random unexplored area in the world and move toward it? Of course there might be a number of obstacles preventing that. We might be able to break down the problem into a number of sub-goals designed to avoid obstacles directly in the path of the robot's path. Or, the unexplored area might be in a boxed enclosure. When do we decide to give up on the goal?

My algorithm instead explores an area in the immediate vicinity of the robot (for example a rectangular area, centered on the robot). It picks a random position in this area that has not been visited, and checks to see if there is a straight line path to it without any obstacles in the robot's way. If so, the robot moves toward that goal exploring areas around the goal.

I omit the implementation details (force potential method, detecting obstacles in a straight line path) for brevity's sake, besides it isn't too hard anyway. This method actually turns out to be pretty effective. It explores a fair amount of the world in reasonable time, is able to navigate through narrow pathways and squeeze itself through tiny openings!

Take a look at the map of the world generated after 5 minutes of running time...

... and 20 minutes...

Anyone have better (and simple) ideas?

Michael Schumacher refused to give up hope of winning the inaugural Chinese Grand Prix after a spin in qualifying left him at the back of the grid.

Schumacher said: "You know in formula one you should never give up. If you know me, I never do."

"I'm Michael Schumacher. I don't need to test my driving ability, but it's certainly interesting to do what I have to do from where I am now."

Technology: Intel MMX/SSE/SSE2
Algorithm: Diagonal, Horizontal
Precision: Byte, Word

Copyright (C) 2003 Arpith Chacko Jacob

Download sw-simd-x86-1.0.0.2.zip

This package includes a parallel version of the Smith Waterman algorithm using Multimedia Extension Instructions on Intel platforms. See [1] for complete details. Two approaches, diagonal [2] and horizontal [3] are used.

The source is written in C and Assembly, and may be compiled using the GNU C compiler and the GNU Assembler. Implementations for MMX (on Intel Pentium with MMX, Intel Pentium II), SSE (Intel Pentium III) and SSE2 (Intel Pentium 4) are available. A processor detect routine that should run on most Intel 486 machines and above selects the best possible implementation during runtime, according to the technology available on the processor.

Byte (maximum possible score 255) and word (maximum possible score 65535) precision implementations are available. The actual maximum score for each precision will vary according to the similarity matrix. Negative scores are eliminated from the SW comparison matrix by biasing the similarity matrix, hence increasing the precision (since one bit is no longer needed for the sign bit). The bias value is the most negative value in the similarity matrix and is added to each element in the matrix. Hence the maximum score for the byte and word precisions are 255 - BIAS and 65535 - BIAS respectively.

The horizontal MMX and SSE approaches perform better than the corresponding diagonal approaches for standard gap penalties, and hence should be prefered on Pentium III machines or lower. The diagonal SSE2 approach performs better than the horizontal SSE2 approach for standard gap penalties, and hence should be used on Pentium 4 machines or higher. The horizontal approach performs far better however, for extremely large gap penalties (of the order of 40 + 2k, see [1]).

Limitations:

• Does not include a 3dnow implementation for AMD machines. However, SSE2 is supported on AMD processors.
• The MMX implementations perform poorly due to the lack of appropriate instructions in the MMX instruction set.
• The MMX and SSE implementations on Intel workstations use MMX registers which are aliased with the FPU registers of the floating point unit. Hence floating point operations and MMX/SSE instructions cannot be mixed together without saving state information. The 'emms' instruction is used for this purpose, but can incur a large time penalty for its execution.
  In this package floating point instructions are used for benchmarking in DEBUG mode, (with flag -DDEBUG in Makefile) and hence the emms instruction is included only in DEBUG mode, and not in the normal compilation mode. 'emms' is not required for the SSE2 implementations.
• Elements in the similarity matrix are limited to signed char.
• The gap open and gap extend penalties are limited to unsigned char.

To compile:

        
To execute:

Sample:

References:

[1] Arpith Chacko Jacob, "Whole Genome Comparison using Commodity
Workstations," B.E. thesis, 2003.

[2] Andrzej Wozniak, "Using video­oriented instructions to speed up sequence comparison," Computer Applications in the Biosciences, 13(2):145-150, 1997.

[3] Torbjorn Rognes and Erling Seeberg, "Six-fold speed-up of Smith-Waterman sequence database searches using parallel processing on common
microprocessors," Bioinformatics, 16(8):669-706, 2000.

"Whole Genome Comparison using Commodity Workstations," Arpith Chacko Jacob, Sugata Sanyal, 2003.

http://www.arpith.com/media/papers/jacob03pdsw.pdf

Abstract— Whole genome comparison consists of comparing or aligning two genome sequences in the hope that analogous functional or physical characteristics may be observed. Sequence comparison is done via a number of slow rigorous algorithms, or faster heuristic approaches. However, due to the large size of genomic sequences, the capacity of current software is limited. In this work, we design a parallel-distributed system for the Smith-Waterman dynamic programming sequence comparison algorithm. We use subword parallelism to speedup sequence to sequence comparison using Streaming SIMD Extensions (SSE) on Intel Pentium processors. We compare two approaches, one requiring explicit data dependency handling and the other built to automatically handle dependencies. We achieve a speedup of 10 - 30 and establish the optimum conditions for each approach. We then implement a scalable and fault-tolerant distributed version of the genome comparison process on a network of workstations based on a static work allocation algorithm. We achieve speeds upwards of 8000 MCUPS on 64 workstations, one of the fastest implementations of the Smith-Waterman algorithm.

After working on a studio shoot of the Indian Batsmen and not getting their autographs because "I'm not a cricket fan," David's latest work is on the front page of BBC News Online!

The BBC News Online Photographer of the Year competition aims to find the best photographer - decided by internet users - from a selection of photos sent in on various themes. Round one was on "Street Life" and David's entry was one of 14 featured on the BBC's site.

Continue...

The best way to contact me is via email. I usually check my account several times a day.

Personal messages may be sent to my address at . If you would like to email large attachments or forwards, please use the address .

I should be able to reply to your email within a day or two.

Thank you.

I live, breathe computers (well not really, I _try_ to have a life! ). This site is my first attempt to add a human side to my online presence. I intend to write regularly and post images of life from across the pond.

I study at Washington University in Saint Louis, doing my Masters in Computer Science. I did my undergraduate at Vellore Institute of Technology, and worked with SCM Microsystems for a year.

This site runs highly customized versions of b2evolution and coppermine gallery. The site design was "borrowed" from elements around the web; icons used on this website were made available by generous artists. The site has been tested on Internet Explorer 6.0, Opera 7.52 and Mozilla Firefox 0.9.2.

A big thank you to David Kirba for letting me use his photograph for my logo. If you need a shoot done in Chennai or want to see his amazing stock photos, get in touch with him at .

uClinux is a popular port of the Linux operating system to processors without a MMU (Memory Management Unit). Kernel versions 2.0.x, 2.4.x, and 2.6.x are supported to varying degrees on numerous architectures.

The uClinux distribution contains the following main components: the uClinux kernel, various libraries and numerous linux utilities. In this article some of the tasks that need to be done to port the uClinux kernel to a new architecture are examined. The information is specific to the 2.4.x uClinux kernel and the Samsung S3C44B0X, a 32-bit processor with an ARM7TDMI core.

The latest uClinux distribution uClinux-dist-20040408, can be downloaded from here. The ELF ARM7 toolchain for uClinux can be downloaded from here.

Three are three main levels where porting is required. In the case where the processor core is not supported, a new architecture will have to be added in uclinux/linux-2.4.x/arch/. In our case, support for the ARM7TDMI architecture is already present in uclinux/linux-2.4.x/arch/armnommu/ considerably reducing the effort required to port uClinux to the s3c44b0x processor. At the second level, support for the particular processor (machine) is to be added using processor specific knowledge such as registers etc. Finally, support for the board containing the processor and peripherals need to be added. This will include adding support for devices on the board that are not yet supported by linux, or configuring existing device drivers.

Continue...

This article describes the steps to be followed to debug applications on embedded ARM7TDMI processors using the GNU Debugger 'GDB' and gdbserver.

Embedded systems typically have memory constraints that restrict the size of executables (with debug information) and debuggers stored in ram. A stripped executable binary of much smaller size is usually placed on the target board, while the executable with debugging information remains on the host development system. Similarly since GDB is a large and sophisticated debugger, a light-weight control program gdbserver was created to be run on the target system.

gdbserver is executed along with the stripped application on the target machine. GDB is loaded on the host system along with the unstripped application, containing debug symbols. GDB communicates with gdbserver via a serial port or TCP/IP to provide a full-fledged debugging environment. In this article a GUI front-end debugger, Data Display Debugger 'DDD' is used.

Continue...

Random notes on the installation of Wonka, Kaffe, PCSC-lite, and Java Native Interface on ARM linux systems.

Continue...

Here's a quick shell script I wrote to mount windows shares from Linux. It may be called with the arguments 'mount' or 'umount' to respectively mount and unmount the windows shares.

During uClinux development, one of the most useful tools is a kermit download utility. Most bootloaders support download of binary images on to their targets via the Kermit protocol on a serial line. In windows the program Hyperterminal may be used to send the file from a host. For unix systems Columbia University released a free program, G-Kermit CU, which can be called by Minicom to perform a kermit transfer.

The following patch allows G-Kermit CU to function as a standalone program, eliminating the need of a terminal program such as Minicom.

Continue...

This article details the steps that need to be followed to add a kernel module to the uClinux build process.

Continue...

This article details the steps that need to be followed to add a user application to the uClinux build process. Upon building the uClinux distribution, the executable is created and copied to the romfs directory which is included with the final image. After the target board boots up, the binary may be executed from the rom filesystem.

Continue...

Thanks to Zippora for this one

I came across this quote from an article on Scrambles Amongst the Alps, a first hand account of Edward Whymper's life spent climbing the Alps.

Rated as one of National Geographic's adventure classics, this is one book I would like to get my hands on.

View gallery