ICFPC 2009

I spent this weekend participating in the ICFP contest. This year the task was a series of problems of increasing difficulty in which we had to steer a satellite orbiting the Earth in order to accomplish various objectives. Like the task last year, it depended heavily on physics, mathematics, your knowledge of a particular domain and the stability of your numerical calculations, not to mention the need for the occasional compensating manoeuvre. It was fairly tedious and I didn't quite enjoy it as much as I did the tasks from some of the previous years.

Like the tasks in 2006 and 2007, the task this year involved implementing a virtual machine so that the teams could use whichever language and environment they felt comfortable with, while relieving the organisers of the onerous task of having to support myriad languages and libraries that nevertheless left many a team grumbling in dissatisfaction.

The organisers supplied binaries for simulating the different problems. These binaries had to be interpreted in a virtual machine implemented by the teams and represented the controller of the satellite. The teams had to feed inputs to this controller in order to solve the associated problem. They then had to submit the execution traces of these simulations as their solutions. They would typically also implement a visualisation tool to see what is happening. The little-endian 4-byte unsigned integers and 8-byte IEEE-754 floating-point numbers used by the virtual machine input and output formats were a perfect match for programmes running on x86-32.

Catching a Target Satellite (in Red) Using a Hohmann Transfer Orbit

The simplest problem was to put the satellite into another orbit using a Hohmann transfer orbit while burning the least amount of fuel. This is a neat two-burn manoeuvre that transfers a satellite in one circular orbit into another circular orbit using an interim elliptical half-orbit. The next couple of problems were to attempt a rendezvous with a passive target satellite orbiting in circular and elliptical orbits respectively. The hardest problem ("Operation Clear Skies") was to make the satellite rendezvous with various other passive satellites in different orbits around the Earth, with the Moon also exerting its gravitational pull, while stopping by every now and then at an orbiting fuel station to replenish burnt fuel. Each problem had four different configurations representing various test scenarios.

The Final "Operation Clear Skies" Problem (Without the Moon)

I chose C99 for my implementation and used SDL for the graphics. I spent the first day learning about the basics of orbital mechanics, implementing the virtual machine, creating a basic visualisation tool and solving the first problem. I spent the second and third days improving the visualisation tool and trying to solve the second problem with an acceptable margin of error (staying within 1 km of the target satellite for at least 900 seconds). I gave up on the third day since it became somewhat irritating to continue with the task. I ended up having submitted solutions only to the four configurations from the first problem.

A lot of my time on the first day was spent in trying to figure out why my satellite was not moving in the direction I intended for it, until I finally realised that I had to fire its thrusters in the direction opposite to the target direction. For the rendezvous in the second problem, my satellite would get somewhat close to the target satellite, but not close enough to term it a success. This was partly because the discrete per-second simulation allowed manoeuvres only every one second and partly because of compounding numerical errors. I tried a lot of compensating manoeuvres to overcome their effects, but still couldn't solve it satisfactorily.

I am now filled with immense respect for rocket scientists who manage to successfully dock space shuttles, space stations and satellites under much more complicated conditions than the ones simulated by the task for this year's contest. Last year, I was similarly in awe of designers of autonomous rovers for harsh alien terrains like that on Mars.

Update (2009-07-07): There is now an ICFP contest sub-reddit where you can find links to write-ups from other teams.

Tweet