My research focuses on discovering structure that makes it possible to solve complex sequential decision tasks. In particular, I have developed a method called NeuroEvolution of Augmenting Topologies (NEAT) that builds an artificial neural network (ANN) topology appropriate for the task. NEAT makes it possible to learn control policies in challenging real-world domains, such as real-time gaming and robotic and vehicle control. In the future, I will extend NEAT to discover more complex and realistic neural structures.
Neuroevolution (NE) is a machine learning method that has achieved early successes in significant applications over the last decade. In NE, a population of ANNs evolves in a survival-of-the-fittest competition to perform a task or solve a problem. ANNs that perform better reproduce to create offspring that replace those that are less successful, and over generations, performance gradually improves. NE has made several significant achievements possible over the last decade, such as discovering the mobility strategy in Othello only a few years after it was first discovered by humans, successfully controlling a rocket that flies without fins, and the fastest learning in benchmark pole balancing reinforcement learning problems. These early accomplishments suggest that NE is a powerful method with the potential to solve important real world problems.
In most early NE methods, the topology of the ANN was chosen by the experimenter. Such fixed-topology NE methods search for the best connection weights to perform the task. The number of parameters being searched is equivalent to the number of connections in the network. Thus, fixed-topology NE is similar to other reinforcement learning methods in that the search aims to optimize parameters in a chosen space.
However, unlike traditional reinforcement learning methods, NE can also learn the topology of networks along with their connection weights. By evolving compact topologies with as few connections as possible, the search space can potentially be significantly reduced, leading to faster search. However, the early topology-evolving methods were not as effective as they could have been because there was no way to recombine or compare different topologies efficiently.
I designed the NEAT method specifically to solve this fundamental problem, making it possible to evolve populations of diverse topologies quickly and efficiently. NEAT utilizes historical marking and speciates the population in order to protect innovative structures in their own niches. In a process of complexification, ANNs become increasingly complex over generations, making it possible to build up to the right number of parameters for the task.
This approach to evolving diverse topologies yielded significant results. First, NEAT solved the difficult reinforcement learning benchmark problem of balancing two poles simultaneously without velocity information in the fastest time to date. Complexification from a minimal starting point allowed NEAT to find very small topologies that were easily optimized. Second, NEAT demonstrated how complexification can lead to complex robot-control strategies in a simulated robot duel domain. This domain is particularly challenging because it requires discovering increasingly sophisticated strategies in competitive coevolution. As reported in our recent JAIR article, Competitive Coevolution through Evolutionary Complexification, complexification establishes and maintains an evolutionary arms race, i.e. sophisticated strategies continue to elaborate throughout evolution, which is generally very difficult to achieve.
Currently, NEAT is being applied to several challenging real-world problems. First, in a joint project with Toyota, NEAT is being used to evolve a warning system to help drivers navigate safely In preliminary tests in simulation, the system succeeds in warning before crashes are imminent, allowing drivers to take preventative action. Second, NEAT is being extended to work in real-time so that multiple agents can evolve in a simulation or a gaming environment in response to player behavior. A prototype of this real-time version of NEAT (rtNEAT) has been integrated into a commercial-grade video game engine to create the NERO project, which is sponsored by the Digital Media Collaboratory (DMC) at the IC2 Institute at UT Austin. The DMC has dedicated significant resources, including assembling a team of over 30 volunteers, to create a new genre of video game around rtNEAT. In this new genre, agents learn tasks specified by a player in real time. In response to this project, video game and training simulation companies such as NCSoft and RadioActive Labs have expressed interest in utilizing rtNEAT technology in their products, which may change the way characters develop in video games in the future. In these and other domains, NEAT is solving real problems in ways that have not heretofore been possible.
Although NEAT was introduced only three years ago, it has already had significant impact. Our paper on the NEAT methodology won the Best Paper Award in Genetic Algorithms at GECCO-2002, the premier conference in the field. At least seven publicly available versions of NEAT have been independently produced by other researchers for various computer platforms and languages. NEAT was featured in the AI Techniques for Game Programming book, by Mat Buckland, presented as a method for evolving control strategies for live-action video game characters. NEAT has been used as a teaching tool in graduate classes at the University of Texas and the University of New Mexico. In response to the growing interest in NEAT, a NEAT Users Group was independently founded by Derek James, and currently includes over 100 members from around the world. NEAT has been popular most likely because it is the first method that can quickly and efficiently evolve increasingly complex arbitrary neural structures, which is widely recognized as an important challenge in the field.
In the future, I plan to push the current neuroevolution technology towards increased realism and complexity. In particular, my research will focus on three key areas: (1) I will make the artificial neurons that compose ANNs more realistic through adding temporal integration properties and plasticity. With such a model, ANNs can use memory to generate complex output patterns and learn over their lifetime. (2) I will develop new indirect encoding techniques that are capable of representing significantly more complex structures with fewer genes. Our paper, A Taxonomy for Artificial Embryogeny (in the Artificial Life journal), charts a course for initial exploration into such systems and is currently the only major review in this area. (3) I will generalize NEAT to a broad range of domains and problems so that it can be further developed as a general process of discovery. While NEAT currently evolves ANNs, complexification can in principle be applied to any structured domain. I will develop major applications in real-world domains, possibly including complexifying electrical circuit designs, building architectures, cellular automata, genetic programs, Bayesian networks, musical compositions, finite automata, and robot morphologies. Developing such applications will encourage students getting started with research and will provide a broad foundation for projects in a variety of domains.
NEAT is a principled step towards the goal of automatically generating complex adaptive systems. Starting from a simple rudimentary solution, a sequence of elaborations creates a chain of increasing complexity, leading to solutions with levels of sophistication heretofore unreachable. My thesis is that a principled sequence of such elaborations can create a chain of increasingly complexity, leading to solutions with levels of sophistication heretofore unreachable. The NEAT methodology is a concrete implementation of this idea, and further developing it theoretically and in practice will be the focal point in my research program.