As long as there are only a few points en route to travel along, humans can rather easily find the optimal way using computational procedures. But the more points there are to consider, the more complicated it becomes. Just think back to Odysseus as he was sailing the Mediterranean Seas from Troy to Ithaca. Legend has it that he passed by 16 islands. It requires the comparison of billions of different routes to find the shortest connecting way within the network of 16 islands.
Finding your way through the chaos
Let’s take a look at how nature and more specifically ants solve this logistical challenge.
A little ant seems determined when walking from one corner to the other, yet an anthill gives a chaotic impression. How do these small active animals find their way in the lively bustle?
The individual ant is not particularly smart. Its brain has a limited capacity with a memory span that is about 10 seconds. It is more about the ants’ communication and coordination with other ant members of their colony. Their doings inspire logisticians in how to optimize supply chains using the ant’s approach of navigating the optimal path between food source and nest. Delivery drivers, telephone routers, and engineers share the common challenge of finding the most efficient route in connecting a high number of points in an often-busy network.
Ants cooperate in a complex decentralized state in which each ant takes its own decisions while staying in active exchange with fellow ants at the same time. Each ant colony has scouts which examine the environment around the nest and leave scents to mark the route they took. The one scout who finds the shortest way to the food source is the first one to return to the group. The others notice the first arrival, and it is evident for them to follow its route to the food. They do so by using the first ant’s scent for orientation.
But what happens if obstacles occur on the way and an alternative route is required? Computer algorithms often do not account for the unpredictability of the real world since they are designed to analyze static arrangements. For that matter and to assess the ants’ approach further, researchers at the University of Uppsala in Sweden tested the ants’ ability to solve a dynamic optimization problem by converting the classic Tower of Hanoi into a maze. The ants could choose between over 30.000 paths to get to the food source.
But what happens if obstacles occur on the way and an alternative route is required? Computer algorithms often do not account for the unpredictability of the real world since they are designed to analyze static arrangements. For that matter and to assess the ants’ approach further, researchers at the University of Uppsala in Sweden tested the ants’ ability to solve a dynamic optimization problem by converting the classic Tower of Hanoi into a maze. The ants could choose between over 30.000 paths to get to the food source.
They heavily populated the maze and found in only one hour the shortest route. Then, the researchers blocked off some paths and opened new areas to test the ants’ dynamic problem-solving ability. At first, they did what you might have observed as a child when placing a stone in front of an ant trail, curious to see their reaction. The ants start curving the previous optimal path moving around the obstacle.
In the research experiment, the ants needed only one hour to figure out that another path turned into the shortest one. Broken down timewise, this means the ants spent merely one-tenth of a second per path and per decision. These incredible techniques of adaptation can provide further insights into developing problem-solving software to help industries to adapt to changing environments.
Let’s think back to Odysseus. He would have probably reached the port of Ithaka much earlier had he had the opportunity to consult with an ant swarm. Today’s computer simulations use the ant scout approach and the “ant colony optimization algorithm (ACO)” that can find optimal routes in the shortest time. What Odysseus was not able to do, modern computer simulations using virtual ant scout software can solve quickly.
Research article + pictures source: http://jeb.biologists.org/content/jexbio/214/1/50.full.pdf
