Posted on 2008-08-15 18:00 JST by Curt Sampson
:: **comments enabled**

I was having a look through the blogs and code of some of the other competitors and found a few things of interest.

Greg Heartsfield’s entry was done in Haskell and in many ways seemed similar to ours. (Well, the code wasn’t formatted nearly as nicely. :-)) He didn’t use Parsec for the parser, and comparing the two parsers, I think ours (which did use Parsec) is a bit cleaner. But he did use the State monad for control, whereas we threaded the state through by hand. (I really should look at that State monad one day.) We both seem to be doing similar geometry stuff, though our typed, vector-based calculations seem nicer. I didn’t see him in the first final trial, though; I would have been curious to compare his results.

Le club des 5 did theirs in OCaml, and they seemed to have one of the more sophisticated algorithms around. As they explain in their README, they find a path by

establishing a delaunay triangulation with all known obstacles as given points (including martians). The triangulation is transformed into a voronoi diagram that describes the possible paths that avoid the obstacles at maximum distance. The shortest path to the home base is found using Dijkstras algorithm.

Directions are added based on Bezier interpolation, using only the first few points of the computed path. Speeds are added based on the curvature radius of the Bezier spline and current speed.

They used a PID Controller to “improve reactivity and minimize oscillation,” which was a darn sight more sophisticated than what we did, though given the minimal number of possible control states on the rover, might well be going overboard.

And I’m really not convinced that actually following the paths of the Voronoi diagram is the best way to go. Using it to find a route is fine, but going through or even near those points is invariably going to be longer than hugging the boulders and craters.

LazyBear also did his in Haskell, and although the code looks a bit of a disaster to me, it evidently works well, since he made it home five out of five times in the seventh trial, which knocked us out (though just barely).

Or maybe there’s just a little luck involved with which algorithm you happen to be using; he cratered on the first run of trial 6, while we made it home every time, and we were about 25% faster than he was.

Russell O’Connor also did his in Haskell, but took a different approach: placing potential functions around the world and using the gradients they produce to navigate. It’s apparently all very simple if you understand automatic forward differentiation and know where to find (and how to use) the Data.Number.Dif library on Hackage. (It’s in the “numbers” package.)

And it did seem to work, until about round 6, anyway. Not bad for doing it in only a day, alone, and in less than two hundred lines of code! Unfortunately, he chose a rather strange method of distributing his code, and I was unable to decode some bits near the end. But I think I saw, though not understood, the interesting bits.

A last note:

A lot of people seemed to slow down when approaching the origin. That might be one reason we tended to do well earlier on; we didn’t do this (unless we needed turn more tightly), which would get us in a few hundred milliseconds faster at the end, under the right circumstances.