Asymptotically-Optimal Multi-Robot Visibility-Based Pursuit-Evasion
Authors:
- 13 May 2024
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 10366-10373
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.Keywords
This publication has 41 references indexed in Scilit:
- Motion Planning by Sampling in Subspaces of Progressively Increasing DimensionJournal of Intelligent & Robotic Systems, 2020
- dRRT*: Scalable and informed asymptotically-optimal multi-robot motion planningAutonomous Robots, 2019
- Heuristics for the Multi-Robot Worst-Case Pursuit-Evasion ProblemIEEE Access, 2017
- Sparse Methods for Efficient Asymptotically Optimal Kinodynamic Planning2015
- Distributed pursuit-evasion without mapping or global localization via local frontiersAutonomous Robots, 2011
- A robotic system for monitoring carp in Minnesota lakesJournal of Field Robotics, 2010
- Search and Rescue Robotics2008
- Probabilistic roadmaps for path planning in high-dimensional configuration spacesIEEE Transactions on Robotics and Automation, 1996
- Pursuit-evasion in a graph1978
- A note on two problems in connexion with graphsNumerische Mathematik, 1959