Next generation of algorithms inspired by problem-solving ants

Dec 10, 2010
The ants were able to find the shortest route from one end of the maze to the other in under an hour, then were able to adapt and find the second shortest route when obstacles were put in their path.

(PhysOrg.com) -- An ant colony is the last place you'd expect to find a maths whiz, but University of Sydney researchers have shown that the humble ant is capable of solving difficult mathematical problems.

These findings, published in the Journal of Experimental Biology, deepen our understanding of how even simple animals can overcome complex and dynamic problems in nature, and will help develop even better software to solve logistical problems and maximise efficiency in many human industries.

Using a novel technique, Chris Reid and Associate Professor Madeleine Beekman from the School of Biological Sciences, working with Professor David Sumpter of Uppsala University, Sweden, tested whether Argentine ants (Linepithema humile) could solve a dynamic optimisation problem by converting the classic Towers of Hanoi maths puzzle into a maze.

Finding the most efficient path through a busy network is a common challenge faced by delivery drivers, telephone routers and engineers. To solve these optimisation problems using software, computer scientists have often sought inspiration from in nature - creating algorithms that simulate the behaviour of ants who find the most efficient routes from their nests to food sources by following each other's volatile pheromone trails. The most widely used of these ant-inspired algorithms is known as Ant Colony Optimisation (ACO).

"Although inspired by nature, these computer algorithms often do not represent the real world because they are static and designed to solve a single, unchanging problem," says lead author Chris Reid, a doctoral student from the Behaviour and Genetics of Laboratory.

"But nature is full of unpredictability and one solution does not fit all. So we turned to ants to see how well their problem solving skills respond to change. Are they fixed to a single solution or can they adapt?"

The researchers tested the ants using the three-rod, three-disk version of the Towers of Hanoi problem - a toy puzzle that requires players to move disks between rods while obeying certain rules and using the fewest possible moves. But since ants cannot move disks, the researchers converted the puzzle into a maze where the shortest path corresponds to the solution with fewest moves in the toy puzzle. The ants at the entry point of the maze could chose between 32,768 possible paths to get to the food source on the other side, with only two of the paths being the shortest path and thus the optimal solution.

The ants were given one hour to solve the maze by creating a high traffic path between their nest and the food source, after which time the researchers blocked off paths and opened up new areas of the maze to test the ants' dynamic problem solving ability.

After an hour, the ants solved the Towers of Hanoi by finding the shortest path around the edge of the maze. But when that path was blocked off, the ants responded first by curving their original path around the obstacle and establishing a longer, suboptimal, route. But after a further hour, the ants had successfully resolved the maze by abandoning their suboptimal route and establishing a path that traversed through the centre of the maze on the new optimal route.

But not all the colonies' problem solving skills were equal: ants that were allowed to explore the maze without food for an hour prior to the test made fewer mistakes and were faster at resolving the maze compared to the ants that were naive. This result suggests that the "exploratory pheromone" laid down by ants searching a new territory is key in helping them adapt to changing conditions.

"Even simple mass-recruiting ants have much more complex and labile problem solving skills than we ever thought. Contrary to previous belief, the pheromone system of ants does not mean they get stuck in a particular path and can't adapt. Having at least two separate pheromones gives them much more flexibility and helps them to find good solutions in a changing environment. Discovering how ants are able to solve dynamic problems can provide new inspiration for optimisation algorithms, which in turn can lead to better software and hence more efficiency for human industries."

Explore further: Science casts light on sex in the orchard

Provided by University of Sydney

3.7 /5 (27 votes)

Related Stories

Desert ants smell their way home

Feb 27, 2009

Humans lost in the desert are well known for going around in circles, prompting scientists to ask how desert creatures find their way around without landmarks for guidance. Now research published in BioMed ...

Recommended for you

Science casts light on sex in the orchard

15 hours ago

Persimmons are among the small club of plants with separate sexes—individual trees are either male or female. Now scientists at the University of California, Davis, and Kyoto University in Japan have discovered ...

Four new dragon millipedes found in China

17 hours ago

A team of speleobiologists from the South China Agriculture University and the Russian Academy of Sciences have described four new species of the dragon millipedes from southern China, two of which seem to ...

Scientist creates automatic birdsong recognition app

20 hours ago

Dr Dan Stowell, an EPSRC Research Fellow in QMUL's School of Electrical Engineering and Computer Science, has used a grant from Queen Mary Innovation to develop a prototype for an app that turns his research ...

New research reveals fish are smarter than we thought

21 hours ago

(Phys.org) —A new study from researchers in our Department of Psychology with colleagues at Queen Mary University of London has reported the first evidence that fish are able to process multiple objects ...

User comments : 11

Adjust slider to filter visible comments by rank

Display comments: newest first

KBK
5 / 5 (1) Dec 10, 2010
The interesting thing here is the 'secondary explore state' (seeming second pheromone state) found by the mathematicians.
KBK
3 / 5 (2) Dec 10, 2010
Also, just for the heck of it, apply this emergent model to weather chaos theory modeling..and see what comes of it.

Just a random thought. It could lead somewhere. It might need a bit of adapting but maybe a two state model is the way to go.
thales
5 / 5 (2) Dec 10, 2010
They've done research on bees as well - how they solve the so-called "traveling salesman" problem. Fascinating stuff.
A_Paradox
5 / 5 (2) Dec 10, 2010
Yeah, I've spent a lot of time trying to control the ants around our garden; they are nothing if not incredibly persistent and very resilient. But if I don't keep attacking their colonies and out-stations, they take over the place and diligently undermine paving stones and concrete slabs, as well as making it impossible to stand in the driveway.

I suspect they have at least half a dozen tracking pheromones: possibly one for each type of main expedition they go on. EG, defensive patrol and nest maintenance, foraging patrol, egg or baby transport, and other journey types. They very probably secrete combinations of pheromones when traveling, based on the relative priorities of the various corporate needs of the moment.

One thing is clear: the pathways ants evolve over the "hour"or so the authors talk of embody the path of least resistance between two nest sites, not simply the shortest linear pathway.
HaveYouConsidered
not rated yet Dec 10, 2010
A Paradox,

As for the long term control of ants, a little boric acid powder dissolved in hot water and sprayed around the perimeter of your paths and structures does wonders and is dirt cheap.

Mixed with a bit of automobile antifreeze and sprayed sparingly on exterior wood surfaces, it also eliminates termites and wood rot, without hiring expensive knuckleheads who use stuff that doesn't last a week.
Quantum_Conundrum
not rated yet Dec 10, 2010
Mixed with a bit of automobile antifreeze and sprayed sparingly on exterior wood surfaces, it also eliminates termites and wood rot, without hiring expensive knuckleheads who use stuff that doesn't last a week.


Sure, if you want to kill your pets too while you're at it...
ThanderMAX
3 / 5 (2) Dec 11, 2010
Not at all a new algorithm,"Ant colony optimization" is already backdated algorithm (from mid 1990 era) ... its part of biological inspired evolutionary algorithms - such as genetic algorithm, memetic algorithm...

Few of the really new algorithms in these regard : Artificial Bee Colony Algorithm (proposed in 2005), Gravitational search algorithm etc...
Husky
not rated yet Dec 11, 2010
i would think the compositions and ratio of pheromones secreted by ants be influenced by available and newly acquired energy of the ant and stresshormones, this would allow other ants to sniff out that while one route may be shorter to food linearly , it contains more stress pheromone, harder work. Anyway it would be nice if you'd have some kind of general purpose spreadsheet model in Excel that helps you to compile/map a problem as an antroute chart and the ants will crawl through the worksheet cells, testing its values, upon wich they crawl to the next cell, meanwhile leaving for instance a colorcode property of the cell as pheromone, to make it more visible to observer what and how trends are developing in the system. the working of multiple pheromones could be made visualised by stacking worksheets and assign each slice its own pheromone colour and decision rules
epoch
not rated yet Dec 12, 2010
studies of group behavior is very interesting. one cannot be certain what mechanisms are at play.
one example showed a robot in an arena where a nnumber of balls were scattered. a number of robots (i believe it was something like a dozen) where deployed in the arena. those robots had a "pusher" in the front (like a shovel of sort). the robot behavior was programmed to be "keep going forward, turn when you hit a wall, backup and then turn if you have 3 balls in the "pusher". turned out that the secondary side effect of that behavior was to collect and push all the balls back together, and maintaining it that way.

we know that the ants use the pheromones to identify "already used paths". it could be that simply the ants mark paths as they use them, putting weights to each "path". the ants simply confirm or invalidate those (as the environment changes). that is how network routers do their job. check weights and advertise to neighbors.
how they establish the path would be interesting...
thinkyhead
5 / 5 (1) Dec 13, 2010
I'd be curious to see who's smarter - ants or slime molds. But seriously, it should surprise no one that even the simplest living organisms possess incredible problem-solving abilities. After all, problems to solve wouldn't even exist if not for life. (Since non-living things have no needs, therefore no problems.) You might even say life is "problem-solving incarnate." Every lowly amoeboid has startling insights into issues we lumbering oafs can barely conceive.
A_Paradox
not rated yet Dec 25, 2010
Husky & epoch

My understanding is that however many the pheromones are, a key factor in ant ecology is the speed at which the pheromones evaporate or become chemically altered by the environment. The rate of dissipation of the pheromone is what allows the build up of useful information about a pathway. There is _no_ pathway to start with, just widely spread and basically random traces left by foragers and scouts. Over time, useful destinations become the focus points of ever fresher pheromone markings and the spread of relatively fresher markings from individual ants narrows to the most energetically efficient pathway between such currently useful places. With no 'thought' involved, just detection, discrimination, then selection based on current priority.

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.