ICFPC 2008

I participated in the ICFP contest again this year. The task this year was to write a programme that guides a rover on the planet Mars towards its home base within a time-limit of 30 seconds, while avoiding boulders, craters and hostile Martians. The rover would get telemetry data from its sensors (which could see over a very limited portion of the terrain at a time) roughly every 100 milliseconds. As usual, we were given 72 hours to solve this problem. As it turned out, I encountered an unexpected problem during the contest and my final submission turned the rover into a "buggy", if you get the drift.

Just before the beginning of the contest, the primary hard disc of my PC crashed. So I spent most of the first day trying to rescue data, making space on another hard disc for a fresh installation, downloading Slackware 12.1 installation CDs' ISOs, installing it and setting up my environment. (A side-effect of this re-installation was that Firefox stopped crashing as often as it used to - perhaps the degrading hard disc had caused one or more system libraries to become corrupt.) This left me with only a couple of hours on the first day and just two days to solve the task.

Since I knew nothing about path planning, pursuit evasion, obstacle avoidance, etc., I turned to Google for help and it didn't disappoint. I came across the "potential field" method pioneered by Oussama Khatib for such tasks. The basic idea is very simple: you imagine that each obstacle exerts a repulsive force on the robot (diminishing with its distance) and that the target exerts an attractive force on the robot (constant in magnitude) - when you sum up the vectors representing these forces, you get the desired direction of movement. To simplify the task, I assumed everything to be a point even though they were circular discs in the task description- this allowed me to come up with a working implementation on the first day itself and in just a couple of hours. It could reach the home base in some cases without a mishap, though its zig-zag motion made it seem as if a drunk driver was in charge.

On the second day, I did some more research and hit upon the "Vector Field Histogram" (VFH) method by Johann Borenstein and associates. It is an evolution of the potential field method and is described in these papers:

1. The Vector Field Histogram -- Fast Obstacle-Avoidance for Mobile Robots
2. VFH+: Reliable Obstacle Avoidance for Fast Mobile Robots

I spent most of the second day trying to understand the papers and implementing the enhanced method from the second paper ("VFH+"). As I have experienced many a time before, it is one thing to read a paper and quite another to implement the described method in a working programme. As the old adage goes, "the devil is in the details". For example, there are some obvious and not-so-obvious typographical errors in these papers. There are thresholds used by the papers for which there are no helpful suggestions except to arrive at them "by experimentation". To compound these problems, I ran into issues with latencies, the physics of the rover, floating-point errors, my misunderstanding of the Math.atan( ) function in Java, etc. In the end, I still managed to get something that was better than the programme from the first day, though it had a propensity to fall into craters or hug unappreciative Martians. As always, I wish I had at least one more day to work on the problem.

I used Java as the implementation language with everything in just a single file. One of the neat things (or maybe not) was that I was able to use Java's graphics library to conveniently draw the discs representing boulders, craters and Martians, as well as a rectangle representing the borders of the map, into an off-screen buffer that served as the histogram used by the VFH+ method as input. The thing that I had overlooked about the Math.atan( ) function in Java was that it always returns a value in the range -π/2 to +π/2, so I should additionally use the sign of the abscissa to determine the "real" angle.

The task this year was a throwback to the usual ICFPC tasks (unlike those in 2007 and 2006). What I liked about the task was that it was simple enough for you to get started in just a couple of hours and yet you could spend the three days constantly tweaking your implementation and still remain dissatisfied. It was also something that a solo hacker could tackle without being put to a disadvantage by larger teams.

The simulator for the task that let you see the rover in action was not available for a few hours initially and when it was, it did not work on Windows - there were only versions for Linux x86 and Mac OS X x86/PPC. Even for those running Linux or Mac OS X, it was not smooth sailing as it depended on libgmp and an accelerated video driver. The organisers provided a customised Knoppix LiveCD that would represent the test environment for evaluating the submissions, but it did not work for many people or was too slow to develop in. Finally, there were four things to track this time during the contest - the mailing list, the IRC channel, the FAQ and the issue-tracker.

All said and done, I enjoyed taking part in this year's contest and look forward to taking part again next year.

You can read accounts from other teams and see some of the submissions from the links collected on a page from contest wiki.

Tweet