Autonomous navigation system applied to collective robotics with ant-inspired communication

ABSTRACT

Research in collective robotics is motivated mainly by the possibility of achieving an efficient solution to multi-objective navigation tasks when multiple robots are employed, instead of a single robot. Several approaches have already been tried in multi-robot systems, but the bio-inspired ones are the most frequent. This paper proposes to augment an autonomous navigation system based on learning classifier systems for using in collective robotics, introducing an inter-robot communication mechanism inspired by ant stigmergy, with each robot acting independently and cooperatively. The navigation system has no innate basic behavior and all knowledge necessary to compose the decision-making artifact is evolved as a function of the environmental feedback only, during navigation. Repulsive and/or attractive pheromone trails are produced by the robots along navigation, following very simple rules. Basically, each robot has to perform obstacle avoidance and target search, and the status of the pheromone level at the position currently occupied by each robot will influence the coordination of the two fundamental behaviors. Experiments are performed in simulation, with comparative results indicating that the presence of the pheromone trails is responsible for significant improvements in the capture rate and in the length of the route adopted by each robot.

REFERENCES

• 1: Abraham, A. and Ramos, V. Web usage mining using artificial ant colony clustering and linear genetic programming. In Proceedings of CEC '03. Canberra, Australia, 2003, (2) 1384 -- 1391.
• 2: Arai, T., Pagello, E., and Parker, L. Guest editorial, Advances in multi-robot systems. IEEE Transactions on Robotics and Automation, 18(5), 2002, 655--661.
• 3: Ronald C. Arkin, An Behavior-based Robotics, MIT Press, Cambridge, MA, 1998
• 4: Bauer, A., Bullnheimer, B., Hartl, R.F. and Strauss, C. An ant colony optimization approach for the single machine total tardiness problem. In Proceedings of CEC'99. Piscataway, USA, 1999, 1445--1450.
• 5: Caetano, F.H., Klaus, J. and Zara, F.J. Ants: Biology and Anatomy. (in Portuguese) Editora da UNESP, Rio Claro, 2002.
• 6: Scott Camazine , Nigel R. Franks , James Sneyd , Eric Bonabeau , Jean-Louis Deneubourg , Guy Theraula, Self-Organization in Biological Systems, Princeton University Press, Princeton, NJ, 2001
• 7: Cazangi, R.R. and Figueiredo, M.F. Simultaneous Emergence of Conflicting Basic Behaviors and Their Coordination in an Evolutionary Autonomous Navigation System, In Proceedings of CEC'02, Honolulu, USA, 2002, 466 -- 471.
• 8: Cazangi, R.R., Von Zuben, F.J. and Figueiredo, M.F. A Classifier System in Real Applications for Robot Navigation. In Proceedings of the CEC'03, Canberra, Australia, 2003, (1) 574 -- 580.
• 9: de Castro, L.N. and Von Zuben, F.J. Biologically Inspired Collective Robotics. In L.N. de Castro & F.J. Von Zuben, Recent Developments in Biologically Inspired Computing, Idea Group Inc., Chapter 1, 2004.
• 10: França, F.O., Von Zuben, F.J., and de Castro, L.N. Definition of Capacitated p-Medians by a Modified Max Min Ant System with Local Search. In Proceedings of 11th International Conference on Neural Information Processing, Calcutta, India, 2004, 1094--1100.
• 11: Ding, Y., He, Y. and Jiang, J. Multi-Robot Cooperation Method Based on the Ant Algorithm. In Proceedings of the 2003 IEEE Swarm Intelligence Symposium, Indianapolis, USA, 2003.
• 12: Holland, J.H. Escaping Brittleness: The Possibilities of General-Purpose Learning Algorithms Applied to Parallel Rule-Based Systems. In Michalsky, R.S., Carbonell, J.G. and Mitchell, T.M., (eds.), Machine Learning: An Artificial Intelligence Approach, Morgan Kaufmann, 1986.
• 13: Kube, C.R., Parker, C.A.C., Wang, and T., Zhang, H. Biologically Inspired Collective Robotics. In L.N. de Castro & F.J. Von Zuben, Recent Developments in Biologically Inspired Computing, Idea Group Inc., Chapter 15, 2004.
• 14: Sherafat, V., de Castro, L.N. and Hruschka, E.R. TermitAnt: An Ant Clustering Algorithm Improved by Ideas from Termite Colonies <http://www.dca.fee.unicamp.br/%7Elnunes/>. In Proceedings of 11th International Conference on Neural Information Processing, Calcutta, India, 2004, 1088--1093.
• 15: Svennebring, J. and Koenig, S. Building Terrain-Covering Ant Robots. Technical Report GIT-COGSCI-2002/10, College of Computing, Georgia Institute of Technology, Atlanta, USA, 2002.
• 16: Wagner, I.A. and Bruckstein, A.M. Cooperative Cleaners: A Case of Distributed Ant-Robotics <http://www.cs.technion.ac.il/~wagner/>. In Communications, Computation, Control, and Signal Processing: A Tribute to Thomas Kailath. Kluwer Academic Publishers, The Netherlands, 1997, 289 -- 308.
• 17: Watabane, Y., Ishiguro, A. and Uchikawa, H. Decentralized Behaviour Arbitration Mechanism for Autonomous Mobile Robot Using Immune Network, In D. Dasgupta (Editor), Artificial Immune Systems and their Applications, Springer, 1999.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.9 Robotics
          Subjects: Autonomous vehicles

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems; Intelligent agents

General Terms:
Algorithms, Experimentation, Performance

Keywords:
ant stigmergy, autonomous navigation, collective robotics, learning classifier systems