Pursuit-evasion
Sign in to savePursuit–evasion (variants of which are referred to as cops and robbers and graph searching) is a family of problems in mathematics and computer science 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, Torrence Parsons introduced a formulation whereby movement is constrained by a graph. The geometric formulation is sometimes called continuous pursuit–evasion, and the graph formulation discrete pursuit–evasion (also called graph searching). Current research is typically limite
~6 min read
Encyclopedic overview
10 sectionsContents
- Discrete formulation
- Problem definition
- Variants
- Complexity
- Multi-player pursuit–evasion games
- Continuous formulation
- Applications
- See also
- Notes
- References
Pursuit–evasion (variants of which are referred to as cops and robbers and graph searching) is a family of problems in mathematics and computer science 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, Torrence Parsons introduced a formulation whereby movement is constrained by a graph. 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.
Excerpted from Wikipedia’s “Pursuit-evasion” article, available under the CC BY-SA 4.0 licence.