WNCG Seminar: Ant Navigation and When to Follow GPS Directions
The following problem arose from the work of Fonio et al, a group of ecologists and computer scientists, who tried to understand the behaviour of longhorn crazy ants (Paratrechina longicomis) in navigating back to their nest after gathering food. Single ants were demonstrated to be laying pheromone ‘pointers’ to be followed by groups of ants carrying large loads. Sometimes the pointers are wrong. This leads to an optimization problem on networks with a destination node (the nest). A GPS or other system selects a direction (pointer) to the nest at every node. This will be the same direction every time the node is reached. These directions are correct with a known probability p. If followed all the time this might lead to an infinite loop starting at some node with wrong pointing direction. The problem is to choose a ‘trust probability’ q (as a function of p) with which to choose the pointer direction, in order to minimize the expected time to reach the destination node. If the pointer direction is not chosen, a random edge is chosen to leave the node. We show how to attack this problem in several ways.