Red Rhover: An ICFP Contest 2008 Post-mortemby Mike Pavone
Team Rhope Burn participated in the ICFP Programming Contest again this year. This time around the task was to guide a rover to its home base while avoiding craters, boulders and Martians. The task turned out to be pretty Rhope friendly. Get DString and Split made short work of retrieving and parsing the data from the simulator and nothing about the task necessarily required a lot of processing power (though it could certainly help with certain approaches) so the slowness of the current Rhope implementation wasn't really an issue.
The contest started at 3PM local time, but I didn't really get started until I got on the train to head home from work at about 5:45. I spent the train ride trying to get the simulator to run on my laptop (didn't run in my Ubuntu install and I had a bit of trouble with the LiveCD initially). After my wife picked me up from the train station, she wanted me to tag along to Babies 'R' Us so she could pick up a baby shower gift for a friend. So it was in the Babies 'R' Us parking lot that I got a lame manual control client working (prints telemetry updates to standard out and accepts manually entered commands on standard in). By the time I got home, I had a more or less working autonomous client that would ignore obstacles and just turn towards the goal. I called up my sole teammate and he agreed to work on storing object info so we could use it with a proper pathfinding algorithm for the main round and I would continue to work on the kludgey obstacle avoidance strategy so we would have a reasonable rover for the lightning round.
The next few hours were basically wasted. I was trying to get the LiveCD running on my laptop to properly drive my old 21" CRT so I could have just a short glance between the screen I was doing my development on to the one on which the simulator was running. In the end I couldn't get it to work right so all the fiddling was just wasted time I could have better spent on the task itself. My teammate had more severe problems getting a workable environment and so wasn't able to contribute anything until the following day.
After giving up on my stupid monitor issue, I pulled an all-nighter to work on the lightning round submission. By about 10 AM local time (7AM contest time), I had a rover that could avoid obstacles by turning left. I had tried to get it to choose the optimal direction, but it just ended up changing it's mind over an over resulting in it aiming right for the obstacle so I kept the simple turn left approach for the lightning round. There was code in my lightning round entry to avoid Martians by treating them as stationary objects with radius 0.4 + their current speed times some multiplier. Unfortunately, the interpreter had a bit of a bug that resulted in everything after the decimal point getting truncated when converting a string to a floating point number. Since both the base radius (0.4) and the multiplier I was using were less than 1, the Martians ended up having an effective radius of 0 so they ended up being ignored.
So I submitted what I had that morning and then went off to my friend's bachelor party. That took up pretty much the whole day and I was exhausted afterwards (no sleep + 3 hours of paintball will do that) so I didn't work on the submission any more until Sunday after church. My teammate did finally manage to get his dev environment straightened out though so he produced a bug fix so that objects that are further away than home base are ignored and a number of test maps that our current rover couldn't really handle. He really enjoyed making the maps so I suggested he whip up a little test harness that would allow us to test a bunch of maps unattended and then make some more test maps.
I decided to try and make our current rover less hackish rather than try something fancy like implementing A* pathfinding. I fixed the aforementioned floating point bug and then attempted to get the rover to successfully pick an "optimal" direction for avoiding obstacles. This took way too long as we weren't really modeling the physics of the way the rover turned. The collision avoidance code would just increment away from the goal angle (the angle to home base) until it found one that was clear without taking into consideration whether the rover was physically capable of turning to that path before it collided with the obstacle. This tended to cause the rover to either pick an unrealistic direction or to oscillate between two directions when trying to avoid an obstacle.
I eventually managed to come up with a really hackish solution that worked pretty well for the test maps. The code would search for the first angle on either side that passed all visible obstacles starting from the goal angle. The rover would then choose the one that was closest to its "adjusted" current angle rather than the one closest to the goal angle. The "adjusted" angle was the angle reported by the telemetry data modified based on the current turning state and the turn speed parameters with a bit of fudge to try and account for rotational acceleration. This worked okay, but I suspect it will fall apart on a map that had different rover parameters (didn't have time to test for this unfortunately).
After that, I worked on improving our Martian avoidance behavior. Up to that point, we treated Martians as a stationary object with a radius of 0.4 (their actual radius) plus somewhere between 1 to 3 turns of movement (I experimented with different values at different times). This worked for the dumb Martians in the sample simulator, but it equally favored a path in front of a Martian as one behind it which seemed like it could be a problem in later heats. It also resulted in avoiding a Martian by a much greater distance than necessary when passing behind it. The new Martian avoidance code checked for intersection with a line segment extending 3 turns from the front tip of the Martian (assuming that it goes straight at its current speed) and then used the standard obstacle collision detection with radius 0.4 if that check passed. Not sure if it was really worth the effort. It helped our time on 1 run on spiral. Who knows how it will pan out with the actual contest maps.
I think the last change I made before submitting was to make some modifications to my fudge factor for the collision check to try and take into account the rover's current speed and distance to the object. Not too sure how this one will pan out in the actual contest either. I think I may have ended up making the rover a bit to aggressive in taking a close path to obstacles. Time will tell.
Overall I'm pretty happy with how the contest went for us this year. I think we submitted a very solid lightning round entry and our main round entry was at least good enough not to be embarrassing. Rhope has matured a lot since last year and wasn't really a major obstacle to our success like last year. I do wish I had taken a step back every once an a while and evaluated my approach (Monday morning it became clear to me that I should have abandoned the kludgey angle based collision detection and done some simulation based on turn commands instead, but it was too late at that point). I'd also like to try and have a slightly bigger team next year and try to get everyone in the same place. I was pretty productive this weekend, but I suspect my teammate would have been able to produce a lot more if we were physically in the same location. Most importantly though, I had a lot of fun and I look forward to participating again next year.
If you want to check out our rover, you can download our main round submission or our lightning round submission. Both contain source (and a 32-bit Linux binary) of a slightly updated version of the Rhope interpreter with support for things like sine and cosine, though the lightning round one has a bug with parsing floating point strings (this bug also exists in the stock Alpha 2 interpreter).