Pursuit-evasion is a family of problems in mathematics

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

 and computer science

Computer science

Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

 in which one group attempts to track down members of another group in an environment. Early work on problems of this type modeled the environment geometrically. In 1976, Parsons

Torrence Parsons

Torrence Douglas Parsons was an American mathematician.He worked mainly in graph theory, and is known for introducing a graph-theoretic view of pursuit-evasion problems . He obtained his Ph.D. from Princeton University in 1966 under the supervision of Albert W. Tucker.-Further reading:Memorial...

 introduced a formulation whereby movement is constrained by a graph

Graph (mathematics)

In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...

. The geometric formulation is sometimes called continuous pursuit-evasion, and the graph formulation discrete pursuit-evasion (also called graph searching). Current research is typically limited to one of these two formulations.

Discrete formulation

In the discrete formulation of the pursuit-evasion problem, the environment is modeled as a graph.

Problem definition

There are innumerable possible variants of pursuit-evasion, though they tend to share many elements. A typical, basic example is as follows (cops and robber games): Pursuers and evaders occupy nodes of a graph. The two sides take alternate turns, which consist of each member either staying put or moving along an edge to an adjacent node. If a pursuer occupies the same node as an evader the evader is captured and removed from the graph. The question usually posed is how many pursuers are necessary to ensure the eventual capture of all the evaders.

Often the movement rules are altered by changing the velocity of the evaders. This velocity is the maximum number of edges that an evader can move along in a single turn. In the example above, the evaders have a velocity of one. At the other extreme is the concept of infinite velocity, which allows an evader to move to any node in the graph so long as there is a path

Path (graph theory)

In graph theory, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence. A path may be infinite, but a finite path always has a first vertex, called its start vertex, and a last vertex, called its end vertex. Both of them...

 between its original and final positions that contains no nodes occupied by a pursuer. Similarly some variants arm the pursuers with "helicopters" which allow them to move to any vertex on their turn.

Other variants ignore the restriction that pursuers and evaders must always occupy a node and allow for the possibility that they are positioned somewhere along an edge. These variants are often referred to as sweeping problems, whilst the previous variants would fall under the category of searching problems.

Variants

Several variants are equivalent to important graph parameters. Specifically, finding the number of pursuers necessary to capture a single evader with infinite velocity in a graph G (when pursuers and evader are not constrained to move turn by turn, but move simultaneously) is equivalent to finding the treewidth of G, and a winning strategy for the evader may be described in terms of a haven

Haven (graph theory)

In graph theory, a haven is a way of describing a strategy for an evader to win a certain type of pursuit-evasion game on an undirected graph. Havens were first introduced by ; they may also be used to characterize the treewidth of graphs and to prove the existence of small separators on...

 in G. If this evader is invisible to the pursuers then the problem is equivalent to finding the pathwidth or vertex separation. Finding the number of pursuers necessary to capture a single invisible evader in a graph G in a single turn (that is, one movement by the pursuers from their initial deployment) is equivalent to finding the size of the minimum dominating set

Dominating set

In graph theory, a dominating set for a graph G =  is a subset D of V such that every vertex not in D is joined to at least one member of D by some edge...

 of G, assuming the pursuers can initially deploy wherever they like (this later assumption holds when pursuers and evader are assumed to move turn by turn).

The board game Scotland Yard

Scotland Yard (board game)

Scotland Yard is a board game in which a team of players, as "police", cooperate to track down a player controlling a "criminal" around a board representing the streets of London. It is named after Scotland Yard, the headquarters of London's Metropolitan Police Service...

 is a variant of the pursuit-evasion problem.

Complexity

The complexity of several pursuit-evasion variants, namely how many pursuers are needed to clear a given graph and how a given number of pursuers should move on the graph to clear it with either a minimum sum of their travel distances or minimum task-completion time, has been studied by R. Borie, C. Tovey and S. Koenig.

Multi-Player Pursuit-Evasion Games

Solving multi-player pursuit-evasion games has also received increased attention. See R Vidal et al., Chung and Furukawa http://cmr.mech.unsw.edu.au/people/AlexChung/cfchung.htm, Hespanha et al. and the references therein. Marcos A. M. Vieira and Ramesh Govindan and Gaurav S. Sukhatme provided an algorithm that computes the minimal completion time strategy for pursuers to capture all evaders when all players make optimal decisions based on complete knowledge. This algorithm can also be applied to when evader are significantly faster than pursuers. Unfortunately, these algorithms do not scale beyond a small number of robots. To overcome this problem, Marcos A. M. Vieira and Ramesh Govindan and Gaurav S. Sukhatme design and implement a partition algorithm where pursuers capture evaders by decomposing the game into multiple multi-pursuer single-evader games.

Continuous formulation

In the continuous formulation of pursuit-evasion games, the environment is modeled geometrically, typically taking the form of the Euclidean plane or another manifold

Manifold

In mathematics , a manifold is a topological space that on a small enough scale resembles the Euclidean space of a specific dimension, called the dimension of the manifold....

. Variants of the game may impose maneuverability constraints on the players, such as a limited range of speed or acceleration. Obstacles may also be used.

Applications

One of the initial applications of the pursuit-evasion problem was missile guidance systems formulated by Rufus Isaacs

Rufus Isaacs (game theorist)

Rufus Philip Isaacs was a game theorist especially prominent in the 1950s and 1960s with his work on differential games.-Biography:...

at the RAND Corporation.