Accepted version, Autonomous Robots The final publication is available at springerlink.com Distributed Pursuit-Evasion without Mapping or Global Localization via Local Frontiers

Abstract This paper addresses a visibility-based pursuit-evasion problem in which a team of mobile robots with limited sensing and communication ca-pabilities must coordinate to detect any evaders in an unknown, multiply-connected planar environment. Our distributed algorithm to guarantee evader detec-tion is built around maintaining complete coverage of the frontier between cleared and contaminated re-gions while expanding the cleared region. We detail a novel distributed method for storing and updating this frontier without building a map of the environment or requiring global localization. We demonstrate the functionality of the algorithm through simulations in realistic environments and through hardware experi-ments. We also compare Monte Carlo results for our algorithm to the theoretical optimum area cleared as a function of the number of robots available.