A probabilistic movement model for shortest path formation in virtual ant-like agents

ABSTRACT

We propose a probabilistic movement model for controlling ant-like agents foraging between two points. Such agents are all identical, simple, autonomous and can only communicate indirectly through the environment. These agents secrete two types of pheromone, one to mark trails towards the goal and another to mark trails back to the starting point. Three pheromone perception strategies are proposed (Strategy A, B and C). Agents that use strategy A perceive the desirability of a neighbouring location as the difference between levels of attractive and repulsive pheromone in that location. With strategy B, agents perceive the desirability of a location as the quotient of levels of attractive and repulsive pheromone. Agents using strategy C determine the product of the levels of attractive pheromone with the complement of levels of repulsive pheromone. We conduct experiments to confirm directionality as emergent property of trails formed by agents that use each strategy. In addition, we compare path formation speed and the quality of the formed path under changes in the environment. We also investigate each strategy's robustness in environments that contain obstacles. Finally, we investigate how adaptive each strategy is when obstacles are eventually removed from the scene and find that the best strategy of these three is strategy A. Such a strategy provides useful guidelines to researchers in further applications of swarm intelligence metaphors for complex problem solving.

REFERENCES

• 1: Adriano Cavalcanti, Tad Hogg, Bijan Shirinzadeh, and Hwee C. Liaw. Nanorobot communication techniques: A comprehensive tutorial. In IEEE ICARCV 2006 International Conference on Control, Automation, Robotics and Vision, 2006.
• 2: Andrew Colin. Ant colony algorithms: Solving optimization problems. In Dr. Dobb's Journal (www.ddj.com/dept/ai/191800178?pgno=1), 2006.
• 3: Marco Dorigo, Mauro Birattari, and Thomas Stutzle. Ant colony optimization: Artificial ants as a computational intelligence technique. Technical report, Universite Libre de Bruxelles, BELGIUM, 2006.
• 4: Marco Dorigo , Gianni Di Caro , Luca M. Gambardella, Ant algorithms for discrete optimization, Artificial Life, v.5 n.2, p.137-172, April 1999 [doi>10.1162/106454699568728]
• 5: Duncan E. Jackson, Mike Holcombe, and Francis L. W. Ratnieks. Trail geometry gives polarity to ants foraging networks. In Nature. Nature Publishing Group, 2004.
• 6: Kurumatani Koichi and Nakamura Mari. Generating qualitative equations about macro behaviours of foraging in ant colony. In Proceedings of the German Conference on Bioinformatics, GCB'96 (Leipzig), pages 142--147, 1996.
• 7: Daniel Merkle, Martin Middendorf, and Alexander Scheidler. Modeling ant brood tending patterns with cellular automata. In Proceedings of the Workshop on Modelling of Complex Systems by Cellular Automata, volume 2.2, pages 412--419, 2005.
• 8: Daniel Merkle, Martin Middendorf, and Alexander Scheidler. Modeling ant brood tending patterns with cellular automata. Journal of Cellular Automata, 2.2:183--194, 2006.
• 9: Yoshiyuki Nakamichi and Takaya Arita. An evolutionary simulation of the origin of pheromone communication. In Proceedings of MPS Symposium 2004 on Complex System Science and its Application, 2004.
• 10: 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]
• 11: Liviu A. Panait and Sean Luke. Ant foraging revisited. In Proceedings of the Ninth International Conference on the Simulation and Synthesis of Living Systems (ALIFE9), 2004.
• 12: Liviu A. Panait and Sean Luke. Learning ant foraging behaviors. In Proceedings of the Ninth International Conference on the Simulation and Synthesis of Living Systems (ALIFE9), 2004.
• 13: Steffen Priesterjahn, Andreas Goebels, and Alexander Weimer. Stigmergetic communication for cooperative agent routing in virtual environments. In Proceedings of the International Conference on Artificial Intelligence and the Simulation of Behaviour, 2005.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.2 Graphics Systems

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.6 Methodology and Techniques
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development

Keywords:
directionality, dissipation, emergent behaviour, quality, recruitment, search and return pheromone, speed