Mars Mission Results

Navigation

Introduction

This is Matthew Ogilvie's solution to the Mars Rescue Mission Challenge.

Downloads: The plain-C program can be downloaded by clicking here. This newer version fixes a slight bug in the remainingCost() function that occasionally caused the subsolution optimizer to find non-optimal subsolutions. You can also still get the older version. You can also download some additional tools I used (maps, scripts, and an alternate version of marsimg.cpp). Some sample solutions are listed below.

This implementation can find optimal solutions for moderately large maps (generally best with the --compress 1 option) fairly rapidly. Generally this mode is memory-usage bound.

It can also find good nonoptimal solutions for larger maps and/or multiple maps by optimizing subsequences of an initial rough solution that is found first. This tends to be CPU bound, with configurable tradeoffs between the memory/CPU usage, and the quality of the found solutions.

I learned about this contest from Slashdot. Some years ago my AI class attempted to solve a similar kind of problem (a "sliding numbers puzzle") using Lisp (it was a homework assignment), but due to limited memory in machines at the time, and the inherit inefficiencies of lisp, no one was not very successful at solving puzzles that had been more then slightly randomized. I remember thinking I could probably do much better with tight C code, but never got around to it. So when I saw a contest with actual prizes for coding up a similar type of algorithm, I overcame inertia and started coding. I haven't really kept track of how much time I've spent on this, but I'm sure it is more then I originally intended to.

General Notes:

  1. The core "optimize()" algorithm just does a breadth-first search for the best path. It stores all "needs to be visited" states in a priority queue/heap.

  2. It also stores all previously seen states. They are stored in either a hash table, or a tightly packed array attached to each square in the map. Overall the tightly packed array may have a slight advantage in memory usage over the heap when most states need to be seen (depending on how many states are unreachable but listed in the table), but where it really shines is when the total table size gets bigger then RAM. The packed array has better memory access locality, and when the table size is larger then RAM, continued progress is much faster then with the hash table.

    Note that the hash table is still used as part of the heap when the packed array is enabled; in that case the hash table will only store the states that are also in the heap.

  3. In order to handle bigger maps and/or multiple targets, it can also be put into a "rough solution followed by optimization" mode. The rough solution algorithm basically solves a version of the problem at the scale of the input map where the only legal moves are up, down, left, and right, with no concept of velocity. It then converts that rough solution to an unoptimized solution by running optimize() between each pair of adjacent states in the rough solution, and concatenating the result together. It then improves the unoptimized solution by splitting off short subsolutions, finding the start and end states of the subsolution, and using optimize() to find the best way to get from the start to end states of the subsolution.

  4. Multitarget maps are solved by first constructing a cost table between all pairs of targets (finding improved rough paths as described above), then running a simulated annealing based traveling salesman algorithm on the cost table. It then composes a full solution from the found target sequence, and uses the "improve" algorithm to improve it further.

  5. The optimize() routine also has a "remainingCost()" heuristic that does a conservative estimate (never over-estimate) of the remaining cost to reach the end state. This is only enabled when doing subsolution optimizations, since it won't work very well if there are a lot of of twists and turns before reaching the end state.

  6. With a small subsolution size (12 to 15), I can get a reasonable solution to map.txt in about an hour without swapping on a puny 200MHz PPro with only 64 MB ram.

  7. Most of my real runs were done on a 2.6GHz P4 with 1GB ram. It can find optimal solutions to map.txt in 4 to 6 minutes (using the compressed state mode), and digs slightly into swap space. I did not try to do optimal solutions of any of the bigger maps.

  8. Could easily force a particular path by inserting extra walls in the map.

  9. Could easily avoid hitting walls by giving a large --wall cost.

  10. A bit harder to ensure soft landing at end: need to modify termination conditions in the code with with more special cases.

  11. To extend to 3D: Rule extensions: Add 2 more thrusters, controlled with one bit each. New direction breaks into 10 subpositions per map position, and has 21 different velocities (-10<=vz<=10).

    Rough solution is probably easy. Improving rough solution might be difficult; you might be stuck only being able to improve very short subsolutions. Optimal solution for anything larger then very very small is hard.

  12. Theoretically it could be extended to find optimal solutions to multitarget maps by using a bitmask of acquired targets, instead of a target sequence number. But it is likely it would need good hueristics (better then remainingCost()) to solve very many targets and/or anything very large at all.

  13. Slightly increase caching state information to improve rough solution improvement performance?

  14. During "improvement", perhaps allow targeting a sequence of end states from the input sequence, for a wider objective cross section?

  15. Maybe eliminate "all seen state" table; only remember "need to be processed"? I'm worried this would cause a lot of duplicated effort (re-calc a state multiple times). But maybe an intermediate solution would be possible: continue to have a table bigger then the heap, but allow stuff to expire from and be taken out of the table eventually.

    Or maybe keep some kind of "coarse" (map-resolution?) cache; ignore new state if it is substantially worse then the best in its coarse collection of states.

    Research would be needed to decide how either of these might be done.

  16. Perhaps use an etching/line-thinning algorithm to convert traversable areas to a single pixel thick, convert to a logical graph structure, and use some variations of the "rough" solution idea to drive solution finding.

  17. Go even more coarse then map resolution, in some kind of divide-and-conquer algorithm?

  18. A totally different optimization approach: Use genetic algorithm technique to improve initial rough solution?

  19. Could eliminate "cost" from CompressedState completely (recompute from action and remainingCost() whenever needed...). But this weaken cache locality.

    Could eliminate 1 or 2 bits per velocity with smarter implementation. Could eliminate "action", it can be reconstructed by finding the "optimal" way to get to this state from previous one...

    Three bytes per state should be possible (manual bit mangling to avoid structure alignment of 4). Two bytes per state might even be possible with some effort.

  20. UPDATE (31 Jan) now fixed: Possible bug: On some maps with some configurations, some consistency-checking code is occasionally detecting a situation when an "improved" solution ends up worse (with a higher cost). I'm a bit confused: Although there might be some problem with the remainingCost() heuristic, any cost increase should be detected and avoided at the subsolution level before it gets to the overall solution. Maybe I'll have time to track this down before the end of the contest.

  21. Weaknesses of subsolution optimization strategy:

Sample Solutions

Run on a 2.6 GHz P4 with 1GB ram. The optimal solutions for map.txt had approximately 1GB memory footprint. The memory usage for "improved rough" runs increase and decrease a lot during a run, but seemed to max out at about 300MB at times.

Except where otherwise noted, all solutions were generated using the 24 Jan version of the program.

map-step-rough

map-optStep

map-optFuel

map-optStepWall

map-optFuelWall

map-step-35

map-fuel-35

map-fuel-fix40

big-step-30

big-fuel-27

big2-step-27

big2-fuel-fix35

big2-fuel-27

random-step-30

random-fuel-30

random2-step-27

random2-fuel-27

small-step-12

map-step-8

small-fuel-12

map-fuel-8

On A 200 MHz PPro with 64MB ram

map-step-16

map-fuel-16

Recent Changes

Last modified: Wed Jan 26 21:16:33 MST 2005 HERE