- Lead-up
- First few hours
- Day one progresses
- The push for the lightning round
- The morning after
- Day two
- Attacking problem 4
- Into the morning
- Extra notes and unimplemented ideas
- Code listings
Lead-up
Eric Stansifer is a friend of mine at Caltech, who is in the bay area this summer for an internship. Upon arriving here roughly two weeks ago, he told me about this contest. After looking at previous years' contest topics, I thought it was reasonably interesting and I thought I might as well try to participate. Up to opening day, we did no prep work, which in hindsight was a bit of a mistake, since Eric is a Haskell coder, and I only do C/C++. It took him a while to figure out the Haskell foreign function interface to call into my VM.
First few hours
On the morning-of, I skimmed the description without reading the problems at all and coded up the VM (OVM) in C in about 2 hours. Obviously, it didn't work. At all. It was well into the evening when it finally worked, having fixed the CMPZ immediate bit-size (how did the spec get this wrong?!), and a number of other really dumb things.
After waking up, Eric read through the problem descriptions and read up on all kinds of orbital transfers. By then I still hadn't really read the problem 1 description.
Day one progresses
The afternoon heat wasn't good for productivity nor my debugging. The first auxiliary tool to get coded up was a disassembler, translating the provided OBF binaries into human readable pseudo-assembly code and a corresponding program data file. An assembler was later created using C macros but was never really used. The unassembler made the VM internal code much less elegant with tons of preprocessor macros, since I avoided redefining each function by just including the implementations twice with difference macro definitions. At this point I was seriously thinking about making the VM a JIT compiler to x86 machine code, but I don't have any experience with that.
With the disassembly and some understanding of Hohmann transfers, we needed the initial conditions of the simulation. A set of programs were created to extract all the initial condition information from the binaries by running them forwards by one timestep. I hadn't realized that the sensor outputs for positions were all relative to our satellite, which made for some interesting conclusions. After working out that all satellites moved clockwise, Eric probably had our plan for solving the first two problems formulated.
By dinner time, the VM still wasn't in a working state, and we hadn't really done anything towards solving the problems. After dinner I found the last bug in the VM that prevented it from running binaries, and we could move forward with testing out the two-impulse Hohmann transfer for problem 1. After fixing a few more VM problems and coding up the Hohmann parameters found in Wikipedia, we had a final score of 67.7 for scenario 1001 sometime past midnight. Within a few seconds of seeing the score for 1001, Eric had computed in his head that the official score formula predicted something in the 79 range. It took us a few minutes to reverse engineer how the number 67.7 was obtained. First, we noticed the log dependence on time is actually an integer logarithm (ceiling of what you might think). Then we realized it was using the fuel consumed rather than the fuel remaining.
This was an exciting discovery and we wanted to notify the contest organizers about it. Of course, it would be to our advantage to not disclose something like this, but after verifying the problem we deemed it too obvious for others to not notice. At 2 in the morning we fired off an email, never receiving a response until the blog update the next morning.
Five minutes after the contest started I registered the junk submission account MySpoonIsTooBig (if you don't get the reference, google it) to download the binaries (I didn't know we could submit as many times as we wanted). Now, we wanted to come up with a new name that was also funny. We dug through my funny pictures folder until we found the above picture. At the time, we had the funniest name on the board, until we later saw "when i was 4 years old i was maimed by a giant pig". Well played.
At this point all we had was an input for 1001 that we knew would produce a non-failing score. The output of the simulator that drives the VM only produces an ASCII file of impulses at all timesteps. To convert this to the submission format, I wrote a small utility to compress and convert it into the OSF format. Due to the ambiguity in the specification about which timestep is considered timestep 0, it took me about half an hour to submit the damn thing without receiving a CRASHED status.
Now with the toolchain complete for solving the 100x series, we submitted 1002-1004 within a few minutes of each other, all with rather mediocre scores in the 60-70 range since we were being fuel misers. For the time being this would have to do.
The push for the lightning round
With problem 1 out of the way (for now), the focus was on problem 2. Eric realized early on that the problem is identical to problem 1 if we just wait in the initial circular orbit for a proper amount of time before proceeding with the Hohmann transfer. After working out all the math details, he handed me a set of equations to code up. The results were somewhat disappointing; we missed the target by a few kilometers. The difference was slight though, and probably mainly due to the discretization of time (the results should be exact for a continuous time evolution). We tried changing the way we round the waiting times but that didn't seem to fix it.
We gave up on 2001 temporarily to see how we might solve 2002. As we twiddled the way we round, we noticed that instead of rounding to the nearest integer, we got closer and closer to the target as we added larger and larger integer constants to the Hohmann transfer time. Finally, at adding 13 extra seconds, we hit the target. At three in the morning, ugly hacks like this don't seem so ugly, and this was just the start.
We tried this twiddling for 2001 but it was no good. Eric then noticed that we were overshooting the target, so he thought, what if we did all the calculations assuming the target sat in an orbit half a kilometer smaller? As it turns out, with this, our solution now hits the target. This added another hack to our bag of tricks. Luckily 2003 and 2004 require no such absurdity. After submitting all 8 problems, our score was 1006.1333, putting us at 7th place on the leaderboard.
By this time, it was past five in the morning, and our ability reason was stretching thin. Pretty convinced now that problem 3 was out of our reach for the Lightning Round, and receiving no response from the contest organizers on problem 1 scoring, we decided to abuse the binary's scoring bug as much as possible. (The plan was for me to wake up before 11 AM and submit fuel-optimized results if the binaries were changed.) We discussed how best to waste fuel, and decided that if we make wasteful burns forwards then immediately backwards to the direction of travel just after the Hohmann transfer, we could maximize our chances of remaining on course with the target trajectory. Also, to avoid accumulating error, we would split the amount of fuel into several smaller impulses to prevent large impulses from generating excessive drift in the two timesteps. Since problem 1 initial conditions always placed the our satellite at a starting angle of a multiple of 90 or 45 degrees, this fuel wasting method was quite straightforward to add in by hand.
So with this strategy, Eric sat there opening each input in vim, and manually adding around 5 cycles of extra burns, computing it all in his head. This worked astonishingly well, as we usually ended up with less than 5 m/s of fuel left (a testament to Eric's mental math abilities). In one case, we had 0.2 m/s of fuel left, giving a score within 0.002 of the theoretical maximum for the amount of time we took. This got us pretty excited, and after submitting all the new fuel-wasting inputs, our score sat at 1127.6835, putting us at 4th place; the highest score with only 8 problems submitted.
The morning after
I had set an alarm for 10:30 AM the previous night, and I awoke well before the alarm went off, despite getting less than 5 hours of sleep. I checked the ICFP page and saw the update that problem 1 scoring will remain the way it is. Great.
With Eric still asleep, and just less than an hour left to try to submit something for problem 3 for the lightning round, I got to work trying to generate some ad-hoc method to hit the elliptical orbit. I didn't get very far.
Day two
I spent the afternoon figuring out how to hit the ellipse and came up with this. It is reasonably easy to find an ellipse whose perigee is tangent to a starting point on a circle, and also tangent to the target ellipse. To do this, I expand the circle outwards from the starting point by increasing its eccentricity until it hits the target ellipse. Programatically, I perform a bisection search over the range of eccentricities, narrowing the difference between a lower (never intersects target ellipse) and upper bound (intersects target ellipse twice). However, these ellipses may not hit the target object at the right time, so we need to search over all starting locations. I know I'm close to hitting the target when, at the point of tangency to the target ellipse, the angular difference between where I am and the target is small. Performing a linear search over the set of starting angles, I am looking for two points where the phase difference (angle difference in [0, 2pi]) changes from just under 2pi to just above zero. I then perform a bisection search to maximize this phase difference. This now finalizes the elliptical transfer trajectory. Note that this method only works if the starting circular orbit doesn't intersect with the target ellipse.
Of course, just like in problem 2, due to discretization error, the trajectory won't hit the target. Not by a longshot. For 3001, I was off by more than 20km. An ad-hoc tweaking was not going to reliably get us on target. I would have to perform a nonlinear optimization. Gradient descent looked good.
Eric had started a writing decompiler in Haskell to translate the disassembly into a more readable form. It was about 5 PM now, and the afternoon heat was wearing us down; time to break for food. At the table, we discussed a few possible strategies for solving problem 4, including possible flight paths and maneuvers to reverse the direction of travel. I had plotted the trajectories of all satellites in problem 4 so we had a rough idea of what we were in for. Eric entertained the idea of approaching the problem as an optimization problem over satellite visitation order, but I was a bit more concerned with the logistics of how to get to a satellite. We went back to work on what we had been doing.
A short while later, Eric came upstairs to tell me of some successes with the decompiler, and shortly afterwards, I had a gradient descent optimized set of inputs for 3001 that would hit the target. With this, results for 3001, 3002, and 3004 were pumped out (with some tweaking of the optimization parameters). Scenario 3003 was a problem since the target ellipse intersects the initial circle, so my algorithm would always fail to find a suitable elliptical transfer. Making matters worse, the target ellipse is extremely eccentric, so any amount of delayed action for our satellite would mean a very long time-to-hit.
I mentioned this to Eric and he said I could try to just use a homing system (in hindsight, this is the equivalent of a proportional-derivative (PD) controller). He later revealed that was partly a joke since the control system is really only meant to home into targets very close to us, not something a million meters away. I thought we were doing pretty well with our fuel-miser strategy of using only two burns, so I was trying to devise a way to do it in only two burns. After about half an hour of trying, I just implemented Eric's controller.
The controller in its raw form basically sets the impulse equal to a linear combination of the velocity difference and position difference between us and the target. Basically, it tries to match velocity and position. Of course, when starting a thousand kilometers away from the target, the controller will be a bit overzealous in the first few steps; enough so that it drains all the fuel in the first few timesteps. I instituted a maximum cap on the impulse allowed, and it quickly converged. I notified Eric of this success, and he thought it was hilarious. He wondered what would happen if we twiddled the maxmimum impulse cap as well as the PD controller parameters, so we sat there for about 10 minutes fiddling with it until we were happy. In the end, we managed to complete problem 3 in just over 2600 seconds, while using under 20 percent of the fuel. At this point, we had a score of 2587.8953, putting us at 3rd place; the highest score with only 12 problems solved.
Later, we realized that the PD controller never outputs a zero impulse, so how could we possibly have had 900 seconds of convergence without impulse? We realized that my simulator dumps to ASCII with limited precision, so all small values are output as identically zero. ASCII formats saved the day again.
Attacking problem 4
It was around midnight now, meaning we had less than 11 hours to finish problem 4, and we basically had no idea what we were doing. Eric was planning out a strategy for solving problem 4 as well as automating problems 1-3 (so that we didn't have ridiculous manual hacks required). By this time his decompiler was getting sophisticated enough to make the decompiled output somewhat understandable. I was much more concerned with getting some kind of result out the door. We parted ways to work on our respective concerns.
Backtracking, I had recognized the need for a faster VM earlier and started working on a version of the VM with an identical interface, but specialized for computing the physics of problem 4 directly, instead of interpreting the binary. To do this, I needed the exact initial conditions from the binary. It took many hours (I had started earlier) to fully extract all the data for 4001, and with the help of the decompiler, made the extraction much quicker. Particularly tricky was the computation of satellite 10's initial velocity, which were not hardcoded, but computed using the physical constants. I think I had finally gotten my new VM working before 10 PM. The results matched the interpreted output to within 1e-12 relative error. I also added the ability to save the VM state so that simulations could be run forward without ruining an ongoing VM run. Unfortunately, this faster simulator (EVM) never got used. I probably shouldn't have spent so much time on it.
To get started producing some kind of partial solution to problem 4, I thought about starting with my approach to problem 3. The need for nonlinear optimization deterred me from taking that route, and I coded up a new state machine to just try to visit all the satellites in some given order by performing Hohmann transfers between them. Little did I know, in 4001, the satellite trajectories were not circles (but they looked like circles!), so i missed the first satellite by a few million meters. I must have been really tired since I didn't figure this out for a few hours. When I finally did, Eric and I discussed plans of attack some more, and we came up with an iterative algorithm to hit a target on an elliptical orbit starting from a circular orbit.
The algorithm goes like this. Suppose you have an initial estimate of where the satellite will be when you hit it (say, where it is right now). Then compute a Hohmann transfer to that point. You now know how long it will take to get there, and can therefore simulate where it will be after that amount of time. This provides an updated estimate of where it will be. If the algorithm converges, it will converge to the proper elliptical orbit needed to hit the object. Incorporated in this is a wait time of course, since a delay is needed to get the timing right, and we have to make the orbit circular after hitting a target. After coding this up (this happened in parallel with some other activities) it turned out to fail to hit the target, again due to discretization error. I shelved this approach temporarily.
Into the morning
Eric had been coding up a framework to drive my virtual machine in Haskell so that all high level decisions could be made in Haskell (my code up to this point had been pretty awful to look at). He had been looking into how to call Haskell from C, or how to call C from Haskell. After deciding the latter was the right thing to do, he drafted up an interface that my VM would have to implement for him to call it. It was 5 in the morning already.
After some more hacking on his part, Eric had Haskell code that could produce both fuel-optimized and fuel-depleting inputs for problem 1. It was probably 6 or 7 in the morning at this point, and we were getting too tired to properly do anything. Meanwhile, I had decided to use the iterative algorithm above and just perform a gradient descent optimization on it. The code before adding this looked reasonably clean, and afterwards, it was a wreck, but it worked for getting to satellite 0 of 4001 and 4003, giving scores just over 200 for each. Trying to do anything more than that was deemed beyond reach, and we called it quits. Our final score was something like 2650. In retrospect, since we never proceeded to any other satellites, we should not have consumed the extra fuel to make the final orbit circular (but who can think properly after being awake for 24 hours).
Extra notes and unimplemented ideas
Having just taken a course on convex optimization, I was trying to come up with ways of using those ideas for this contest. At 3 hours to go, I realized that I could pose the homing problem as a convex problem, but it would be hopeless to try to solve it that way (I only know how to solve things using the Matlab package CVX). It goes like this. We want to minimize fuel, primarily, since presumably we are already close to the target. The dynamics of the kinematic equations of motion are linear in position and velocity (4 state variables). The problem here is that gravity is nonlinear. However, in homing, we are presumably not moving over large distances, so we model gravity as an affine function of position. This then gives us a linear dynamical system with 4 state variables, where the inputs are the velocity change and a constant (set to unity). The convex problem is then to minimize the 1-norm of the inputs, subject to the starting conditions, and an end time condition of reaching the target exactly. We would need to explicitly specify the end time, but presumably we could try out many end times and optimize over score. I think this problem may be recast as a linear program, but I never worked it out since I knew I could not implement it before the contest ended.
Eric had some ideas of running global optimizations, but I'll have to wait for him to write it up.
Code listings
- Orbit Virtual Machine implementation (pure C)
- Explicit Virtual Machine (implements problem 4 directly) (pure C)
- Disassembler (pure C)
- unasm.c - gcc -I../ovm unasm.c ../ovm/ovm.c ../ovm/ovm_run.c -o unasm