Stigmergic landmark foraging

ABSTRACT

In this paper, we describe a nature-inspired optimization algorithm based on bee foraging behavior. This algorithm combines the high performance of bee path-integration navigation with ant-like stigmergic behavior in the form of landmarks. More precisely, each individual landmark can be created at any walkable state in the environment and contains a collection of direction markers with which visiting agents can find their way in an unknown environment. A landmark can either be represented by an agent or any other information distributing object (e.g., a RFID). Essentially, we implement ant recruitment behavior based on pheromone. However, instead of using attracting or repelling pheromone in every state of the environment, we only update directional information at key locations in the environment. The resulting algorithm, which we call Stigmergic Landmark Foraging (SLF), proves to be very efficient in terms of building and adapting solutions.

REFERENCES

• 1: Dídac Busquets , Carles Sierra , Ramon López De Màntaras, A Multiagent Approach to Qualitative Landmark-Based Navigation, Autonomous Robots, v.15 n.2, p.129-154, September 2003 [doi>10.1023/A:1025536924463]
• 2: B. Cartwright and T. Collett. Landmark learning in bees. Journal of Comparative Physiology A, 151:521--543, 1983.
• 3: K. Cheng, T. Collett, A. Pickhard, and R. Wehner. The use of visual landmarks by honeybees: bees weight landmarks according to their distance from the goal. Journal of Comparative Physiology A, 161:469--475, 1987.
• 4: L. Chittka and J. Kunze. The significance of landmarks for path integration in homing honeybee foragers. Naturwissenschaften, 82:341--343, 1995.
• 5: M. Collett, T. Collett, S. Bisch, and R. Wehner. Local and global vectors in desert ant navigation. Nature, 394:269--272, 1998.
• 6: M. Collett, D. Harland, and T. S. Collett. The use of landmarks and panoramic context in the performance of local vectors by navigating honeybees. Journal of Experimental Biology, 205:807--814, 2002.
• 7: T. Collett. Insect navigation en route to the goal: multiple strategies for the use of landmarks. Journal of Experimental Biology, 199:227--235, 1996.
• 8: T. Collett, E. Dillmann, A. Ciger, and R. Wehner. Visual landmarks and route following in desert ants. Journal of Comparative Physiology A, 170:435--442, 1992.
• 9: T. S. Collett and M. Collett. Memory use in insect visual navigation. Nature, 3:542--552, 2002.
• 10: J. Deneubourg, S. Aron, S. Goss, and J. Pasteels. The self-organizing exploratory pattern of the Argentine ant. Journal of Insect Behaviour, 3:159--168, 1990.
• 11: Marco Dorigo , Thomas Stützle, Ant Colony Optimization, Bradford Book, 2004
• 12: Matthias O. Franz , Bernhard Schölkopf , Hanspeter A. Mallot , Heinrich H. Bülthoff, Learning View Graphs for Robot Navigation, Autonomous Robots, v.5 n.1, p.111-125, March 1998 [doi>10.1023/A:1008821210922]
• 13: M. O. Franz, B. Schölkopf, H. A. Mallot, and H. H. Bülthoff. Where did i take that snapshot? scene-based homing by image matching. Biological Cybernetics, 79:191--202, 1998.
• 14: P. Gaussier, C. Joulain, J. Banquet, S. Leprêtre, and A. Revel. The visual homing problem: An example of robotics/biology cross fertilization. Robotics and Autonomous Systems, 30:155--180, 2000.
• 15: D. Lambrinos, R. Möller, T. Labhart, R. Pfeifer, and R. Wehner. A mobile robot employing insect strategies for navigation. Robotics and Autonomous Systems, 30(1--2):39--64, 2000.
• 16: N. Lemmens, S. de Jong, K. Tuyls, and A. Nowé. Bee system with inhibition pheromones. In European Conference on Complex Systems (ECCS), 2007.
• 17: N. Lemmens, S. de Jong, K. Tuyls, and A. Nowé. Bee behaviour in multi-agent systems: a bee foraging algorithm. Lecture Notes in Artificial Intelligence: Adaptive Agents and MAS III, LNAI 4865:145--156, 2008.
• 18: N. Lemmens and K. Tuyls. Stigmergic landmarks lead the way. In The 20th Belgian-Dutch Conference on Artificial Intelligence (BNAIC), 2008.
• 19: R. Menzel, K. Geiger, L. Chittka, J. Joerges, J. Kunze, and U. Müller. The knowledge base of bee navigation. Journal of Experimental Biology, 199:141--146, 1996.
• 20: R. Möller. Insect visual homing strategies in a robot with analog processing. Biological Cybernetics, 83:231--243, 2000.
• 21: M. Müller and R. Wehner. Path integration in desert ants, Cataglyphis Fortis. Proceedings of the National Academy of Sciences, 85(14):5287--5290, 1988.
• 22: Carl Owen , Ulrich Nehmzow, Landmark-based navigation for a mobile robot, Proceedings of the fifth international conference on simulation of adaptive behavior on From animals to animats 5, p.240-245, September 1998, Univ. of Zurich, Zurich, Switzerland
• 23: K. M. Passino and T. D. Seeley. Modeling and analysis of nest-site selection by honeybee swarms: the speed and accuracy trade-off. Behavioral Ecology and Sociobiology, 59:427--442, 2006.
• 24: M. van Dartel, E. Postma, and H. van den Herik. Universal properties of adaptive behaviour. In H. Blockeel and M. Denecker, editors, Proceedings of the 14th Belgium-Netherlands Conference on Artificial Intelligence (BNAIC'02), Leuven, Belgium, pages 59--66, 2002.
• 25: G. M. Viswanathan, V. Afanasyevc, S. V. Buldyrev, S. Havlin, M. G. E. da Luze, E. P. Raposof, and H. E. Stanley. Lévy flights in random searches. Physica A: Statistical Mechanics and its Applications, 282:1--12, 2000.
• 26: A. N. Vlasak. Global and local spatial landmarks: their role during foraging by columbian ground squirrels (Spermophilus columbianus. Animal Cognition, 9:71--80, 2006.
• 27: K. von Frisch. The dance language and orientation of bees. Harvard University Press, Cambridge, Massachusetts, 1967.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems

Additional Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.2 Types of Systems
          Subjects: Decision support (e.g., MIS)

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.0 General
          Subjects: Cognitive simulation
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development

General Terms:
Algorithms, Design, Management, Performance, Theory

Keywords:
landmark navigation, multi-agent systems, swarm intelligence