ICFP Contest 2009

It's been just about a year and I haven't posted anything... I've got a few drafts of posts, so maybe I'll try to get one or two of them done this summer. Anyway, this weekend was the ICFP contest. I don't have near as much to say about it as last year, mainly since I only spent about 16 hours working on it, starting Sunday afternoon, along with David Roundy and some help from our friend Joanna.

The problem

It was an interesting problem this year. Teams were required to implement a virtual machine to run "OrbitVM" binaries provided by the contest organizers. Then the interesting part was writing a controller to perform certain tasks in orbital dynamics (in 2d), ranging from doing a simple Hohmann transfer to change the radius of a circular orbit, to flying around to collect a number of satellites. The physics seems like it would be interesting to work out, but we didn't really get around to it. Just thinking about it, though, an orbit about a single body in 2d has four parameters: the semimajor axis (for simplicity, I'll assume it's an ellipse), the eccentricity, the orientation of the major axis, and the phase along the orbit. These can be calculated from the position and velocity (x, y, v_x, and v_y) of a satellite. On the controls side, there are only two "knobs" we can control: the impulses in the tangential and radial directions. So we can see that it can't be trivial to transfer from any orbit to any other, and in fact we could probably define some sort of metric to describe how distant two particular orbits are (minimizing a cost function composed of total impulse and time required). Of course, even with just elliptical orbits, this is well beyond the realm of tractability, but if it were implementable, it would lead to some sort of traveling salesman problem, except that the distances varied with time in incommensrate ways. What a mess... (not to mention the real problem also had a moon to make the orbits less than elliptical, and was integrated with a large enough time step to make the integration error somewhat important)

Our solution

That's enough abstraction. I enjoyed working on the contest, although we only solved the first sub-problem of performing a Hohmann transfer. With only one day, there really wasn't any chance to outdo last year's performance, but we decided to have some fun with it anyway. The original plan was to do it in postscript, so our team name was "Paper Jam in Tray 3". But it turned out that rolling our own IEEE doubles was just too tedious (postscript only supports singles natively), and the extra precision was important (at least, in the Verlet integrator David wrote). So instead we implemented all of our logic in the OrbitVM virtual machine. It wouldn't have been completely terrible to write straight assembler, but I felt it would be more fun to write a compiler, so we embedded an OrbitVM a compiler into Haskell. It was a pretty simple compiler, and would have benefited greatly from more developed control structures (the VM itself was rather lacking in control structures: every instruction was executed and every mutable value in memory was written to exactly once per time step; the only control structure was a conditional copy that could copy from one of two memory locations, depending on the result of a comparison). We did implement a static data type, Vector, that simplified dealing with 2d coordinates and velocities, but the part that was most frustrating to deal with was maintaining state from one time step to the next; with some more thought I believe it could have been improved quite a bit.

We also had to find some way to connect these programs together. A perl script provided good plumbing and also allowed us to intercept the communication and visualize the trajectories with ghostscript, as well as allowing us to inspect some of the internal quantities to see what was going wrong.

I spent a number of hours, after we finally got some points on the scoreboard, trying to get the second problem, but without a more sophisticated development system, it was difficult to try new ideas and we never quite managed to catch any moving satellites, although I was able to fly by them briefly (just the velocities were all wrong by the time the positions matched up). The basic strategy I used (at least for the case of both satellites in circular orbits) was to calculate the required "phase difference" for when to start the transfer such that I landed on the second orbit just as the target was passing by. This got me close, but not quite close enough, and I never figured out how to do the tiny tweaks of the orbit to close in. It might be fun to make a "real-time" orbit simulator to get some intuition for how to do this. There would be some orbiting circle and the goal would be to pilot a spacecraft into an orbit within the circle using a combination of radial and tangential burns. Though maybe once you're looking at it in the rotating frame it would just be a piece of cake. We never actually looked at the rotating frame, which was maybe our problem...

Download

In case you're curious, our source tree is available at http://pages.physics.cornell.edu/~shicks/darcs/icfp09/.