thirteen

Algorithm used in submission, team THIRTEEN, ICFP Contest 2009 [eng]

сентября 21, 2009 в 13:48 | Новости |

There were several requests from english-speaking audience about the algorithm

which was used by our team. So, this article may give some description.

Full source code is in at the end of that post (subversion url).

Team Thirteen algorithm contains the following parts:
————————————————————

1) Lambert transfer: given the

• current coordinates
• motion vector
• exact desired transfer time T
• destination point,

calculates the impulse vector. This is done analytically (matlab+books), and very fast algorithm is implemented (10 iterations max). The results are not exact, but are used as a basis for

• estimating the travel costs to any satellite
• actual transfer setup (see “9)”)

2) Choose the right time to start. Given the

• current position
• destination satellite
• 2 time brackets

calculates the delay (t0) before Lambert transfer and duration T of the transfer, so that transfer has optimal parameters (speed or fuel usage).

3) Moon gravity - when some “earth/moon” point is passed, Earth gravity is not taken into the account when calculating Lambert, and moon-centered calculations are performed.  Otherwise, moon is excluded from the Lamber equations same way.

4) bin -> java compiler. Produces java class for fast calculations, for each task. Input/Output as per specification, 1 time tick is calculated. ”clone” method for previews of the future.

5) Simulator: given the initial impulse and delta T, calculate final state of the world (T iterations of VM).

6) For task 4001-4004, bin -> java compiler which does NOT calculate all satellites, only earth/moon/traveller coordinates. This is done by tracking data dependencies in bin file and excluding all non-relevant calculations which result in non-needed ports. 15-20x speedup is achieved.

7) caching of satellites position for the whole time range of problem, for faster lookup at any time point (done once per problem). Together with “6)” it gives fast “future preview” ability with regard to satellites.

8 ) Travelling salesman problem, reducing the use of fuel, without visiting fuel station. By the way, score was added for visiting it (later we discovered it). When choosing next satellite, we optimized t0, and T (see “2)”) and used search depth of 2 satellites (current, next, one after next), and criteria was to minimize sum of fuel spent.

9) Precise meeting. Given the satellite, using the Lamber transfer, get the initial impulse. Then, minimize the function distance_to_destination_with_initial_impilses(Ix, Iy) function is implemented as a simulation flight using fast java implementation of formulas from bin file (see “4)” and “6)”). Using gradient descent for optimization. Problem: when travelling towards earth, calculates very slowly due to unsophisticated algorithm.

9a) when optimization fails due to very long computations, travel anyway with best found impulse, then calculate new impulse in the middle of travel. Repeat if needed.

10) another algorithm of travelling salesman, where speed of travel was optimized, but fuel was refilled at the base station, was developed, but due to competition time constraints, was not polished, and used as backup algorithm. This helped to solve 1 problem, where main algorithm failed (!) during the separate top-10 competition in the aftertime.