ICFP Contest 2008
Preliminary
This year we explored the Mars during the ICFP Contest 2008. The aim was to write a controller for a mars rover that should find it's home base avoiding boulders, craters, and, of course, Martians. The rover has a advanced telemetry unit that can detect these obstacles within its surrounding (exact to the millimeter) and a simple drive controller that knows only five steering directions (hard left, left, straight, right, hard right) and three accelerations (accelerate, roll, brake).
Our controller should connect to a map server, which sends telemetry data to the rover and accepts steering and acceleration commands. Although the interchange format was specified, there was some information missing: No formulas for driving mechanics were given, there was no information about the limitations (map size, number of obstacles, maximum/minimum size of obstacles, maximum/minimum range of accelerations, speed, vision range, number of Martians). At first there was not even an example map; only about one hour after the contest a server with some example maps was posted.
We were the team SwtPl, consisting of five persons (plus two supporters).
Day 1: Lightning Contest
We splitted the task into several components: (1) Map representation as quad-tree, (2) network interface with callbacks for incoming messages, (3) GUI that shows our internal part. Note that we had no route planning at that moment; we wanted to leave that for later. This was a good decision, as the initial idea of a brute-force A* algorithm would probably have not worked at all.
After a few hours we could visualize the telemetry from the server. We also implemented an interface to drive the robot by hand. It turned out that the main problem was to control the driving mechanics. Path planning was not important on the sample maps, so we decided to write a simple controller that drives to the next goal and just avoids obstacle that are on the way.
At this moment I wondered if we can simulate the driving mechanics. The contest description contained a formula for speed, but nothing more. This contained two unknown variables accel and drag. However, the server tells the maximum speed of the rover which allows to compute drag from accel. The acceleration could then be determined by watching two adjacent telemetry data when accelerating. After we got the formulas I wrote a short program that computes acceleration and then predicts the speed, position, turn of our rover. This enabled us to predict our own position after a given time.
Our lightning algorithm just steers to the next goal (which can be the home base or the border of the next obstacle). It then simulates its movement and checks for obstacles on the way. If there is an obstacle before the next goal it will make its border to the next goal. The direction (left or right border) is determined by simple heuristics. When the obstacle is passed the home base is the next goal again. There is no prediction after the next obstacle and we always drive with max speed. In some cases the rover will crash into craters that are close behind the next goal, or it will fail to steer to the home base and orbit it on a circle. We also had no strategy for avoiding Martians.
Day 2: A new plan and screwing up the code.
When I came back the next morning, I wanted to write a driver that can drive around obstacles in a given order, computing maximum speeds and tracking on circles and line segments. But I had troubles getting the old code running. Someone had refactored the code a bit and introduced a lot of typos (e.g. x for y). Please, test your changes before committing next time.
After a while (38 hours after the contest started) I had the old code running again and fixed a few older bugs to improve the next destination selection. There was also now a GUI that displayed the predicted path. Here is a screen shot.
The pink circle marks the next obstacle, the pink line is the predicted path we will follow. When the pink path intersects an obstacle, this obstacle is made the new next obstacle. A simple heuristic is used to determine whether we go left or right.
The next 36 hours we spent programming the path follower, programming a module to compute costs of paths, programming a planning algorithm that selects the best path according to their costs. The problem was that we didn't get it bug free. So even in our final version the planner would suddenly choose an infeasible new plan instead of keeping the old valid plan. Finally we had the problem that the server clock went wrong and didn't accept our solution claiming that it was 31 seconds too late. Well, the lightning solution was probably better. What is really annoying is that we did not submit our fixed lightning solution (the 38hours solution).
Downloads
Here are some versions of the JohoPlanner. Unfortunately, we only submitted the lightning version, not the improved version we had later. The aftermath version was done after the contest finished. It can evade the Martians with some spectacular maneuvers.
You can run them as described in the submission section of the contest task. You can also run the GUI from the icfp08 directory with
java -cp bin/swtpl.marsrover.jar swtpl.marsrover.gui.ClientGui <server> <port>
You can even steer in the GUI using the arrow keys, but in that case the controller and you are fighting with each other :)