A complete algorithm for visibility-based pursuit-evasion with multiple pursuers

Abstract We introduce a centralized algorithm for a visibility-based pursuit-evasion problem in a two-dimensional environment for the case of multiple pursuers. The input for our algorithm is an environment represented as a doubly-connected edge list and the initial positions of the pursuers. The output is a joint strategy for the pursuers that guarantees that the evader has been captured, or a statement that no such strategy exists. We create a Cylindrical Algebraic Decomposition(CAD) of the joint configuration space by using polynomials that capture where critical changes can occur to the region of the environment hidden from the pursuers. Then after computing the adjacency graph for the CAD we construct a Pursuit Evasion Graph(PEG) induced by the adjacency graph. A search through the PEG can produce one of the following outcomes: the search can reach a vertex where the pursuers' motions up to this point ensure that the evader has been captured, or the search terminates without finding a solution and produces a statement recognizing that no solution exists.

@inproceedings{StiOKa14,
  author = {Nicholas M. Stiffler and Jason M. O'Kane},
  booktitle = {Proc. IEEE International Conference on Robotics and
               Automation},
  title = {A complete algorithm for visibility-based pursuit-evasion
           with multiple pursuers},
  year = {2014}
}