Planeamento de redes e rotas - aprender com as formigas


23 Jan 2007
Achei estes artigos interessantes, estudar as formigas para desenvolver melhores algoritmos de planeamento de redes e rotas mais curtas ou eficientes entre pontos de redes complexas.

Next generation of algorithms inspired by problem-solving ants
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.

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 computer scientists 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 ant colonies 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 Social Insects 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 problem-solving software and hence more efficiency for human industries."

Supercolony trails follow mathematical Steiner tree
An interdisciplinary study of ant colonies that live in several, connected nests has revealed a natural tendency toward networks that require the minimum amount of trail.

Researchers studied ‘supercolonies’ of Argentine ants with 500, 1000 or 2000 workers to identify methods for self-organising sensors, robots, computers, and autonomous cars.

They put three or four nests of ants in empty, one-metre-wide circular arenas to observe how they went about connecting the nests.

As with railway networks, directly connecting each nest to every other nest would allow individual ants to travel most efficiently, but required a large amount of trail to be established.

Instead, the ants used central hubs in their networks – an arguably complex design for creatures that University of Sydney biologist Tanya Latty described as having “tiny brains and simple behaviours”.

“We found that ants almost always made networks that minimised the total amount of trail, consistent with optimisation at a colony level, rather than at an individual level,” Latty told iTnews.

“In many cases, they did a remarkable job of making networks that looked almost exactly like the mathematical shortest path, called a ‘Steiner tree’.”

Argentine ants form trails by tapping the ground with their abdomens to leave behind trails of pheromones that attract other ants.

Because pheromones evaporate over time, trails have a “maintenance cost” of worker ants that continuously march along the trail to lay down pheromones.

Kai Ramsch and Martin Middendorf of the University of Leipzig’s Parallel Computing and Complex Systems Group hoped to apply the ants’ networking methods to organic computing systems.

“Clearly, in order to work together the components of an organic computing system need to be connected,” said Ramsch and Middendorf, who collaborated with Latty for the study.

“Hence, a central question is: How can many components be connected by a network that is formed by the components themselves in a self-organized way?”

In a separate study of Argentine ants last year, University of Sydney biologist Chris Reid speculated that ants and their pheromones could be modelled by data packets that left behind a line of code that expired after a set period of time.

The German computer scientists noted that the digital “evaporation rate” of artificial pheromones would be varied according to speed, distance, number of information packets and network structure of a computer network.

“It is necessary to change the evaporation rate for the artificial pheromones so that they fit to application,” they told iTnews in an e-mail exchange. “This can be simulated with our models.”

A network in four hours

The team found that ant colonies completed the majority of network formation within their first two hours in the arena.

Each experiment lasted a total of six hours, although very few topological changes were observed after four hours.

Latty said she initially suspected that the ants were building low-maintenance networks because they had too few resources to directly connect each nest.

That theory was deemed unlikely, when the researchers found larger supercolonies dedicated their additional resources to building paths that essentially improved the robustness of the network.

The researchers hoped that their study of ant colonies would also yield “self-healing” organic computing networks, since nodes were controlled individually and not by a central control unit.