Asymptotically-Optimal Multi-Robot Visibility-Based Pursuit-Evasion

Abstract

The multi-robot visibility-based pursuit-evasion problem tasks a team of robots with systematically searching an environment to detect (capture) an evader. Previous techniques to generate search strategies for the pursuit team have shown to be either computationally intractable or permit poor solution quality. This paper presents a novel asymptotically optimal algorithm for generating a joint motion strategy for the pursuers. To explore the space of possible pursuer motion strategies, the algorithm utilizes a trio of hierarchical graph data structures that each capture certain elements of the problem such as connectivity (valid single pursuer motion), coordination (multiple pursuer motion), and tracking information (evaluating where an evader may be). The algorithm is inspired by well-known methods in the motion planning literature and inherits its asymptotic optimality from those techniques. In addition, we describe a method that can improve upon solutions found during the formative stages of the main algorithm, using a "fast-forward" approach that foregoes guarantees of asymptotic optimality, implementing heuristics that concentrate future samples into improving the path quality of the nominal solution. The algorithms were validated in simulation and results are provided.