Methods for competitive and cooperative co-evolution

Abstract We have been investigating evolutionary methods to design behavioral strategies for intelligent robots in multi-agent environments. Such ~nvi-ronments resemble an ecological system in which species evolve and adapt in a complex interaction with other evolving and adapting species. This paper will report on our investigations of alternative co-evolutionary approaches in the context of a simulated multi-agent environment. Background This is a progress report on our efforts to design intelligent robots for complex environments. The sort of applications we have in mind include sentry robots, autonomous delivery vehicles, undersea surveillance vehicles, and automated warehouse robots. We are investigating the issues relating to machine learning on representative tasks such as playing hide-and-seek, tag, or competing to find hidden objects. Our test bed includes multiple mobile robots. We have been investigating evolutionary methods to design behavioral strategies for such tasks. In particular, we are exploring the information processing capabilities of genetic algorithms that improve system performance through simulated evolution. Much of the earlier work in genetic algorithms has focused on static environments, i.e., environments whose most important characteristics do not vary in time. For example, we have used genetic algorithms for learning reactive rules for navigation and collision avoidance for environments in which is assumed that the obstacles move slowly relative to the robot (8). We have also investigated evolutionary methods in dynamic environments. For example, Cobb and Grefenstette (2) examined genetic algorithms for randomly shifting environments. If the changes in the environments can be detected and classified by the learning system, then case-based methods can by applied (6). However, environment which contains other learning agents more closely resembles an ecological system in which species evolve and adapt in a complex interaction with other evolving and adapting species. This paper reports o