WNCG Seminar: Ant Navigation and When to Follow GPS Directions

Friday, April 05, 2019
11:00am - 12:00pm
EER 1.516 (North Tower)

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.


Professor of Operation Research
The University of Warwick

Prof. Steve Alpern joined the ORMS group at Warwick Business School after a long stay at the London School of Economics, where he was Professor of Mathematics and Operational Research. Alpern grew up and completed his education in the United States, where he received the AB at Princeton (Senior Thesis written with Oskar Morgenstern) and the PhD at the Courant Institute-NYU (thesis on dynamical systems, under Peter Lax). Before crossing the Atlantic, he taught at NYU, UCLA, Bryn Mawr and Yale.

Alpern did much of his early work in the area of ergodic theory and dynamical systems, working with J. Oxtoby, S. Kakutani and V. Prasad. Current research interests are in the Operational Research areas of game theory, search theory (particularly rendezvous search, which he first proposed in 1976) and decentralized matching theory. Lately Alpern has been applying theoretical results in search theory to animal behaviour (predator search for prey, 'pilferer' search for cached nuts). He has recently become interested in problems of group decision making, including jury voting and committees.