Coordinating multi-rover systems: evaluation functions for dynamic and noisy environments

ABSTRACT

This paper addresses the evolution of control strategies for a collective: a set of entities that collectively strives to maximize a global evaluation function that rates the performance of the full system. Directly addressing such problems by having a population of collectives and applying the evolutionary algorithm to that population is appealing, but the search space is prohibitively large in most cases. Instead, we focus on evolving control policies for each member of the collective. The main difficulty with this approach is creating an evaluation function for each member of the collective that is both aligned with the global evaluation function and sensitive to the fitness changes of the member. We show how to construct evaluation functions in dynamic, noisy and communication-limited collective environments. On a rover coordination problem, a control policy evolved using aligned and member-sensitive evaluations outperforms global evaluation methods by up to 400%. More notably, in the presence of a larger number of rovers or rovers with noisy and communication limited sensors, the improvements due to the proposed method become significantly more pronounced.

REFERENCES

• 1: A. Agah and G. A. Bekey. A genetic algorithm-based controller for decentralized multi-agent robotic systems. In In Proc. of the IEEE Int. Conf. of Evolutionary Computing, Nagoya, Japan, 1996.
• 2: A. Agogino , K. Stanley , R. Miikkulainen, Online Interactive Neuro-evolution, Neural Processing Letters, v.11 n.1, p.29-38, Feb. 2000 [doi>10.1023/A:1009615730125]
• 3: A. Agogino and K. Tumer. Efficient evaluation functions for multi-rover systems. In The Genetic and Evolutionary Computation Conference, pages 1--12, Seatle, WA, June 2004.
• 4: Gianluca Baldassarre , Stefano Nolfi , Domenico Parisi, Evolving mobile robots able to display collective behaviors, Artificial Life, v.9 n.3, p.255-267, Summer 2003 [doi>10.1162/106454603322392460]
• 5: M. Dorigo and L. M. Gambardella. Ant colony systems: A cooperative learning approach to the travelling salesman problem. IEEE Transactions on Evolutionary Computation, 1(1):53--66, 1997.
• 6: S. Farritor and S. Dubowsky. Planning methodology for planetary robotic exploration. In ASME Journal of Dynamic Systems, Measurement and Control, volume 124, pages 4: 698--701, 2002.
• 7: Dario Floreano , Francesco Mondada, Automatic creation of an autonomous agent: genetic evolution of a neural-network driven robot, Proceedings of the third international conference on Simulation of adaptive behavior : from animals to animats 3: from animals to animats 3, p.421-430, July 1994, Brighton, United Kingdom
• 8: F. Gomez and R. Miikkulainen. Active guidance for a finless rocket through neuroevolution. In Proceedings of the Genetic and Evolutionary Computation Conference, Chicago, Illinois, 2003.
• 9: F. Hoffmann, T.-J. Koo, and O. Shakernia. Evolutionary design of a helicopter autopilot. In Advances in Soft Computing - Engineering Design and Manufacturing, Part 3: Intelligent Control, pages 201--214, 1999.
• 10: A. Martinoli, A. J. Ijspeert, and F. Mondala. Understanding collective aggregation mechanisms: From probabilistic modelling to experiments with real robots. Robotics and Autonomous Systems, 1999.
• 11: Maja J. Mataric, Coordination and Learning in Multirobot Systems, IEEE Intelligent Systems, v.13 n.2, p.6-8, March 1998 [doi>10.1109/5254.671083]
• 12: Kenneth O. Stanley , Risto Miikkulainen, Efficient Reinforcement Learning Through Evolving Neural Network Topologies, Proceedings of the Genetic and Evolutionary Computation Conference, p.569-577, July 09-13, 2002
• 13: K. Tumer and A. Agogino. Overcoming communication restrictions in collectives. In Proceedings of the International Joint Conference on Neural Networks, Budapest, Hungary, July 2004.
• 14: Kagan Tumer , David H. Wolpert , Kagan Turner, Collectives and Design Complex Systems, SpringerVerlag, 2004
• 15: K. Tumer and D. Wolpert. A survey of collectives. In Collectives and the Design of Complex Systems, pages 1,42. Springer, 2004.
• 16: Kagan Tumer , David Wolpert, Collective Intelligence and Braess' Paradox, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.104-109, July 30-August 03, 2000
• 17: L. Darrell Whitley , Frédéric Gruau , Larry D. Pyeatt, Cellular Encoding Applied to Neurocontrol, Proceedings of the 6th International Conference on Genetic Algorithms, p.460-469, July 15-19, 1995
• 18: D. H. Wolpert and K. Tumer. Optimal payoff functions for members of collectives. Advances in Complex Systems, 4(2/3):265--279, 2001.

INDEX TERMS

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

General Terms:
Algorithms, Performance

Keywords:
genetic algorithms, multiagent systems, neural networks