Emergence of Cooperation in a Pursuit-Evasion Game

1 Introduction

The use of evolutionary computation as a design process for control of robot reams has received much attention in both real world [Quinn, 2000], [Schultz and Grefenstette, 2000], and simulated problem domains [Kitano, 1997]. Such attention is due to the difficulty in specifying a priori an effective means for multiple interacting robot controllers, and the inherent adaptability of artificially evolved controllers. The use of evolutionary computation to exploit emergent cooperation remains a relatively unexplored area of research in the pursuit and evasion domain [Benda eta!. 1985] and related predator­ prey systems [Nishimura and Takashi, 1997] using multiple predators and prey. Various approaches have been used to study the pursuit evasion domain, where the task is for multiple predators to capture a prey by surrounding it [Korf, 1992], [Levy and Rosenschein, 1992], though few researchers have investigated emergent cooperation in these systems, with notable exceptions such as Denzinger and Fuchs [1996], Haynes and Sen [1996] and Yong and Miikkulainen [2001].

In this approach there is no plasticity so the predators cannot adapt during their lifetime. The fitness assigned to each predator is simply the fitness calculated for the single genotype that specifies the predator team. The main advantage of this approach is its simplicity in terms of behavioral encoding and calculation of team fitness.

Plasticity Approach: As illustrated in figure 1 (right) this approach generates and tests n copies of a single genotype, so that as with the single pool approach, the predator team is homogenous. The difference is that individual phenotypes are able to adapt during their lifetime as a result of a recurrent neural network learning process. The advantage of the plasticity approach is that it allows for specialization of behaviour by individual predators without being affected by the problem of needing to estimate fitness contribution of different predators to the team as a whole. For both the single pool and plasticity approaches, every individual genotype in the population is tested against n-1 randomly selected genotypes from the same population. This process is repeated for all 10 epochs of a predator's lifetime.

Multiple Pools Approach: As illustrated in figure 2 this approach takes a single genotype from every population of genotypes where the number of populations corresponds to the number of predators. Each genotype is then decoded into a separate phenotype, where this set of phenotypes then represents the team of predators. In each generation, every individual genotype in a population is tested against n-1 other genotypes, randomly selected from one of the other populations of genotypes. This process is then repeated for every epoch. The advantage of the multiple pools approach is that it encourages behavioural specialization in the group of predators, in that the artificial evolution setup provides for more genetic diversity.

Rule Based Approach: This approach takes a predator previously evolved for obstacle avoidance and then extends this behavior with a simple set of rules designed to encourage a cooperative encirclement pursuit strategy when at least two predators collectively approach a single prey. The rules cause a predator to move towards the right side of detected prey, and to push to the left against that side, while moving about the prey's periphery. If an obstacle is detected on the preys right side, the predator will attempt to keep moving about the preys periphery until a 'free-space' is found.

Evaluation of Approaches

In order to quantify the effectiveness of emergent prey capture strategies, two different measures were used to evaluate performance. The first was predator team fitness, where fitness awarded to the team was proportional to how much a prey was slowed during the team's lifetime. The second was prey capture time, which was the time period for which a prey was immobilized by the collective efforts of at least two predators. For both the single pool and plasticity approaches a single genotype specifies the entire predator team. That is, predators are clones of each other, so evaluation of team performance in this case is not problematic. The performance of a predator team executed under either of these approaches is simply measured as the fitness value assigned to the genotype that specifies the team. For the rule-based approach, a pseudo fitness function that emulates the single pool and plasticity approaches was implemented. In contrast to these approaches a predator team using the multiple pools approach is specified by n genotypes selected from n different populations. Hence, each genotype must be assigned an individual fitness score, and team performance evaluation needs to be computed by estimating the fitness contribution of each genotype to the team as a whole. A method of evaluation widely known as: fitness sharing [Bull and Holland, 1997] was implemented for the multiple pools approach, where an equal fitness score is assigned to each individual genotype, thereby assuming that each individual contributed to team performance equally. The advantage of this method is that fitness for individual genotypes is easily calculated and there is no disparity between team fitness and the fitness of individual team members.

Agents, Environment and Artificial Evolution

For all experiments a generational evolutionary algorithm using linear rank-based selection was used [Goldberg, 1989]. Each population contained 100 genotypes, where initial populations consisted of randomly generated genotypes. Genotype length was set to 24 genes, where each gene consisted of several bits encoding each neuron type and connection weights. At the tum of each generation, the 20 genotypes that have accumulated the highest fitness were allowed to reproduce. The total fitness of an individual genotype was the sum of all its fitness for all epochs of its life. Reproduction was done via generating five copies of each genotype in order to create the next generation.

During this copying process 10 percent of the connection weights were mutated. Mutation added a random value between -1.0 and + 1.0 to the weights current value. This process was repeated for the 500 generations that each simulation ran for. As illustrated injigure 3 (left), the body of each predator and prey is assumed to be a Khepera mobile robot [Mondada eta!. 1993].

The robots used as predators were equipped with 8 infrared proximity sensors, and 8 light sensors positioned on the periphery of the Khepera. The robots used as prey were equipped with 8 infrared proximity sensors, as well as a light on its top. This light could be detected by the predator light sensors and was used so as each predator robot could distinguish fellow predators from a prey. Figure 3 (right) illustrates the feed-forward neural network consisting of an input and output layer with no hidden units [Nolfi and Parisi, 1997] that controlled all robots executed under the single pool and plasticity approaches. In the case of the predators, the input layer consisted of 16 units that encoded the activation level of the robots 16 sensors. These 16 input units were connected to 4 output units. Figure 3 (right) also illustrates the recurrent neural network controller used in the plasticity experiments, where the activation level of two additional output units was copied back into two additional input units. The first two output units represented the two motors of the robot and encoded the speed of the two wheels. These motor units controlled the robots behavior in the environment. The next two output units represented two teaching units that encoded a teaching input for the fust two output units. The two motor units used this teaching input in order to learn using the back propagation procedure [Rumelhart et a!. 1986]. In the plasticity experiments there were an additional two output units that were the recurrent units and contained activation values for the motors from the previous cycle. For the robots that were the prey, a network connecting 8 sensory input units to 4 motor output units was trained for an obstacle avoidance behavior before being placed in the environment.

The environment corresponded to a 1 OOOcm x 1 OOOcm arena with no obstacles. When a predator robot was placed in the environment, sensory input was received via the input units, and activation values were passed to the two motor units, and the teaching units. The activation value of the two motor units was used to move the robot, thus changing the sensor input for the next simulation cycle. The activation value of the two teaching units was used to change the weights that connected the input units to the motor units using back propagation. This cycle was then repeated.

3 Results

Four sets of experiments were executed to test each of the three artificial evolution approaches and the rule-based approach. Each set of experiments tested the six group types and ten replications of each experiment were made.

Figure 4 illustrates the average fitness attained for all groups of predators using the rule-based, single pool, plasticity and multiple pools approaches. Figure 5 presents the average prey capture time attained for the four approaches. Prey capture refers to the instance when the prey is immobilized for a time interval t0 ·· t;.

Evolved Behavior

Evolved behavior observed for each of the three artificial evolution approaches is described in this section. For the rule-based approach, even though behavior was not evolved as for the other approaches, a single cooperative pursuit strategy emerged as the result of interaction of multiple predators following a simple set of rules.

Single Pool: For all six group types tested only two cooperative prey-capture strategies consistently emerged. These strategies, termed: encirclement and entrapment are briefly described in the following. In the encirclement strategy at least three predators move to circle the prey, each moving in the same direction in close proximity to the prey, for some period of time. The strategy was rarely able to immobilize the prey and was only effective in slowing the prey for a short period of time, given that the predators were not able to coordinate their movements for an extended period. The entrapment strategy, illustrated injigure 6, also used at least three predators, where either one or two predators moved to each side of the prey, while another, termed: a blocker, moved around the flanking predators, to approach the prey from the front, in order to trap the prey in a triangular formation. In the example depicted in figure 6, P1 and P2 are the flanking predators and P3 is the blocker. Note that at simulation time step n+j when the prey moved to escape, the flanking predators moved also, turning one way to force the prey in a specific direction. The blocker then moved around in order to affront the prey again. This system of entrapment, movement, and then entrapment continued for several times before the prey was able to evade the predators.

Rule-Based: A single cooperative strategy emerged using at least two and at most three predators. The strategy was similar to the encirclement strategy that evolved under the single pool approach. As with the single pool version of encirclement, the strategy was rarely successful at immobilizing a prey due to the lack of coordination between predators as they collectively approached a prey.

Plasticity: In these experiments one emergent cooperative prey capture strategy was observed. This strategy, illustrated in figure 7, was a derivative of the entrapment strategy and termed: role switcher. In this strategy a form of behavioural specialization emerged during the lifetime of the predators. Specifically, two different types of behavioral roles emerged, termed knocker and flanker. A flanking predator moved along one side and just ahead of the prey forcing the prey to turn in a particular direction, where as a knocking predator 'knocked' into the side of the prey forcing it to slow its movement. The role-switcher strategy was formed by a knocker predator moving along side a flanking predator and role of a flanker and knocker switching whenever a prey attempted evasion. Figure 7 depicts predator P3 formerly flanking assumes the knocking role at simulation time step n+k after the prey moves to evade, and predator P1 formerly knocking assumes a flanking role. This dynamic adoption and switching of roles coordinated the movements of the predators and thus effectively slow a prey's movement. Also, relative to the entrapment and encirclement strategies, role switcher was able to more frequently immobilize a prey.

Multiple Pools: As with the plasticity experiments the role switcher strategy was the only cooperative prey-capture strategy that consistently emerged, though a specific difference was noted. Namely, different predators adopted different roles from the beginning of their lifetimes. Specifically, particular predators always assumed the role of a flanker, while other predators always assumed the role of a knocker. Figure 8 depicts predators P2, P3 and P5 as maintaining the roles of flankers, and predators P1 and P4 maintaining the roles of knockers.

0 E, '""''

E; : Prey; P 1 : PndatDr (hie: Knoclur ); P2 : Predatu (Role: Flan.lur); P, : PndatDr (hie: Flanlur) P· : Pndatu(hle: Knoclur ); P,: Prea.tu(Role: Flanlur)

Figure 8. The role-switcher pursuit strategy, illustrated for group type 3: 5 predators and I prey. Here the assumption of behavioral roles is set at the beginning of a predator's lifetime.

Thus, at simulation time step n+j predator P4 does not move to assume the role of a knocker in the strategy as it is already taken by predator P 1 at this stage. This adoption of roles that was maintained throughout the lifetime of the predators served to increase the effectiveness of the role switcher strategy in terms of the measures defined for prey capture strategy performance. Notably the strategy was consistently effective at immobilizing a prey, for all group types tested.

4 Analysis and Discussion

This discussion compares emergent prey-capture strategies with the rule-based pursuit strategy and relates each to the group types tested and the two performance measures.

Single Pool: Two cooperative prey-capture strategies, each using at least three predators, consistently emerged for all six group types tested. Though, relative to the plasticity and multiple pools approaches these emergent strategies performed poorly in terms of average team fitness and prey­ capture time. These results are presented infigures 4 and 5 respectively and as shown were consistent for all group types tested. The low fitness and prey-capture time of the encirclement and entrapment strategies was found to be a result of interference that occurred as two or more predators collectively approached a prey. This result was found to be due to confused infrared sensor readings of predators in close proximity to each other, and the fact that individual predators did not possess any memory, explicit form of communication, or coordination to facilitate a successful cooperative prey capture strategy. As illustrated infigures 4 and 5, this result is especially prevalent for group types 5 and 6, which used eight predators.

Rule-Based: From the interactions of predators following a set of rules, an encirclement strategy emerged, though as with the single pool version of the strategy it was effective for at most three predators. Also, note in figures 4 and 5, that similar to its single pool counterpart the strategy proved most effective for group types: 1 and 4. Given that in these experiments the chance of predators physically interfering with each . other as they approached the prey was minimal. The rule-based approach, similar to the single pools approach, also performed best in group types where the predator to prey ratio was medium as in group types 1 and 4.

Plasticity: In experiments using this approach the role switcher strategy frequently emerged for all group types tested. In the role-switcher strategy a form of dynamic behavioral specialization emerged in at least three predators. This behavioral specialization was in the form of dynamic role adoption that emerged during the lifetime of a predator and varied from predator to predator depending upon the group type being tested. This dynamic role adoption facilitated cooperation between the predators affording the predator team a high average fitness and prey-capture time comparative to the single pool and rule-based approaches, for all group types tested. This result is presented in figures 4 and 5 respectively. In experiments testing group types 1, 3 and 5 at least three and at most six predators constituted the role-switcher strategy, where a maximum of three flanked either side, and the role of a flanking and knocking predator switched whenever the prey turned to evade. In experiments testing group types 1 and 6, at least three and at most eight predators formed the role-switcher strategy, where a maximum of two predators flanked either side of a prey. As with the experiments testing group types 1, 3, and 5 the role of the predator closest to the prey and the knocking predator switched whenever the prey turned so as to escape, though the difference of experimental results from testing group types 1 and 6, was that two sub-groups of predators emerged, meaning that two of the prey were simultaneously engaged by two predator sub-teams.

The dynamic assumption of roles during a predators lifetime allowed for the formation of sub-groups in the predator team, and thus served to yield a higher average team fitness and prey capture time. As presented in figures 4 and 5 respectively, these two measures were relatively higher in experiments testing group types 1, 4, and 6, and low in experiments testing group types 3 and 5. In experiments testing group types 3 and 5, this result was due to multiple predators attempting to assume the same behavioral role as they collectively approached the single prey. For group type 2, the 1 predator to 1 prey ratio increased the chance of the strategy dispersing given an increased probability of distraction from a passing prey. In the other group types tested a higher predator to prey ratio reduced the number of predators that collectively approached the prey at any given time, thus increasing the likelihood of unhindered dynamic adoption of a behavioral role in the role-switcher strategy. It is theorized that behavioral specialization for role switching emerged as an indirect result of interference that occurred when at least three predators collectively approached a prey. Such interference was observed in the single pool experiments and often caused emergent strategies to fail prematurely, thereby making it more difficult for such strategies using at least three predators to be selected for and propagated by the evolutionary process. Where as, the role-switcher strategy was able to achieve a high team fitness and prey-capture time, it was at best only able to slow the prey, and never completely immobilizing the prey in experiments testing group types 2 through to 5. This is reflected in figure 5, which presents a relatively higher average prey capture time for experiments testing group types 1 and 6. Thus, the dynamic adoption of roles was only effective where the predator to prey ratio was sufficiently high, though not so high as in the case of group type 5 where an excess of physical interference between predators prevented the role­ switcher strategy from regularly forming.

Multiple Pools: In experiments using the multiple pools approach only a single cooperative prey-capture strategy emerged. This strategy was classified as a derivative of the role-switcher strategy using at least three predators that was observed in the plasticity experiments. Though the multiple­ pools role-switcher used a genetic based specialization. In the plasticity experiments the adoption of specialized behaviour was dependent upon the positions of the predators at a given time, where as in the multiple pools experiments, different predators initially behaved differently and assumed genetically pre-determined roles prior to engaging in the multiple pools version of the role-switcher prey-capture strategy. That is, one predator always assumed the role of the knocker while the others always assumed the role of a flanker, or that of an idle predator. Idle predators, for example predator P4 in figure 8, served the purpose of reducing any potential interference between predators as they collectively approach a prey. Idle predators also increased the chance of success of the prey-capture strategy via limiting the number of predators that constituted the strategy. The fact that the predators were genetically different is one explanation for the evolution of specialized behavioural roles that complemented each other in the emergence of the multiple pools role switcher strategy. In the experiments testing group type 6, two specialized sub­ groups of predators, comprising two groups of four predators emerged.

The effectiveness of these two specialized sub-groups is illustrated in figures 4 and 5, which present a relatively high average fitness and prey-capture time for all group types, comparative to the single pool, rule-based and plasticity approaches. Note that as with the plasticity approach, the multiple pools approach is more effective at exploiting an environment containing at least two prey via the formation of two specialized predator sub-groups. Thus, the multiple pools approach facilitated the evolution of specialized predator sub-groups to simultaneously capture two prey, where genetic based specialization proved to be more effective, in terms of measures for fitness scored and prey capture time. This comparison was made with the dyna~ic assumption of behavioral roles as done by predators usmg the plasticity approach.

5 Conclusions

This paper presented a set of experiments testing three different artificial evolution approaches and a rule-based approach for the synthesis of cooperative behaviour wit~in a team of predators, where the task was to cooperatively capture at least two prey. Results compared the perform~nce of these approaches for six different group configuratiOns. The comparison was in terms of two measures designed to quantify the efficacy of emergent cooperative prey capture strategies. These measures were predator fitness and prey­ capture time. Results presented indicated the multiple pools approach to be superior in terms of these two measures for all group types tested. The superiority of the multiple pools approach was found to be a result of a genetic form of behavioral specialization that assigned behavioral roles at the beginning a predators lifetime. The multiple pools approach also facilitated the evolution of two specialized sub-groups of predators in scenarios using at least two prey. Evolution of these sub-groups improved the effectiveness of these strategies in terms of higher team fitness and prey capture time, comparative to the rule-based, single pool and plasticity approaches. Specifically, the specialized sub­ groups aided in reducing interference between predators as they collectively approached a prey.

A comparison with other evolution of cooperation approaches in the pursuit-evasion domain [Denzinger and Fuchs, 1996], [Haynes and Sen, 1996] and [Yong and Miikkulainen, 200 l] is difficult given the real world nature of the experiments described in this paper. Though the robots were simulated, the environment was a continuous domain and the simulation incorporated noise in sensory data, namely confused infrared sensor readings resulting from two or more Khepera's being in close proximity to each other. This noisy sensor data was a key reason for interference between multiple predators as they collectively approached a prey. Also, a continuous enviro~en~ does ~ot allow for the selection of distinct sets of sttuatwn/actlon values that are possible in grid world implementations [Denzinger and Fuchs, 1996] where a finite set of actions and resultant outcomes can be defined. While, the emergence of cooperation is simpler to analyze in these grid world domains, they are limited by their own implementations, so the study of mechanisms that facilitate emergent cooperation such as behavioral specialization is limited to trivial situations.