2021/02/17 by Trevor Olsen, Olsen, Trevor, Anne M. Tumlin +5
Engineering · #Computational Fluid Dynamics and Aerodynamics #FOS: Computer and information sciences #Guidance and Control Systems #Military Defense Systems Analysis #Robotics (cs.RO)
paper · pdf · doi:10.48550/arxiv.2102.09013
openalex publication_date 2021/02/17 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
Given a two-dimensional polygonal space, the multi-robot visibility-based\npursuit-evasion problem tasks several pursuer robots with the goal of\nestablishing visibility with an arbitrarily fast evader. The best known\ncomplete algorithm for this problem takes time doubly exponential in the number\nof robots. However, sampling-based techniques have shown promise in generating\nfeasible solutions in these scenarios. One of the primary drawbacks to\nemploying existing sampling-based methods is that existing algorithms have long\nexecution times and high failure rates for complex environments. This paper\naddresses that limitation by proposing a new algorithm that takes an\nenvironment as its input and returns a joint motion strategy which ensures that\nthe evader is captured by one of the pursuers. Starting with a single pursuer,\nwe sequentially construct Sample-Generated Pursuit-Evasion Graphs to create\nsuch a joint motion strategy. This sequential graph structure ensures that our\nalgorithm will always terminate with a solution, regardless of the complexity\nof the environment. We describe an implementation of this algorithm and present\nquantitative results that show significant improvement in comparison to the\nexisting algorithm.\n