Perverse: An ICFP 2002 Programming Contest Entry

Design

Perverse is a fairly straightforward three-state machine:

• Going Home: out of packages to deliver, go home to pick more up. This is of course the starting state.
• Delivering: the robot has packages in its inventory, and is delivering them.
• Searching: there are no packages at Home, and none in inventory. But the game isn't over, so wander about.

In a map with more than one Home Base, the Searching state should never occur. This leads me to a list of known weaknesses:

• doesn't keep track of how many packages are at each Base; (this means that in a two-base world, it could shuttle back and forth all day);
• when in Searching, it doesn't check the list of dropped packages. It actually does maintain an extent of packages, and records the coordinates whenever known (for instance, if a robot at X,Y drops package foo). It just doesn't use this knowledge - the most inexcusable (i.e. easily fixed) shortcoming.
• blind to other robots (so even an opportunistic shove is not attempted).
• bidding is very simplistic

Balancing that, a few things I'm happy about:

• The pathfinding is good! If there are no stupid bugs, then it will always find the optimal path to a given destination. If no path is found, the destination is no longer considered (we'll find a backup or change state if there are no backups).
• Paths are always cached. So, even though the CPU usage on a large map could be high, it is amortized over the length of the path.
• If at any time, the robot finds itself off the path (i.e. it was pushed), it will always calculate a new path. This may or may not be the same as the old path.
• Package selection: packages are sorted according to a simple heuristic that takes weight (good) and Manhattan distance (bad) into account. Optimal package selection is variant of the Backpack problem, which I seem to recall is NP-complete. So we just take packages until we run out of room.
• A simple heuristic tends to keep the robot away from water when convenient, in case any psychopath robots are lurking nearby.

Other things...

The A* search algorithm wants a quirky data structure. A priority queue is desirable for finding the lowest-cost Open node. However, you also frequently search the Open list for a given node in order to compare a new g() value with the best g() found so far for that node. Essentially, we want a sequence which is uniquely keyed in one dimension (by node id) but sorted in another dimension (by node cost g()).

On the surface, a std::Map seems perfect for this, but I was unable to get it to do what I wanted. I now suspect that Map is not in fact the right mechanism - he and I seem to disagree on the meaning of "key".

In the end, I wound up using a heap to manage the Open list. Since only one A* search could be going on at a time, I could store node costs directly in the World data structure. This is precisely the kind of thing that gives me the heebie-jeebies, but at least it's fast.

Mechanics, or "How I spent my long weekend"

I hadn't planned on entering this year. Friday afternoon I changed my mind; wrapped up what I was working on and finally set to work about midnight. The time breakdown was approximately:

• 12 hours not working on the contest;
• 36 hours coding;
• 18 hours sleeping;
• 6 hours doing other things (eating, playing Chu Chu Rocket, etc.)

The submission is written in C++, which is entirely masochistic (and leads to the name of the entry: this was truly a perverse way to enter the contest). I haven't done any serious development in C++ in about 3.5 years... and of course the landscape has changed in that time. For example, the STL is more powerful than I recall, but also more inscrutable.

Of course, re-learning a programming language on the fly is not a winning strategy. As it is, I spent far too much time getting basic infrastructure working and fighting with the STL (see std::Map above).

Conclusions

C++ is not an efficient way to compete in a contest such as this. My own clumsiness exacerbates the situation to the point that more time was spent on infrastructure than solving the core problem (again, see the contest entry name).

Despite this, it was a fun weekend, and I think that Perverse is competitive. The things it does, it does fairly well; I just wish I had time to make it do more things.

The submission tarball: perverse.tgz

- Jon Pile, Team Eikkel