Evolutionary Stigmergy In Multipurpose Navigation Systems

Autonomous robot navigation involves many challenges and difficulties which are augmented when multiple robots operate together. Sophisticated computational techniques are required to cope with autonomous navigation in collective robotics, being the biologically-inspired approaches the most frequently adopted. Stigmergy, i.e. the ants communication by means of pheromones, is the main biological metaphor used in this work to perform multi-robot communication. The robots will be able to mark regions of the environment with artificial pheromones, according to past experiences, assisting one another in a cooperative and indirect way to accomplish the navigation objectives. Each robot is controlled by an autonomous navigation system (ANS) based on Learning Classifier System, which evolves during navigation from no a priori knowledge. Besides learning to avoid obstacles and capture targets, the systems must also learn how and where to lay artificial pheromones. Some experiments and simulations are performed intending to particularly investigate the ANS from three main perspectives: capability of learning to achieve the navigation objectives in collective scenarios, adaptability in face of environmental changes and ability to obtain optimized navigation behaviors by means of stigmergy. © 2006 IEEE.370377Bonabeau, E., Dorigo, M., Theraulaz, G., (1999) Swarm Intelligence: From Natural to Artificial Systems, , Oxford University PressBalch, T., Arkin, R.C., Communication in reactive multiagent robotic systems (1994) Autonomous Robots, 1 (1), pp. 27-52Grasse, P., La reconstruction du nid et les coordinations inter-individuelle chez bellicoitermes natalenis et cubitermes sp la theorie de la stigmergie: Essai d'interpretation des termites constructeurs (1959) Insectes Sociaux, 6Camazine, S., Franks, N.R., Sneyd, J., Bonabeau, E., Deneubourg, J.-L., Theraula, G., (2001) Self-Organization in Biological Systems, , Princeton University PressHolland, O., Melhuish, C., Stimergy, self-organization, and sorting in collective robotics (1999) Artificial Life, 5 (2), pp. 173-202Wagner, I.A., Bruckstein, A.M., Cooperative cleaners: A study in ant-robotics (1997) Communications, Computation, Control, and Signal Processing, pp. 298-308Ding, Y., He, Y., Jiang, J., Multi-robot cooperation method based on. the ant algorithm (2003) Proc. of the 2003 IEEE Swarm Intelligence Symposium, pp. 14-18. , Indianapolis, USA: IEEEVaughan, R., Stoy, K., Sukhatme, G., Mataric, M., Lost: Localization-space trails for robot teams (2002) IEEE Transactions on Robotics and Automation, 18 (5), pp. 796-812Sauter, J., Matthews, R., Parunak, H., Brueckner, S., Evolving adaptive pheromone path planning mechanisms (2002) Proceedings of the First International Joint Conference on Autonomous Agents and Multi-Agent Systems, pp. 434-440Wurr, A., Robotic team navigation in complex environments using stigmergic clues, (2003), Master's thesis, University of ManitobaCazangi, R.R., Zuben, F.J.V., Figueiredo, M.F., Autonomous navigation system applied to collective robotics with ant-inspired communication (2005) Proceedings of the 2005 Conference on Genetic and Evolutionary Computation, 1, pp. 121-128. , Washington DC, USA: ACM Press_, Stigmergic autonomous navigation in collective robotics, in Stigmergic Optimization, A. Abraham., C. Grosan, and V. Ramos, Eds. Springer-Verlag, 2006Holland, J., Escaping brittleness: The possibilities of general purpose learning algorithms applied to parallel rule-based systems (1986) Machine Intelligence II, , R. Michalsky, J. Carbonell, and T. Mitchell, Eds. Morgan KaufmannSvennebring, J., Koenig, S., Towards building terrain-covering ant robots (2002) Ant Algorithms, pp. 202-215Cazangi, R.R., Figueiredo, M., Simultaneous emergence of conflicting basic behaviors and their coordination in an evolutionary autonomous navigation system (2002) Proceedings of the 2002 Congress on Evolutionary Computation, pp. 466-471. , Honolulu, USACazangi, R.R., Zuben, F.J.V., Figueiredo, M.F., A classifier system in real applications for robot navigation (2003) Proceedings of the 2003 Congress on Evolutionary Computation, 1, pp. 574-580. , Canberra, Australia: IEEE PressZiemke, T., On the role of robot simulations in embodied cognitive science (2003) Artificial Intelligence and Simulation of Behaviour, 1 (4), pp. 1-11Reinelt, G., (1990) TSPLIB - A t.s.p. library, , Universität Augsburg, Institut für Mathematik, Augsburg, Tech. Rep. 25