The ICFP Programming Contest 2009

Two weeks ago the annual ICFP Programming Contest took place and, once again, the glorious team Funktion im Kopf der Mensch participated.

This year’s task was to control a satellite orbiting the earth in two-dimensional space and make it meet a few increasingly difficult goals. We were given the specification of a very simple virtual machine and a few programs for that machine, which simulate the motions of the satellite to be controlled and of zero or more target satellites (and later also of the moon). Each run of such a program simulates a timestep of one second and outputs various data, such as the satellite’s positions, the remaining fuel and the score via variables called “output ports”. Commands can be given via “input ports”. Apart from the “scenario selection” command before the first timestep the only commands that can be given are thruster actuations, which are only limited by the available fuel, i.e. the whole remaining fuel can be spent in one timestep if necessary.

The first problem was a transfer from one circular orbit around the earth into another circular one and to stay in that orbit within a radius of one kilometer for 900 seconds. A very simple and efficient way of achieving such an orbit change is the Hohmann transfer, which requires only two thrusts. Here’s what it looks like in our visualization tool:

Screenshot

It wasn’t too hard to correctly perform this transfer, but already a few problems cropped up. Using the formulae for calculating the thrusts for a Hohmann transfer analytically we saw that the simulated orbits differed a tiny bit from what they would be in reality, which was enough to throw us off by more than one kilometer.

Another approach we followed was to find the correct thrust by simply trying out some value, simulating the flight path of the satellite and, depending on whether our flight was too short or too long, adjust the thrust, until we arrived at the correct distance within some arbitrary tolerance. We discovered that by doing this binary search we could find the thrust to bring us within one micrometer of the mark.

For the second problem we again had to transfer from a circular to another circular orbit, but this time we had to meet with another satellite there. In other words, not only did we have to get to the right place, but also at the right time.

A very simple approach to this problem is to just wait until the two satellites are lined up in such a way that when our satellite does the transfer, it arrives in the target orbit at exactly the location of the target satellite at that time. The downside of this solution is that the wait might be a very long one.

To avoid having to wait one can instead do a bi-elliptic transfer, which requires three thrusts and first transports the satellite into a higher (or lower) elliptical orbit which can be freely chosen within some limits. Because the height of that orbit determines how long it takes the satellite to come back, we can choose an orbit which exactly makes up for the time difference in the target orbit between the two satellites. Here’s what it looks like:

Screenshot

The third problem is like the second one, except that the orbits are not circular anymore, but elliptical, which requires some intricate navigation. We came up with this maneuver:

Blackboard

We start out in the elliptical orbit between points A and B and want to meet the target satellite at point E. The trick here is point C, which we can choose arbitrarily high or low, to adjust our timing, like in the second problem. By searching for the correct thrusts this works out pretty well, more or less, and looks like this:

Screenshot

When working on this problem we came upon an approach we should have though of much earlier: Just blindly follow the target satellite, orbital mechanics be damned. Doing this correctly is not entirely trivial, but much simpler than calculating thrusts, and in cases where the satellites are close, it works amazingly well:

Screenshot

It can also gives some very amusing results when they’re not close:

Screenshot

Here our satellite, which, left on its own, would have remained in a comparatively low orbit, makes a 90 degree turn to catch up with the satellite in the much higher orbit, and once it’s close to it, makes another 90 degree turn to follow it.

At this point we hit our biggest hold-up. The organizers of the competition had set up a system for submitting traces of the instructions given to the satellite, the scores of which were displayed on a publicly visible scoreboard, so the teams could compare their progress. The other function that this system served for the teams was to be able to verify their implementations of their virtual machines. When submitting this trace, and various variations of it, we always got the automatic reply that it “CRASHED”, so naturally we assumed that our virtual machine was at fault, and spent hours upon hours trying to identify the problem or to work around it. The issue wasn’t cleared up until after the contest was over, and I’ll discuss it below.

The fourth and last problem was to meet not one but 11 satellites in various orbits. Originally the specification mentioned 12 satellites, and the fact that the 12th satellite didn’t move relative to ours, combined with our earlier problems, convinced us even more that our virtual machine was faulty, so we spent even more time trying to find the issue. Alas, the error in the specification was corrected and we continued working on the rendezvous.

Two complications in this problem were that the satellite’s fuel was very limited and that there was the moon, in addition to the earth, exerting gravity. To get by with the satellite’s small fuel tank, there was a fueling station in low earth orbit which would refuel the satellite on contact, so we could meet one or two satellites and then return to refuel, etc.

We tried meeting a few satellites with the maneuver we had developed for problem three, but soon discovered that for the satellites in the outer orbits, we were very far off our mark. We had calculated the time-delay point not by doing the simulation, but with a simple formula, which worked perfectly for problem three, but in problem four our orbits were distorted by the moon, so that we could easily be off by a hundred seconds, which is quite a lot for a satellite that travels at several kilometers per second. In addition to that, the points at which we thrusted were no longer necessarily the apsides of the orbits, so the error accumulated. Even for the satellites in lower orbits our path would be distorted enough to spoil the rendezvous with the fueling station, so we used the simple follower algorithm to catch up with it. Here we ran into another issue: The fueling station was in a very low orbit, and the follower algorithm was not concerned with orbits at all, so when it had done its job it would sometimes leave us on a collision course with earth, which we had to correct.

At this point there were only a few hours left until the end of the contest, but we came up with two new, very simple approaches. The first was to do only simple transfers from circular to circular orbits (as circular as the moon’s gravity permits), to meet the target satellites in those orbits and to do time-delays by transferring into lower or higher elliptical orbits and then back into the circular orbits again. All these transfers would be exactly calculated by our binary search method, so there would be very little that could go wrong.

The second approach was to do our more complicated maneuver, but instead of single thrusts to go from orbit to orbit, suffering from the moon’s gravity, we would calculate the orbits as if there was no moon and then use our follower algorithm to chase a “virtual” satellite traveling along those orbits. All we had to do was to calculate them correctly and the follower algorithm would do the rest. The only question remaining was whether it wouldn’t waste too much fuel doing corrective thrusts. Our first tests suggested that it would work just fine. Unfortunately time ran out and we weren’t able to finish either algorithm.

I mentioned earlier that the problems we had with our virtual machine were eventually resolved, but only after the contest had ended. In fact, we had two almost completely independent virtual machine implementations – one an interpreter written in OCaml, the other a compiler written in Python, which generates C code. Both VMs gave exactly the same results on our traces, whereas submitting them always failed.

We did our best to find the bug. We examined our code multiple times, ran it on different machines to see if the floating point math might be the culprit, tried other team’s traces that were made public by them. When we found nothing we contacted the organizers, mailed them our traces, described our problems and asked them to give us more information about why our traces failed, but all we got back was the equivalent of “Sorry, we can’t help you.”. All the information we ever got from the submission system was “CRASHED”.

After the contest we were contacted Andy Gill, the contest’s chair. He sent us their virtual machine implementation, which, on my machines, accepted our traces just fine. I asked him to try our trace on his machine, where it also worked fine. In the end it transpired that their submission system had a bug and would silently truncate all traces to 64K.

Drawing a conclusion over the contest I must say that the task was interesting and well chosen, but that the contest was organized and executed very poorly. The task description made the impression of not having gone through a single round of testing, the submission system gave no feedback as to why a submission failed, making it very hard to find problems in the virtual machine (or, as would have been even more important, in the submission system itself) and trying to get non-trivial information from the organizers during the contest was essentially impossible. I do realize that organizing such a contest is a huge and difficult task, but out of the eight ICFP programming contests I’ve participated in, this was the worst-organized one.

Which means that next year it’s almost certainly going to be much better – hurray!