Download the videos: Spiral Small Scatter
The ICFP has come and gone again this year, and this time I was aided by Kimberly Dorn and Ziba Scott. Overall, the contest was really quite well organized, and all the organizers were quite nice and worked very hard for us, fixing bugs and compiling material for people on different platforms. However, I did feel that it could have been handled a little better. The task required that we submit a binary or source that would run/compile on the Knoppix LiveCD environment they gave us, and we were to test our code using a server supplied to us -- but only compiled for Linux. I think that this gave Windows users an unfair advantage. One of my team members (Kimberly) spent the entire first day of work trying to get the server running so they could even test the code. Eventually, the workaround turned out to be emulation using qemu, which while slow and annoying to use, ended up working to some extent.
The other part that could have been handled better was the submission process. Because the code had to run on the LiveCD, and had to be in a specific format upon submission, actually submitting the code felt as if doing so in the dark. The submission page claimed that rudimentary testing would be done to make sure your submission was in the proper format, but there was no positive feedback about this. Also, in previous years there was a scoreboard keeping a running total of how each team was doing. This might have been prohibitive to do, not only because you don't want to run random code on your test servers while people are submitting live, but because each run of the program took at least a few minutes (for reasons that will become clear soon).
The task this year was to command Martian rovers along the surface of Mars, avoiding boulders, craters and nasty (mostly) intelligent martians. And how were we to control these rovers? Our program had to connect to a TCP port on a server (specified by command line arguments) and receive data from the rover and send it rudimentary driving commands (accelerate, brake, turn, turn more). Sounds simple enough, but any of you who have tried programming video games know that this is not a simple task. Our task was made more difficult by the following:
Our first job was split up into two: Kimberly would program the code that would figure out the unknown constants and I would write the basic code to read in the telemetry data and set up a system to actually command the rover -- this basically amounted to implementing the problem specs. The code ran in two threads: one to read the data and one to calculate a course based on the data we'd gathered. It quickly became clear that the first problem we'd have would be to plot a course around obstacles -- never mind the roving martians. Meanwhile, Kimberly had been trying to get the official server working on her computer so she could test it out in the first place. This proved to be quite hard for a Windows user. They didn't even provide Cygwin versions, but to their credit, they made an attempt to do so during the course of the contest. Needless to say, just trying to get the server up and running took her an entire day.
Fortunately, two things that simplified our life were: home base was always at coordinate (0,0) and all the obstacles were perfect circles. So, after making the bot roll blindly towards home, the next thing I did was code something up to detect obstacles between the rover and home base. I'm not familiar at all with collision detection, so I'm proud of my solution: find the line of the rover as an equation, and then solve the system of equations between the line and the circle of the known obstacle. If you work out the math, you can end up with a quadratic equation solving for x, and then you need only to find if the determinant was greater than zero or not. That seems pretty efficient to me.
Once the program knew how to detect if objects were between it and home base, the next thing was to plan a way around them. My first guess was to simply have the rover move at an angle and then try and see if it could make it to home base without any obstacles; I would use waypoints to plot its course. This was admittedly stupid, but it at least passed tests occasionally. This was the version we submitted for the lightning round.
This version of the program wasn't very good. It kept going off in stupid ways and would spiral around home base. What's more is that I had no real way of knowing if my collision detector was working other than printing out coordinates and drawing the lines out myself (or with gnuplot, which I'd never used before). Fortunately, Ziba began programming around this time and started working on a visualizer using pygame. The visualizer showed the moving rover, its programmed waypoints, its path, and pretty sweet Martian landscape background.
From there it was time to talk real strategy. The waypoint system we liked, but it needed to be smarter. We discussed the problems facing us: we needed a good path to the home base, and we needed to stay on the path as much as possible -- the test is timed, so our rover needed to get there as fast as possible. That meant a naive control strategy for the rover sent it off on huge curves. For the first problem, we decided that an easy way to go about it would be hill-climbing: we'd see if there was any obstacles between the rover and base, and if so, we'd set a waypoint to the closer side of the obstacle (provided there were no obstacles in between). Then we'd repeat the process recursively until we found ourselves a clean path.
We hit a slight snag in implementing this, because since we didn't have full knowledge of the obstacles ahead of time, we had to update our path when we saw a new obstacle. This led to problems when the path of the rover had gone slightly off course, making the newly updated course completely different than the last, making the rover unable to respond quickly enough, and more often than not, it ended up in a crater. So we had the system only update when a new object was in the way of our new path. This process is also where the visualizer came in ridiculously useful: it allowed Ziba to see that the collision detection was giving false positives! Turns out that in my sleep deprived status, my collision detection math was off by a small constant, and it got fixed.
This worked well enough, but our rover was still taking the turns too hard. I suggested that we drive smarter: come up with a handful of strategies (brake, then turn, turn and accelerate, etc) and then plot the physics out to see if we'd hit any obstacles doing so. Unfortunately, my lack of phyiscs calculus left me unable to transform the equation given to us for the movement of the rover into anything useful. Fortunately, in the meantime, Kimberly talked me out of this plan, and instead suggested that a simpler method would be to simply slow down enough to make any necessary turns. This was math we could mostly handle, by calculating the speed needed to turn the proper amount given an acceptable "miss" distance. This is where the aforementioned code that figured out the unknown constants really came into play. When I couldn't figure out the equations to know how soon to brake in order to reach the target speed, we simply did a simulation using the equation given in the problem specs.
The martians, in the meantime, had been ignored. It was already Sunday night, and it was my shift, so I was coding alone. I threw together a small bit of code that detected if a martian was headed straight for the rover. When this happened, I had the rover make some evasive manuvers (turn!) and then recalculate its course. It didn't work too well, and was very stupid, but I don't think it'll end up putting the rover into too many craters.
Finally, at submission time, I had an obligatory crisis, resetting my git repository in an attempt to add libraries to the code so the organizers could run our sweet visualization. The submission got in at 11:57am PDT, just in time.
How could the code have been better?
This was my best experience with the ICFP yet. Our team really came together nicely and we were able to break the up into logical tasks. I really feel that if I had spent more time personally (I had some engagements that weekend) on the code, we might have been able to do more of the above and actually been contenders. As it is, I feel confident that our team might make it past some of the first heats. Whatever happens with the score, however, I think almost everything went right this year, and we all did the best job we could. See you all next year!
Pretend Robot Pants
Download our code! You'll need pygame to use the visualizer (set VIZ_DEBUG to True).
email dranger a gmail d com