next up previous
Next: Domain Issues Up: Organization of Existing Work Previous: Organization of Existing Work

The Predator/Prey (``Pursuit'') Domain

The Predator/Prey, or ``Pursuit'' domain (hereafter referred to as the ``pursuit domain''), is an appropriate one for illustration of MAS because it has been studied using a wide variety of approaches and because it has many different instantiations that can be used to illustrate different multiagent scenarios. It is not presented as a complex real-world domain, but rather as a toy domain that helps concretize many concepts. For discussion of a domain that has the full range of complexities characteristic of more real-world domains, see Section 7.

The pursuit domain was introduced by Benda et al. [9]. Over the years, researchers have studied several variations of its original formulation. In this section, a single instantiation of the domain is presented. However, care is taken to point out the parameters that can be varied.

The pursuit domain is usually studied with four predators and one prey. Traditionally, the predators are blue and the prey is red (black and grey respectively in Figure 4). The domain can be varied by using different numbers of predators and prey.

Figure 4: A particular instantiation of the pursuit domain. Predators are black and the prey is grey. The arrows on top of two of the predators indicate possible moves.

The goal of the predators is to ``capture'' the prey, or surround it so that it cannot move to an unoccupied position. A capture position is shown in Figure 4. If the world has edges, fewer than four predators can capture the prey by trapping it against an edge or in a corner. Another possible criterion for capture is that a predator occupies the same position as the prey. Typically, however, no two players are allowed to occupy the same position.

As depicted in Figure 4, the predators and prey move around in a discrete, grid-like world with square spaces. They can move to any adjacent square on a given turn. Possible variations include grids with other shapes as spaces (for instance hexagons) or continuous worlds. Within the square game, players may be allowed to move diagonally instead of just horizontally. The size of the world may also vary from an infinite plane to a small, finite board with edges. The world pictured in Figure 4 is a toroidal world: the predators and prey can move off one end of the board and come back on the other end. Other parameters of the game that must be specified are whether the players move simultaneously or in turns; how much of the world the predators can see; and whether and how the predators can communicate.

Finally, in the original formulation of the domain, and in most subsequent studies, the prey moves randomly: on each turn it moves in a random direction, staying still with a certain probability in order to simulate being slower than the predators. However, it is also possible to allow the prey to actively try to escape capture. As is discussed in Section 5, there has been some research done to this effect, but there is still much room for improvement.

Table 3: Variable parameters in the pursuit domain

The parameters that can be varied in the pursuit domain are summarized in Table 3.

The pursuit domain is a good one for the purposes of illustration because it is simple to understand and because it is flexible enough to illustrate a variety of scenarios. The possible actions of the predators and prey are limited and the goal is well-defined. In terms of the reasons to use MAS as presented in Table 1, the pursuit domain does not necessarily require MAS. But in certain instantiations it can make use of the parallelism, robustness, and simpler programming offered by MAS.

In the pursuit domain, a single-agent approach is possible: the agent can observe the positions of all four predators and decide how each of them should move. Since the prey moves randomly rather than intentionally, it is not associated with any agent. Instead it is considered part of the environment as shown in Figure 5. It is also possible to consider DPS approaches to the pursuit domain by breaking the task into subproblems to be solved by each predator. However, most of the approaches described here model the predators as independent agents with a common goal. Thus, they comprise a multiagent system.

Figure 5: The pursuit domain with just a single agent. One agent controls all predators and the prey is considered part of the environment.

For each of the multiagent scenarios presented below, a new instantiation of the pursuit domain is defined. Their purpose is to illustrate the different scenarios within a concrete framework.

next up previous
Next: Domain Issues Up: Organization of Existing Work Previous: Organization of Existing Work

Peter Stone
Wed Sep 24 11:54:14 EDT 1997