Inside F#

This year, for the first time, I participated in the ICFP programming contest.  This year’s contest involved commanding a rover to navigate the Martian terrain: see the contest task description.  It was tons of fun; I teamed up with Chris Smith, Luke Hoban, and Dustin Campbell for an F# team.

In the end we submitted an entry that does pretty well on a variety of maps.  Some features of our entry:

• It is a heuristics-based approach.  We have some general computations from what we learned about the world physics, but there are lots of hacks where we have arbitrary parameters like "multiply by 2.2" for no other reason than that seems to work well.   And there are tons of if-then-else cases for various edge cases (e.g. if we think we are going too fast, then turn less sharply, unless about to crash, …).
• It is completely "local" – we use the current state for each movement, and do not plan for the long term.  In general we either ‘aim home’ or else ‘aim tangent to the next closest item blocking our path’.
• We use a ‘connected components’ model to group together overlapping (or nearly-overlapping) obstacles.  That way, we can steer around an entire group of nearby objects rather than trying to precisely weave between them.  (I lifted code directly from this post, hurray!)  Our components are connected on an ‘absolute’ scale; it may have been better to group on a relative scale (the farther two distant objects are from you, the more likely it’s an advantage to treat them as a single connected component despite any absolute distance between the two distant objects), but I only just thought of that now.  I think we ‘connect’ any two craters that have only a two-rover-diameter-or-less distance between their perimeters.  This avoids slowing down for precise steering through narrow gaps, but might also cause us to drive long distances around objects we could in fact squeeze through.
• We only rarely slow down – if we are pointed away from home base, or if soon-after-the-next-tangent-we-are-currently-aiming-for we see an object coming soon right behind it.  (Our heuristics for computing ‘stopping distance’ and ‘how fast we can brake to avoid things’ are decent, but not outstanding.)
• We almost completely ignore Martians (very little logic to account for them).  This is risky, but there is no good alternative.
• We ignore many contest parameters, such the ‘max lookahead’ of our sensors.  As a result, if we are given a fast rover who cannot see very far ahead, he will drive way too fast directly ahead into the unknown.
• We are very good at turning quickly and smoothly, despite using a very ad-hoc heuristic approach that’s only loosely based on the (supposed) physics of the task specification.
• We did not create enough of our own sample maps, so I expect there are important cases we neglected.
• There are lots of features we considered implementing but did not have time.  For example, if we are trapped inside a connected component of obstacles with no line of sight out (imagine being inside the top-right of an @-shaped maze), I think we will get befuddled.  We have ‘tunnel vision’, and may potentially drift gently into a boulder that is just barely to the side of the direction we are headed.  We never consider using bouncing off boulders to our advantage.  We thought a lot about a completely different approach that would just predict and simulate the future, and then search futures for best possible outcomes with very little heuristic strategy and mostly learning-on-the-fly, but did not have time/resources to try it.
• We had lots of good, colorful debugging output.

Of course we used our in-house latest-and-greatest F# bits, which are very useful.  I haven’t written any blogs in the past month, partly because I’ve been so busy adding features and fixing bugs for our upcoming CTP release of F#.  I am looking forward to showing off all the hard work we’ve been doing on F#!