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

Nicholas M. Stiffler and Jason M. O'Kane
In Proc. IEEE International Conference on Robotics and Automation
To appear

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.

  author = {Nicholas M. Stiffler and Jason M. O'Kane},
  booktitle = {Proc. IEEE International Conference on Robotics and
  note = {To appear},
  title = {Asymptotically-Optimal Multi-Robot Visibility-Based Pursuit-
  year = {2024}

O'Kane's home page
O'Kane's publication list
Last updated 2024-03-28.