Shortest Paths for Visibility-Based Pursuit-Evasion

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


We present an algorithm that computes a minimal-cost pursuer trajectory for a single pursuer to solve the visibility-based pursuit-evasion problem in a simply-connected two-dimensional environment. This algorithm improves upon the known algorithm of Guibas, Latombe, LaValle, Lin, and Motwani, which is complete but not optimal. Our algorithm uses a Tour of Segments (ToS) subroutine to construct a pursuer path that minimizes the distance traveled by the pursuer while guaranteeing that all evaders in the environment will be captured. We have implemented our algorithm in simulation and provide results.


  author       = {Nicholas M. Stiffler and Jason M. O'Kane},
  title        = {Shortest Paths for Visibility-Based Pursuit-Evasion},
  booktitle    = {Proc. IEEE International Conference on Robotics and
  year	       = {2012}

O'Kane's home page
O'Kane's publication list

Wed Mar 4 12:52:19 EST 2020