There is a family of Cops and Robbers games, played on graphs. I got into this topic through robotic applications
(for more on this see below) and I am slowly discovering a rich mathematical playground. This page is devoted to cops and robbers as well as to their
close relative, graph search. All of these can be seen as versions of the pursuit-evasion problem. I also give several links with
a slant towards robotic applications. Finally, from this page you can download some of my software and papers.
Various Cops and Robber games
"Let G be a finite connected graph. Two players, called cop C and robber R, play a game on
G according to the following rules. First C then R occupy some vertex of G. After that they move
alternately along edges of G. The cop C wins if he succeeds in putting himself on top of the robber
R, otherwise R wins."
This is from the paper "A game of cops and robbers", by M. Aigner and M. Fromme, Discrete Applied Mathematics, vol. 8 (1984), pp. 1-12).
The full paper is available online.
Note that this is just one (perhaps the simplest) version of the game. There are many variants.
For example, there can be more than one cops and/or robbers. Also,
in the above description it is assumed that the cops can see the robber and vice versa.
In another version the robber is invisible. There are versions where the robber is faster than the cops (even infinitely faster).
There is a version where the robber is drunk, i.e. he does not try to escape the cops but simply performs a random walk on the graph.
And so on and so forth. You can use the links in the next section to get started with cops, robbers and graph search; be warned
that these links are just a small sample of a very large bibliography.
Graph Search
"There are [other] problems, besides trying to find someone lost or hiding in a
cave system, that are modelled naturally by [searching] graphs. Searching a road
system for a vehicle that is either moving or parked somewhere is another such
problem. Another problem that can be modelled as a graph [searching] problem,
though it may not be obvious at first sight, is the problem of clearing a complex
system of interconnected pipes that is contaminated by some noxious gas."
This is from the paper "Searching and sweeping graphs: a brief survey", by B. Alspach, Le Matematiche,
Vol. LIX (2004), Fasc. I-II, pp. 5-37. The full paper is
available online
but note that, in this paper, "graph sweeping" is the term for what is usually called graph search
(and, rather confusingly, "graph searching" is the term for what is usually called cops and robbers games).
Similarly to cops and robbers, there is also a large number of graph search variants.
A very good survey (mostly of graph search, but also of cops and robbers) is
this.
Vertex-to-vertex pursuit in a graph, Nowakowski, R. and Winkler, P., Discrete Mathematics, vol. 43, pp. 235--239, 1983. (First seminal paper on cops-and-robbers.)
A game of cops and robbers, Aigner, M. and Fromme, M., Discrete Applied Mathematics, vol. 8, pp. 1-12, 1984. (Second seminal paper on cops-and-robbers.)
Capture of an intruder by mobile agents L. Barriere, P. Flocchini, P. Fraigniaud and N. Santoro, in Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, pp. 200-209, 2002. (A paper on graph search which I read very often.)
GRASTA 2011 (GRASTA is Theory and Applications of Graph Searching Problems, the main conference of graph searchers.)
In the last decade roboticists have used concepts from both the cops and robbers and and graph search literature. Below I give a few links
in this direction. The two theses have very extensive bibliograpies. Most of my papers in the previous section are also robot-centric.
G. Hollinger, A. Kehagias, S. Singh, D. Ferguson ansd S. Srinivasa "Anytime Guaranteed Search using Spanning Trees," tech. report CMU-RI-TR-08-36, Robotics Institute, Carnegie Mellon University, August, 2008.
Last Revised: June 2011
View My Stats
