Pursuit-evasion

Pursuit-evasion

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 (see e.g. Isaacs 1965). In 1976, 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.

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 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. 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 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 is a variant of the pursuit-evasion problem.

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.

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. 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 (Isaacs 1965).

References

*cite journal
author = Ellis, J.; Sudborough, I.; Turner, J.
year = 1994
title = The vertex separation and search number of a graph
journal = Information and Computation
volume = 113 | issue = 1 | pages = 50–79
doi = 10.1006/inco.1994.1064

*cite book
author = Isaacs, R.
authorlink = Rufus Isaacs (game theorist)
year = 1965
title = Differential Games: A Mathematical Theory with Applications to Warfare and Pursuit, Control and Optimization
publisher = John Wiley & Sons
location = New York

*cite journal
author = Kiriousis, M.; Papadimitriou, C.
year = 1986
title = Searching and pebbling
journal = Theoretical Computer Science
volume = 42 | issue = 2 | pages = 205–218
doi = 10.1016/0304-3975(86)90146-5

*cite journal
author = Nowakowski, R.; Winkler, P.
year = 1983
title = Vertex-to-vertex pursuit in a graph
journal = Discrete Mathematics
volume = 43
pages = 235–239
doi = 10.1016/0012-365X(83)90160-7

*cite conference
author = Parsons, T. D.
authorlink = Torrence Parsons
title = Pursuit-evasion in a graph
booktitle = Theory and Applications of Graphs
year = 1976
publisher = Springer-Verlag
pages = 426–441

*cite journal
author = Seymour, P.; Thomas, R.
year = 1993
title = Graph searching, and a min-max theorem for tree-width
journal = Journal of Combinatorial Theory, Series B
volume = 58 | issue = 1 | pages = 22–33
doi = 10.1006/jctb.1993.1027

*cite journal
author = Vidal et al.;
year = 2002
title = Probabilistic pursuit-evasion games: theory, implementation, and experimental evaluation
journal = IEEE Transactions on Robotics and Automation
volume = 18| issue = 5 | pages = 662–669
doi = 10.1109/TRA.2002.804040

*cite journal
author = Chung and Furukawa;
title = A Reachability-Based Strategy for the Time-Optimal Control of Autonomous Pursuers
journal = Engineering Optimization
pages = To Appear [http://cmr.mech.unsw.edu.au/people/AlexChung/cfchung.htm]

*cite conference
author = Hespanha et al.
authorlink = Hespanha et al.
title = Multiple-agent probabilistic pursuit-evasion games
booktitle = Proceedings of the 38th IEEE Conference on Decision and Control.
year = 1999
pages = 2432-2437


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Need for Speed: Most Wanted — En este artículo sobre videojuegos se detectaron los siguientes problemas: Necesita ser wikificado conforme a las convenciones de estilo de Wikipedia. Carece de fuentes o referencias que aparezcan en una fuente acreditada …   Wikipedia Español

  • Need for Speed: Most Wanted — North American cover art for Windows version Developer(s) EA Black Box, EA Redwood Shores, Ideaworks Game Studio (Mobile Version) Publi …   Wikipedia

  • Torrence Parsons — Torrence Douglas Parsons (1941 ndash;1987) was an American mathematician.He worked mainly in graph theory, and is known for introducing a graph theoretic view of pursuit evasion problems (Parsons 1976, 1978). He obtained his Ph.D. from Princeton… …   Wikipedia

  • Rufus Isaacs (game theorist) — Rufus Philip Isaacs (1914 1981) was a game theorist especially promenent in the 1950s and 1960s with his work on differential games. He worked for the RAND Corporation from 1948 until winter 1954/1955. His investigation stemmed from classic… …   Wikipedia

  • Differential game — In game theory, differential games are a group of problems related to the modeling and analysis of conflict in the context of a dynamical system. The problem usually consists of two actors, a pursuer and an evader, with conflicting goals. The… …   Wikipedia

  • Список эпизодов сериала «4исла» — «4исла» (англ. Numb3rs)  детективный телевизионный сериал, созданный Николасом Фалаччи и Шерил Хьютон. Премьера телесериала состоялась 23 января 2005 года, 18 мая 2010 года CBS закрыл сериал …   Википедия

  • Tree decomposition — A graph with eight vertices, and a tree decomposition of it onto a tree with six nodes. Each graph edge connects two vertices that are listed together at some tree node, and each graph vertex is listed at the nodes of a contiguous subtree of the… …   Wikipedia

  • Princess and monster game — The princess and monster game is a pursuit evasion game played by two players on a graph. The game was devised by Rufus Isaacs and published in his book Differential games . [R. Isaacs, Differential Games: A Mathematical Theory with Applications… …   Wikipedia

  • Topological game — A topological game is an infinite positional game of perfect information played between two players on a topological space. Players choose objects with topological properties such as points, open sets, closed sets and open coverings. Time is… …   Wikipedia

  • Yu-Chi Ho — This article is about the Chinese American mathematician. For|the writer and mayor of St Paul|Laurence C. HodgsonInfobox Scientist name = Yu Chi Larry Ho caption = birth date = birth date and age|1934|3|1 birth place = Shanghai, China death date …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”