ICFP Contest 2008

(Browse or download the code at http://www.physics.cornell.edu/~shicks/icfp08)

So, I just finished sleeping off a "double all-nighter" for the ICFP Programming Contest. The task this year was to write a controller for a Mars rover. The program would connect to a server which would send it periodic telemetry updates and then it would send back instructions, either Accelerate, Brake, Left, or Right. I had tried to get a team together for this contest, but it was apparently a busy weekend and all my programmer friends had other plans.

After thinking about the problem (and my situation as a solo entry) for a few minutes, I decided it would be interesting to see if I could write it in TeX. Lately I've been writing a whole lot of TeX for Andy Ruina, as well as for a macro package (inlinedef) I recently submitted to CTAN, so the idea didn't seem too crazy ("When all you've got is a hammer...").

Initial Work

The first problem that arose immediately after I decided on TeX was that TeX has no network access. So I had to make a small concession in writing a small Perl wrapper to do the networking. In the end, this file would be under a hundred lines, so I considered it a necessary, but minimal, evil. On one or two occasions I thought about farming some computation out to the Perl wrapper (such as trig), but in the end decided to stay pure. I learned about the IO::Socket::INET library and used the IPC::Open2 package to open a socket and a two-way pipe to a TeX process. Then we just read the TeX output and wait for special commands. Occasionally we'll write "WANT" which is a signal to Perl that TeX is ready for the next packet of information. Or else "HERE: " which tells Perl to send the following signal back to the server. I coded this up and found that it was really all that was needed to connect TeX to the world. Next, we needed to interpret the data. The server sent plain text data in the form of

  I 600.0 600.0 30000 60.0 ... ;

with a different number of mostly-numerical arguments depending on which letter came first (this determined what kind of datum it was). Since TeX can already parse this sort of thing, I figured the best bet would be to just make these letters all 'active characters' inside TeX so that they acted like control sequences. This worked well because occasionally multiple commands arrived on the same line, and so we'd need to do something special to account for this otherwise, but now it was automatic. More often, however, TeX's requests for data were more frequent than the packets were arriving (this is a good thing), but TeX's request (\read) is blocking, so we just sent an empty line in this case.

Math

If I were writing this in a real language like C++ or Haskell, one of the first things I would do would be to find or write a convenient data type for 2d vectors, since they're all over the place here. But TeX doesn't even really support things as simple as floating-point multiplication or (even worse) division. So I started by kyping some fixed-point multiplication and division macros I remembered seeing on comp.text.tex a while back (posted in the mid-90's by Donald Arseneau). I also kyped Kevin Hamlen's sqrt macro from his CDLabels package that I'd remembered him boasting about. These simple tools in hand, I was able to start making some real progress. I defined a bunch of counters (integer variables) and lengths (fixed-point numbers) and some booleans to keep track of what time it was, where we were and wanted to go, and which way we wanted to turn (wow, alliteration). Then, each time we received telemetry updates, I would turn towards the target if we were off by more than 20 degrees, brake if we were off by more than 90, and accelerate otherwise.

Of course, to figure out how far off from the target we were, I needed an arctangent function, and this is definitely not provided by TeX. So I set about to write \atan (I would have called it \atan2, since that's really what it was, but names can't have numbers normally). Really about the only thing that was feasible to do here was a polynomial expansion. I opened up Octave and plotted tan(x) next to x+x^3/3 (naturally) from 0 to pi/4, and it didn't look that great. But it looked like I could probably do a better job by just tweaking the cubic coefficient by hand. In the end, I settled on atan(x)~x-.2x^2 (sure, I could have optimized it without much difficulty - in fact I just did and it turns out that -.17297x^2 works slightly better, though I would have done really better with the cubic term -.26219x^3, which I've now implemented, or even better, -.05x^2-.18796x^3 -- thanks SciPy). So I coded this up and it seemed to get the job done, anyway. I downloaded the sample server and maps and watched how it worked on the simplest map, with no craters to crash into and die. It didn't quite work, but a little tweaking of the numbers made a big difference and I was able to get home. I went to bed Saturday morning around 7am (EDT) and got 7 hours sleep before I had to wake up for sailing and then having some people over to my apartment, all of which kept me busy until about 10pm.

An inverse heisenbug

According to the jargon file, a heisenbug is one that disappears when you try to debug it. In this case, my code worked okay, but when I tried to see what it was doing by turning on visualization, it suddenly stopped working as well. It wasn't too difficult to figure out that the visualization was slowing down the server so that it didn't deliver all the telemetry data in a timely way. so I decided that I needed better timing. It turns out that even turning on tracing to the log file in TeX is enough to reduce the resolution beyond workability, and in my final code, in later runs when there's a long list of obstacles, that starts slowing it down too much too. TeX doesn't have any sort of timing functions (\time returns the time to the minute that the typesetting began but is in fact constant). So again comes Perl to the rescue. Presumably I could have measured something like distance travelled at a known speed and backed out an estimate for the amount of time spent between iterations, but this would of course changed depending on the situation, so again, I felt justified in resorting to Perl here. Now whenever TeX asked Perl for data, we included a timestamp in the response to keep our own clock. This gave a much better resolution and we could then estimate where we were and make decisions about 10x as often. By 2am Sunday, the rover could make it home consistently on the easy map with no dangers, but usually fell into craters on the more complicated ones, so this was the next thing to be addressed.

Collision avoidance

By far the most difficult (and frustrating) part of the contest was collision avoidance. I tried a number of things to make it smarter, but they all failed miserably. They typically did worse than before I tried to do anything. Generally, I tried the logic that at any time we've got a target we're shooting for, and if at any time there was a known obstacle between the current position and the target, we'd move the target to a place that wasn't hindered (now that I'm writing this, I see the error here much more clearly). Then we issue commands to steer us toward that new target. If ever the path home was unblocked, we'd try to go there instead.

It took a long time to get this code to behave as I wanted. Often I'd find the rover turning the wrong direction entirely, driving straight into craters, driving straight for the outside edge of the map, or once, hitting the same boulder repeatedly until time ran out. If I knew how to do it, it would be neat to stitch together all these bloopers and make a 2-3 minute youtube video of the bloopers and then see them gradually improve to the final result (yay for darcs that that's even possible). Most helpful in this process was Octave (a free MATlab clone) - at one point I coded up a debugging message that printed out Octave code to plot a graph with lines from the current position to the target, the new trajectory, and the obstacle in question. Often the new trajectory was worse than the original one and I could go step-by-step to figure out why that was happening. Eventually when all these little errors were debugged, I had a code that did exactly what I wanted it to do, but it still did no better than if I'd done nothing at all to avoid the obstacles. This was the way it went for most of Sunday (I took an hour nap before church, but otherwise spent the whole time working). People on the IRC channel were talking about A*-algorithms and such, but that was much too smart for me - I had a hard enough time just getting to where I wanted to go when there weren't obstacles - so I just kept plugging away.

Around dinner time, Geoff called and suggested I go to his house to watch a movie. I was trying out a new idea I had, much simpler than many of the others: implement a two-state machine. The rover is either in the running state, where it's turning towards home, or else it's in the swerving state, where it's avoiding an object. If the rover sees an object in the way, closer than a certain distance (determined by the time it would take to turn 90 degrees at max speed, but this foolishly ignored the unknown turning acceleration, which turned out to be pretty important, and could probably have been discovered without too much difficulty... if only I had a team), then it would start swerving away from the object. The key point here was that we were looking ahead of us, rather than looking always toward home. So surprisingly we stopped running into things! I eventually converged on the logic that it would keep turning until it was no longer obstructed, and then it would go into a tunnel-vision mode, heading straight forward until the object it was swerving past was directly perpendicular with its direction, so that we know it's passed before trying to turn back home. This revealed all sorts more bugs as my dot product apparently just didn't work, but eventually I got it all worked out so that by the time I went over to Geoff and Erin's, I had a working version to show them, swerving back and forth and reaching the goal about 80% of the time. Around this time I also called up David Roundy and told him what I was up to. He suggested a few things, including the team name I finally settled on (actually, I think this was his sister-in-law), The Lone TeXnician, and a bit about what I should do with my README file.

The icing on top

By early Monday morning, all I had left to do was clean it up, package it, and make sure it worked on the LiveCD environment that would be used in judging. The latter part was actually a bit difficult and I had been working on and off the whole time to figure out how to install TeX on the system with neither internet connection (apt-get would have been too easy...) or sending in a 50MB tarball with all of the basic TeXLive ditribution in it. I eventually figured out how to get a 2MB portion of the distribution to work by copying files from my /usr/bin/ and /usr/share/texmf/ and running `texhash` over and over again. I spent most of the rest of my time on an extra feature I really wanted. I would use LaTeX's picture environment to draw a map of the planet and trace the path that the rover followed. It took a while to get this working - I started out trying to make a single picture per trial and had grouping issues. I switched to using a separate (but overlapping) picture for each thing I wanted to draw, but they didn't line up properly. I tried saving all the drawing commands to a token list so that I could draw the whole thing at once at the end of the trial, but token list operations are O(n) in the length, so I started lagging way behind and couldn't keep up with the server (it was real-time, remember). Ultimately, I tracked down all but a small issue which caused misalignment only later in the process. This was eventually fixed when I found the errors, both in the swerving code (as I should have realized when they started so late and the trajectory up until them was straight, but then it curved - if I had painted the two modes in different colors like I originally wanted to, it would have been even more blatantly obvious!). Both errors came from putting decimal numbers where an integer was expected (stupid non-typed languages...) resulting in the fractional part being typeset instead of used mathematically, and pushing the reference point away from where it belonged.

Conclusion

I ended up submitting code that I was very proud of. It ignored the ravenous martians entirely, and had a hard time in some tight situations (and some not-so-tight), but in general it made its way home about as well as (or better than) you might expect for 1200 lines of TeX. I ended up getting 8 hours of sleep over the course of three nights, and promptly crashed for 17 hours.

You can browse or download the code if you like. I've cleaned it up a little bit since submission, in particular using better trig approximations I worked out while writing this. If you want to run it, you'll probably need a *nix system. You'll also need to download the simulation server and maps (remember to use '-v' to get a visualization window). Pass the '-l' option to `texsocket` to run in LaTeX and get the PDF output. Unfortunately I don't deal with disconnecting servers very well in the version I submitted, so it doesn't actually produce the PDF (more than) half the time and never gives any hint as to why.

Edit: pictures and pdf documents

Edit 2: Shortly after the contest ended, I learned of pdftex's built-in timers, which one of the commenters noted. I also learned about /dev/tcp (although the contest LiveCD didn't have it compiled into bash anyway). With all that working together, I could presumably have written a completely TeX solution (although blocking vs. non-blocking network access would certainly be an issue... maybe if TeX forked an extra process of itself...). Also, since it's now public knowledge, I did indeed win the judges prize.

I've turned off comments because of spam. If you want to say something, feel free to email me.