Ant-Colony Algorithms

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

This is a public forum. CMP Media and its affiliates are not responsible for and do not control what is posted herein. CMP Media makes no warranties or guarantees concerning any advice dispensed by its staff members or readers.

Community standards in this comment area do not permit hate language, excessive profanity, or other patently offensive language. Please be aware that all information posted to this comment area becomes the property of CMP Media LLC and may be edited and republished in print or electronic format as outlined in CMP Media's Terms of Service.

Important Note: This comment area is NOT intended for commercial messages or solicitations of business.