A couple of weekends ago, Bobby and I worked on this year’s ICFP. It was a long, tiring weekend, but overall it was much more satisfying than last year. Last year, the problem was quite ingenious, but it required quite of bit of ingenuity (for example, a wizz-bang new-fangled approach to string handling would have helped a lot) to get any results at all. This year’s contest, navigating a rover around Mars, avoiding craters, boulders and Martians, was still an interesting and difficult problem, but it was at least obvious where to start. It wasn’t a “either you get it or you don’t” problem, and I liked that.

We made a lot of progress early on, and even had a submission for the lightning round (which had a deadline of 24 hours into the contest; we submitted our with 53 seconds to spare!). After that, progress became harder. Throughout the contest, our rover pretty much just tried making a beeline for home base. Later versions checked if there were obstacles in the was and tried routing around them. While we got better with time, the rover was never able to consistently avoid hitting stationary objects. Thus, we didn’t really get much into higher level problems like Martian avoidance or finding an optimal path through a maze of obstacles. For us, this year’s ICFP was more about angles than AI.

Bobby ended up doing most of the significant work on the core of the rover, with his (much) better control of trig and his (much) better work ethic. But I helped out a lot around the edges, dealing with networking code, map generation/test suites, a few utility functions, etc. I did pursue a few ideas for the core router (generally involving prediction); these were invariably broken and quickly abandoned. (I need to start doing unit tests and the like…)

Lessons learn, notes, problem, anecdotes, etc. in no particular order:

• I continually — continually — said “router” when I meant to say “rover”. It became the running joke of the weekend. Even when I got it right, I often got it wrong: “So the rover — err, I mean router… Damn.” Thus, when it came time to pick a team name when submitting for the lightening round, Bobby came up with the perfect suggestion: “The Rover Routers”.
  

• The contest organizers released various test servers and sample maps over the course of the contest. However, for a very long time, the only version of the server available was for 32 bit x86 Linux. Since Bobby had a 64 bit Linux box and I had my PPC Mac, this was a bit of a problem. We ran the server off of QEMU on my machine for quite some time, until Bobby was able to get it working natively on his system.
  

• Git rocks. Before this weekend, I hadn’t really made good use of a version control system before. This weekend I truly got comfortable using version control. It was fun, with all the pulling and pushing and branch and merging. The command line tools are very fast and user-friendly; the git bundle for TextMate is orgasmically slick.

  (This turned out to be well timed. The software that runs this blog, Byteflow, uses Mercurial, which functions very much like git. Getting comfortable with distributed version control has been an enormous help getting this blog set up — I’ve got three repositories associated with this blog, two on my machine and one on my hosting provider.)

• There were a lot of parameters in our rover where we set the values rather arbitrarily. One thought we had was to make a large test suite with randomly generated maps and then automatically “train” the rover by seeing what values worked better. There turned out to be two main problems with this.

  • First, since the trials were happening in real(ish) time, test suites were always going to take a good chunk of time to run.
  • More importantly, our results turned out to be far less deterministic than we expected and quite sensitive to the vagaries of CPU load and networking issues. When we did try comparing our rover’s performance with different parameters, there was no consistency between runs. One set of parameters might be significantly better than its competitors on one run and significantly worse on another run with the same set of maps.
    

• Bobby’s a Time Lord! (For some reason, his original post looks weird now but this one quotes it in full.) This was immensely helpful in letting us run a lot of test very quickly, but it may have also made the nondeterminism even worse. Nevertheless, I’m quite impressed with his hackertude and his mastery over Time itself.

• My trig is rusty. Heck, it’s completely rusted through.

• simplejson made handling map generation very easy. I’m quite happy it will be in the standard library in Python 2.6/3.0.

• This was the first time I used Python’s asyncore and asynchat modules. On the one hand, they were certainly more convenient than just using the low-level socket module. On the other, they’re confusing as hell! Error handling in particular is poorly documented. I spent a lot of time trying to handle “connection refused” and “broken pipe” exceptions; exception-handling in asyncore is completely unlike anything else I’ve seen in Python. I think there are probably good reasons for all the idiosyncrasies, but it was very frustrating. (Oh, and asyncore.dispatcher is an old-style class. Learned that when trying to use super with a subclass of a subclass of it. Wasn’t a big deal, but I was surprised.) I’m not going to say they’re bad modules, as I don’t really understand them and thus can’t judge them; however, in the future, I think I’ll either just use socket or try to learn Twisted.

• We never really dealt much with Martians. (Getting crater avoidance working right was far harder than anticipated, and after a point every attempt at improving it seemed to make it worse.) We did have some rudimentary ideas:

  • In the code we eventually submitted, the rover treated Martians like (stationary) craters or boulders. To account for their non-stationary nature, we just had the rover pretend they were bigger than they actually were. (The rover assumed they had a radius of 0.7 meters, I think, rather the actual value of 0.4 meters.) It’s unclear how useful this was.

  • At one point I tried to work out some sort of prediction mechanism for our rover. It was a complete disaster. The difference between where the rover thought it would be, say, 500 milliseconds in the future and where it ended up was often wrong by several kilometers — an error larger than the maps it was running on at the time. My code had gotten quite convoluted and inscrutable, and there were more promising things to work on so we abandoned that particular attempt.

  • Towards the end of the contest, I came up with what could have been a incrementally better version of the “Martians as craters” form of prediction we were using. The idea was to treat a Martian as a series of craters along its current current heading. I got a rudimentary form of this sort of working, but it didn’t seem to make much of a difference and I didn’t have much time to test it. Thus, it didn’t make it into the final rover.
    

• Performance was a major issue, as the telemetry data kept coming every 100 milliseconds (or even less, when using Bobby’s speed hack). Bobby reimplemented one of our most used functions in C (and came away singing the praises of ctypes), which dramatically reduced the rover’s CPU usage. Nevertheless, even after that, many of the rover’s problems were likely due to getting behind on processing messages. On Sunday, we talked about having the rover check to see if if it was falling behind and act differently based on that. However, by that time, we were both exhausted and irritable, and I had lost the ability to speak in complete sentences. I tried doing something involving threads that would make that information available, but to no avail.

Altogether, it was a fun, if tiring, weekend. I’m looking forward to next year.