This dissertation examines the problem of designing large scale
multi-robot systems for pursuit-evasion tasks, which involves the detection of all
targets initially located in some environment of interest. We consider targets that
are omniscient and have unbounded speed. Robots, however, are very restricted
in their capabilities and have only limited sensing and communication range. We
develop theory to describe the problem and algorithms to coordinate a large team
of robots to solve the pursuit-evasion task.
One main contribution is a rigorous graph model of multi-robot pursuitevasion,
called Graph-Clear, complementing existing literature on graph-searching.
We determine its complexity and provide algorithms and extensions for a variety
of scenarios. A second contribution is a model for multi-robot pursuit-evasion
in two dimensional environments, called Line-Clear, that abstracts the sensing
capabilities of the robot team to the ability to sense on lines between obstacles
and thereby detect targets. We present terminology and algorithms that enable
the coordination of the movement of such lines while attempting to minimize
the number of robots needed to cover these lines with sensors. To improve the
applicability of the proposed models we also present two automated methods
that extract instances of Graph-Clear and Line-Clear from grid and polygonal
maps. These methods are then combined with the algorithms for Graph-Clear
and Line-Clear to enable the coordination of real and simulated robots for the
detection of all targets within sample environments. We also extend the approach
to an online version that does not require a map of the environment and works
with simple robots, imperfect control, no localization and limited communication
range.