Ants can Optimally solve the Towers of Hanoi

...which is good for the ants, because I'm terrible at it.  This paper was recently published in The Journal of Experimental Biology (link).  Of course, the ants weren't actually moving the disks around a bunch of pegs.  Instead, they created a maze based on the various paths one can take in the game.  Junctions of the maze represent game states.  Edges to other junctions represent the possible legal actions one can perform from the given state. 

There is a single start location and a single end location, at opposite ends of the maze.  They correlate to the starting states in the Towers of Hanoi puzzle.  Note that the maze they used actually just glues two expanded game mazes together, hence why the start and end locations are technically the same.  Thematically, the ants must first play a classical game.  Once they arrive at the solution (at the middle of the board), they must then play a separate game from its solution back to its beginning (correlating to the other half of the maze; they don't ever have to go backwards in the maze). 

The simple, one sentence version is that they created a large maze in which the optimal paths were already known.  During experiments, they would place food at one end of the maze, and ants at the opposite end of the maze.  They then tracked the movement of ants through the maze over time.

Many paths to the food were initially found.  However, over time, the ants would prune the paths they took.  In the overwhelming majority of cases, they found that the ants would end up using only a single, optimal path.  Additionally, if this path was then blocked mid-experiment, the ants were able to find the new optimal path an overwhelming majority of the time.  So the ants could find the best path both statically and dynamically.  As an aside, larger colonies were more capable in finding the optimal path than small ones, as was the case for ants that had been allowed to explore the maze without the presence of food.

There are a number of practical uses for this style of behavior.  These ants were able to solve the shortest path problem using only pheromones deposited by other ants.  There was no central guiding intelligence, but "swarm" intelligence (as pointed out by the authors).  This translates well to communication seen between computers on the Internet.  Routing algorithms must find the shortest path between systems without a central intelligence.  Ideally, only a minimal amount of information is communicated to other systems in this process.  The ants do this, only millions of years before the computer.

The paper points out Ant Colony Optimization (ACO) as an algorithm that exploits this behavior.  However, this algorithm is designed to work on static instances of problems, not on dynamically changing problems as in the shortest path experiment set up in this paper.  Essentially, algorithms that already model themselves on ant behavior are not exploiting everything they could exploit. 

With the findings of this paper, there seems to be enough information about actual ant behavior to design a new, dynamic algorithm, perhaps for routing.  Who knows?  Perhaps the minimal spanning trees (MST) of today will give way to digital ants of tomorrow.  As it is, the current "dynamic" MST algorithms used in routing typically just routinely resolve static instances of MST problems.  They resolve fast enough so that it appears mostly dynamic, although it's not truly dynamic.  The ants have the advantage of being truly dynamic.  If not routing, then there must be some practical application that can use this behavior.  It just seems to have too many interesting properties to not somehow be useful to someone.