A MILLION MONKEYS

A Blog about AI, UI and HI

August 2006

Andrew Colin's article, Ant-Colony Algorithms is a great introduction to swarm-based autonomous computing. Andrew presents the basics, constraints, rules and working code for using (in this case, simulated) swarms of simple autonomous 'ants' to find good solutions to historically-intractible AI problems (e.g., Traveling Salesman).

To me, the most stunning insight offered by Andrew's paper is the notion -- drawn directly from nature -- that artificial ants should have the ability to lay down a 'pheromone' trail, effectively inscribing the environment they share with other swarmbots, and that their main perceptual characteristic is the ability to sense and compare pheromone concentrations on a route. This ability, in effect, to use the environment itself as shared memory lets swarmbots cooperate without resort to a separate, reliable communication plane (e.g., radio, infrared) and with significantly reduced remote sensory capacity (i.e., vision). Colin doesn't suggest what sort of technology might be used for implementing artificial pheromone deposit and sensing in the real world, but enormous strides are now being made in just this area (partly driven by bioinformatics and medicine, partly by nanotechnology, and partly by the exigencies of homeland security). For example, here's an article on laser-based solid-state molecular sensing (perhaps too high-power a strategy for use in robotic ants, and here's another about using engineered arrays of carbon nanotubes to do the same kind of trick. Apparently, if you engineer your nanotubes just right, their resistance varies in the presence of your target molecule.

Colin's simulation, meanwhile, is a real high performer. He's set it up to run against a 50-city standard test-case benchmark (EILON50), and his ants apparently converge to within a few percentage points of the best solution known, within 100 passes over the training set. Go ants!

Posted by John Jainschigg at 11:12 AM  Permalink |