Making decisions through collective behaviour
What does it mean to be an effective problem solver? In humans we discuss concepts such as rationality, anticipatory planning, optimization, and decision-making. These concepts are not, however, limited to humans, or even to vertebrates. Organisms that evolved long before us also have a basic ability to solve problems. In an HFSP-funded project, David Sumpter (Sweden), Madeleine Beekman (Australia), Martin Middendorf (Germany) and Toshiyuki Nakagaki (Japan) have addressed the issue of problem solving by examining the way in which different organisms make navigational decisions when searching for food.
About the author: David Sumpter is Professor of Applied Mathematics in the Department of Mathematics at Uppsala University, Sweden. After his PhD in Mathematics at Manchester University, he did postdoctoral research at Oxford before moving to Umea, Sweden. After a further 3 years at the University of Oxford he moved to Uppsala in 2007.
With Google maps and an iPhone, finding the shortest path between two cities is not such a difficult problem. You trace your way along the roads shown on the screen until you get from A to B. The problem becomes harder if you want to know the fastest path. Each road has a different speed limit and back country roads can be slow. Google maps can still solve this problem quickly. Indeed, any first year university computer science student is familiar with Dijkstra's algorithm, a fast and efficient algorithm for finding shortest paths.
Consider, however, what you would do if you were dropped at an unknown point in the middle of an endless night somewhere in the USA and asked to find the shortest path between New York and LA. In this scenario, you are not alone. You know that scattered across America there are many other people who are trying to solve the same problem. Now and again you see one of them pass in a particular direction sometimes leaving behind a dirt trail as they follow the path left by others. Could you find your way home now?
This is one of the problems faced by an ant in an ant colony. Actually, it is a problem faced by the colony as a whole. The question is how a large number of individuals, each with limited navigational ability, build a short connecting path between food and the nest. The problem is even harder than this: there are many food sources and many nests, which should all be connected; the food sources are of different qualities and contain different nutrients; the food sources and nests change positions through time; and the landscape changes too as new mountains and valleys appear and disappear.
Our HFSP-funded research project has investigated exactly these questions in our model species. In ants, we have investigated the extensive networks they build to connect a central nest to multiple food sources and how different nests are connected together. These transport networks are marked out by pheromones or as physically cleared paths on the forest floor. The paths in the network that provide quick passage from A to B are reinforced as ants travel along them and unnecessary paths are allowed to fall in disrepair until they are no longer used. The networks resulting from this coupling between positive and negative feedback processes provide direct routes between points of interest while requiring low maintenance.
Single cellular slime moulds are very different from ants but the way they solve problems is remarkably similar. The slime mould Physarum polycephalum consists of a network of tubes which shuttle nutrient around. Like ant trails, tubes are the result of positive feedback. When flow is large enough the tube thickens, while unused tubes thin out. Through this process the slime mould is able to build a network that efficiently connects large numbers of food sources. To exemplify this we challenged the slime mould to build a network connecting the suburbs in a food-map of Tokyo (see YouTube video below: Credit: Dr. Seiji Takagi, Hokkaido University). The slime mould spreads out and connects all the food sources; then it contracts to the minimal path between them. We have shown that this same mechanism allows the slime mould to balance its nutrient intake, make rational and sometimes irrational choices and trade-off between speed and accuracy requirements.
One enjoyable aspect of our interdisciplinary collaboration is that we could make realistic comparisons between species. We have challenged ants, honey bees or slime moulds to collect food in an environment where the quality and distribution of food changes through time. We found that different feedback mechanisms allow the species to cope in dynamic environments in different ways. For example, honey bees use a combination of individual memory and dance communication in order for the colony to have a good overall picture of resource distribution. Ants on the other hand use a network of trails to store the same information.
The behaviour of these different species can inspire the way we build computer algorithms. What marks our project out from previous research are two aspects. Firstly, it is the scale and difficulty of the problems we have set for our model species. Secondly, it is the detailed study of the mechanisms involved in problem solving. Together these provide better inspiration for the development of computer algorithms. For example, we have shown that ants use multiple pheromones to track dynamic changes in their environment and then developed an algorithm for tracking noisy signals based on these observations. This is only a beginning. The problem solving of these species consists of many levels of complexity, each of which can be exploited when we develop algorithms for our own human problems.
It is this combination of scientists working from different disciplines---animal and cellular biology, computer science and mathematics---and coming from all over the world which gives our HFSP funded project its spirit and its success. We have learnt a lot from our project and had a lot of fun while doing so.
Members of the grant team met at the Mathematical Biosciences Institute, Ohio, USA in March 2011: top: Audrey Dussatour (Sydney), Madeleine Beekman (Sydney), Chris Reid (Sydney), Boris Granovskiy (Uppsala); bottom: Martin Middendorf (Leipzig), Konrad Diwold (Leipzig), David Sumpter (Uppsala), Kai Ramsch (Leipzig); missing: Tanya Latty (Sydney), Toshi Nakagaki, Atsushi Tero, Kentaro Ito (Hokkaido)
Jerome Buhl, Kerry Hicks and co-workers (2009) The shape and structure of wood ant trails, Behavioural Ecology and Sociobiology.
Audrey Dussutour, Stam Nicolis and co-workers (2009) The role of multiple pheromones in food recruitment by ants, Journal of Experimental Biology.
Atsushi Tero, Seiji Takagi, and co-workers (2010) Rules for biologically inspired adaptive network design, Science.
Tanya Latty & Madeleine Beekman (2010) Irrational decision-making in an amoeboid organism: transitivity and context-dependent preferences, Proceedings of the Royal Society, Series B.
Tanya Latty & Madeleine Beekman (2010) Speed–accuracy trade-offs during foraging decisions in the acellular slime mould Physarum polycephalum, Proceedings of the Royal Society, Series B.
Audrey Dussutour, Tanya Latty, Madeleine Beekman & Stephen Simpson (2010) Amoeboid organism solves complex nutritional challenges, PNAS.
Chris Reid, David Sumpter & Madeleine Beekman (2011) Optimization in a Natural System: Argentine Ants Solve the Towers of Hanoi, Journal of Experimental Biology 214:50-58 doi: 10.1242/jeb.048173
Tanya Latty, Kai Ramsch and co-workers (under revision) Inter-nest trail networks in Argentine ants, Royal Society Interface.