This page contains links to movies (in the form of GIF animations)
depicting evolved robot controllers controlling simulated
Khepera-like robots in a real-time competitive task. The controllers
were evolved using the
NEAT method for evolving neural network topolgies and
weights using a genetic algorithm. All of the movies
depict evolved neuro-controllers from a single run of hundreds of
generations. The movies show the robots' behavior in a task, and
also show the actual evolved neural network controllers
with neurons firing in real-time, so you can see what the
robots are "thinking" as they compete.
The main point of the experiment is to show that evolving neural networks using NEAT allows a new, more powerful kind of competitive coevolution to take place. This powerful form of coevolution is called continual competitive coevolution. The idea is that because NEAT allows networks to add structure indefinitely, a competing population in competitive coevolution should always be able to supplement a strategy by complexifying that strategy through the addition of new structure. The hope is that increasingly sophisticated strategies will utilize increasingly complex structures, preventing the arms race from stagnating.
The competitionThe competitive task is challenging. The robots always start out in a world with exactly the same configuration. 9 pieces of food are placed in the world, with the two robots in the center. The image below shows what the world looks like. Please adjust your browser so that the entire image is visible on your screen:
On the left of the image is the world where the robots collect food. On the right are the robots' neural network controllers. The yellow robot is controlled by the upper neural network, and the red robot is controlled by the lower network.
Each network has 3 numbers to its left. These numbers represent:
Whenever a robot encounters a piece of food, its energy goes up by 500. At the same time, energy decreases the more distance a robot travels. There is no limit to how low energy can go; it can easily sink below zero.
The only way for a robot to win the compition is to collide with its opponent while its energy is higher than its opponent's energy. This rule makes the game interesting, because the predator-prey relationship can constantly shift back and forth, depending on food being eaten. Energy is used for no other purpose than to determine who kills whom in a collision; it does not affect robot's ability to move, although moving can be risky when energy is low, especially when no food is available, since the robot with lower energy can be killed. As long as a robot has higher energy, it is safe.
The rules of the game encourage an unusual phenomenon to evolve: switching behavior. Robots must learn to change their goals quickly depending on which robot has the most energy at any given time. A robot with lower energy may decide to stay put and hope its opponent wastes energy by running around, or it may try to find more food. As you can imagine, complex strategies arise. The main reason that this scenario leads to complexity is that unlike in standard predator-prey tasks, both the predator and the prey are evolving to outwit each other, and networks must be capable of playing both roles.
Understanding the MoviesIn the image above, the world contains two robots, each surrounded by 2 concentric rings. The rings represent rings of range sensors, which work like Khepera range sensors. However, one ring of sensors can detect robots, and the other can detect food. Each ring has 4 sensors with slightly overlapping arcs of sensitivity. The inner ring contains the food sensors, and the outer ring holds the robot sensors. When you watch the movies, you can actually see the sensor activation levels on the rings themselves, and you can see the sensors swiveling as the robots turn. Sensor activations are depicted as squares of different sizes. Note that the robot who currently has the higher energy level has yellow sensor rings, whereas the robot with lower energy has black sensor rings. This way, it is easy to see who could be playing predator at any given time.
The sensors map to the inputs of of the neural networks on the right of the image. The inputs are at the bottom of each network:
Each network has two motor outputs (at the top). The outputs represent the force to be applied the left and right motor. Each motor drives a wheel. Thus, running the left motor alone causes a turn to the right, etc. Each output has a number above it representing its current activation on a scale of 0 to 100,000 (actual outputs are between 0 and 1).
The neural networks depict evolved topologies. They are composed of:
Since NEAT evolves arbitrary topologies, topologies can become quite complex. The visualizations are designed to do their best to display the networks as clearly as possible.
The experimentAs usual , NEAT begins with zero-hidden-node networks and evolves topologies and links from there. If you want to know more details about how the NEAT method works, see our paper. The initial generation contained two populations, A and B, all with uniform zero-hidden-node topologies. A and B were pitted against each other in a competitive coevolution host/parasite framework (see "New Method for Competitive Coevolution", Rosin and Belew, 1996). As the generations progress, an arms race built up between A and B. The results show that increasingly sophisticated structures continually arose (for hundreds of generations), each newly dominant strategy containing significantly more structure than the previous. Also, there was no circularity in the dominance relationships.
Who's the best?Before moving to the animations, we should address one serious question: How do we know that a network is better than another network from just a single competition? There are two answers to this question:
First, the training scenarios are all deterministic (meaning that the food and robots start in exactly the same positions). Therefore, if a network wins against another network in this setup, it will always win, since we did not introduce noise to the sensors.
However, in testing the networks for superiority we should really play many different competitions to attain statistical significance demonstrating that one network really is better than another. Thus, we played each pair of competitors 1,000 times with slightly different food configurations. The superior network was verified by winning a significant majority of these 1,000 competitions. Thus, the movies below are not the reason that we say one network is dominant over another. Rather, they are interesting to observe after the fact, knowing which network is dominant. Knowing this, we can see what strategy the dominant network actually uses by watching the movies. It just so happens that in the movies below, the superior network is always the winner, which is not surprising, since it is what we expect probabilistically.
These early networks are the champions of generations 1 and 3, respectively. The movie begins well into the round. The yellow robot has spent a long time moving towards the food extremely slowly. The movie then begins near the second piece of food. The Red robot has hardly moved at all. The yellow network runs into the red network mostly by chance after getting its food, although it does show some intelligence. (In case you wonder, the yellow network loses badly to later dominant strategies.)
These champions from generations 20 and 50 have evolved to conserve energy by sitting still and letting the opponent waste energy by moving. The problem is that when two such networks meet, nothing happens. That's why this clip doesn't move.
The champions from population A and B in generation 40 compete in this clip. Neither bother to use food at all. The red robot wastes a lot of energy moving around to no end, while the yellow robot slowly edges in. The strategies are poor because they do not utilize the food resources.
Around generation 80, the first good strategy arose in population A. This competition pits the champion of generation 80 against an improved version of the same strategy by the champion of population 95. Note that both competitors here are using a sophisticated strategy with a clear switching behavior among food gathering, caution, and predation. The competition culminates in an interesting standoff where both players have similar energy levels. The robots gingerly approach each other, hoping the other one will waste more energy in the approach.
The standoff is actually quite complex. If one robot moves and the other doesn't, then the mover now has relatively less energy. However, there is no way to win if both robots just stand still, leading to an interesting dilemma. Since robots only receive credit for winning, there is great incentive to take risk. The robots tend to flinch in an attempt to get the other robot to move more, leading to an "old west"-like duel at the end.
Notice that this somewhat sophiticated strategy only requires a single hidden-node, lending support to the practice of starting evolution minimally.
The movie shows an "old west"-style standoff similar to the one in the previous clip, but even more cautious and drawn-out. The competitors here are champions from generations 95 and 90. The movie begins as the standoff begins, skipping the preceding food-gathering.
A later dominant strategy arose around the 190th generation in population B. By generation 221, this new strategy dominated the world. This movie shows the champion of generation 221 playing the champion of generation 130, which is a highly optimized version of the first good strategy to arise. (The lower network, which is the red robot, is from generation 221.)
Notice the later dominant strategy is more cautious than the first, and tends to be conservative about collecting enough food to be safe. We can see the red robot change its stratgy in mid-stride at several points, deciding to get more food instead of pursue the yellow robot.
Important to the theory behind continual coevolution, the higher sophistication of the later dominant strategy utilizes a more complex structure than the inferior network.
Out of 1000 competitions from slightly different starting configurations, the later dominant won 617, the earlier strategy won 376, and the remaining competitions were draws (timed out).
The highest dominant strategy arose in generation 313 in population A This new strategy appears as the lower neural network (red robot). The complexity has clearly gone up significantly. The champion of generation 210 (the prior dominant strategy) is the upper robot (yellow)
Notice that the red robot takes very clever advantage of the yellow robot's tendency to collect as much food as possible. The red robot decides to do nothing while the yellow robot rolls to the second-to-last piece of food. In a surprisingly insightful move, the red robot then dashes for the last piece of food, ensuring victory through its closer proximity. The yellow robot is caught with nowhere to go and quickly devoured.
In 1,000 different competitions between these two strategies, the highest dominant won 532, and the prior dominant won 448. The remainder were draws (timed out).
To be sure that stragies are indeed progressing in sophistication in a total order, we need to check for circular dominance. In other words, even tough the highest dominant strategy is superior to a prior dominant, the even-earlier first good strategy might still be able to defeat the third dominant, creating a circle of dominance. Circular dominance is not what we want in competitive coevolution.
The movie shows the champion of generation 95 (yellow) playing the champion of generation 313 (red). To check for circular dominance, we test the later dominant strategy against the earlier strategy. The highest dominant appears to prevail by being more decisive than the earlier strategy, as this movie shows. The yellow robot simply finds itself in trouble before there is time to do anything about it.
In 1,000 different competitions, the highest dominant won 599, and the other won 313. The remainder were ties.