Multi-robot pursuit-evasion

Abstract

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