Distributed evaluation functions for fault tolerant multi-rover systems

ABSTRACT

The ability to evolve fault tolerant control strategies for large collections of agents is critical to the successful application of evolutionary strategies to domains where failures are common. Furthermore, while evolutionary algorithms have been highly successful in discovering single-agent control strategies, extending such algorithms to multi-agent domains has proven to be difficult. In this paper we present a method for shaping evaluation functions for agents that provide control strategies that are both tolerant to different types of failures and lead to coordinated behavior in a multi-agent setting. This method neither relies on a centralized strategy (susceptible to single points of failures) nor a distributed strategy where each agent uses a system wide evaluation function (severe credit assignment problem). In a multi-rover problem, we show that agents using our agent-specific evaluation perform up to 500% better than agents using the system evaluation. In addition we show that agents are still able to maintain a high level of performance when up to 60% of the agents fail due to actuator, communication or controller faults.

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 International Conference 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 Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2004), pages 1--12, Seattle, 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 (GECCO 2003), 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: 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]
• 11: 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
• 12: Kagan Tumer , Adrian Agogino, Coordinating multi-rover systems: evaluation functions for dynamic and noisy environments, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068109]
• 13: 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
• 14: 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
• 15: 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, robust optimization