I wasn’t going to participate in the ICFP 2008 programming contest this year because I was at a workshop. However, this contest problem was flexible enough that one could create a reasonable entry in a few hours. Therefore, after the workshop, I woke up very early Monday morning (due to jet lag) and started writing a parser for the rover protocol.
Soon I was able to parse the entire protocol, and, by always sending the acceleration command, I had a rover that was off and running and bouncing into walls.
The next task was to implement turning. The most straightforward approach would be to always head towards the home base. At first I had some bugs due to not handling working with angles modulo 360° properly. I fixed this by the natural approach of using (unit) vectors for everything until the very end when I use atan2 to decide if I should turn left or right. Even that probably ought to be removed and done directly with outer and inner products.
So I submitted this program, left the hotel, and thought about how to avoid boulders and craters while waiting for my train. I remembered a very simple method of guiding objects around by using potential functions. By placing a potential function throughout the world, one can try follow the gradient decent to try to get to one’s goal. High potentials can be placed around obstacles to avoid them. This method seemed simple enough to implement on the train from Pregarten to Munich.
Automatic Differentiation makes finding the gradient a snap, if you know how to use the library.
gradient :: ((Dif a1, Dif a) -> Dif b) -> (a1, a) -> (b, b) gradient well (x,y) = (dx,dy) where dx = deriv (\x -> well (x,dCon y)) x dy = deriv (\y -> well (dCon x,y)) y
The above Haskell code finds the gradient of a potential function, well, at the point (x,y) simply by computing the partial derivatives.
In the end, I used a simple linear potential pulling the rover to the home base, and then added repelling wells from boulders and craters based on the inverse distance squared to the rim and the radius cubed of the hazard. Martians were ignored.
The gradient gave a desired velocity. Then I turned, braked, or accelerated to try to bring my current velocity closer to my desired velocity. That was all there was to my navigation.
With some more thought, I think I could come up with more reasonable potentials. At the moment the units of my potential don’t make any sense. However, if I had more time, I would have used a different method of hazard avoidance all together.
In the end, what I submitted seemed fairly reasonable. It sometimes avoids craters, especially the big ones. It sometimes even manages to make it to the homebase, all in less than 200 lines of Haskell and in less than one day.