Convergence and rate of convergence of a simple ant model

ABSTRACT

We present a simple ant model that solves a discrete foraging problem. We provide simulations and a convergence analysis. We argue that the ant population computes the solutions of some optimal control problems and converges in some well defined sense. We also discuss the rate of convergence with respect to the number of ants: we give experimental and theoretical arguments that suggest that this rate is superlinear with respect to the number of agents.

REFERENCES

• 1: D. Aldous and J. Fill. Reversible Markov Chains and Random Walks on Graphs. Monograph in preparation, 1996.
• 2: A. Boumaza and B. Scherrer. Convergence and rate of convergence of a simple ant algorithm. Inria technical report 00121341, 2006.
• 3: Liviu Panait , Sean Luke, A Pheromone-Based Utility Model for Collaborative Foraging, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.36-43, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.25]
• 4: O. Simonin. Personal communication.
• 5: Olivier Simonin, Construction of numerical potential fields with reactive agents, Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, July 25-29, 2005, The Netherlands [doi>10.1145/1082473.1082768]
• 6: Richard S. Sutton , Andrew G. Barto, Introduction to Reinforcement Learning, MIT Press, Cambridge, MA, 1998

INDEX TERMS

General Terms:
Algorithms, Theory

Keywords:
agents, emergent behavior, formal models of agency, multiagent planning, multiagent systems