UC Merced

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.