Visibility-Based Pursuit-Evasion with Probabilistic Evader Models

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


We propose an algorithm for a visibility-based pursuit-evasion problem in a simply-connected two-dimensional environment, in which a single pursuer has access to a probabilistic model describing how the evaders are likely to move in the environment. The application of our algorithm can be best viewed in the context of search and rescue: Although the victims (evaders) are not actively trying to escape from the robot, it is necessary to consider the task of locating the victims as a pursuit-evasion problem to obtain a firm guarantee that all of the victims are found. An algorithm is presented that draws sample evader trajectories from the probabilistic model to compute a plan that lowers the Expected Time to Capture the evaders without drastically increasing the Guaranteed Time to Capture the evaders. We introduce a graph structure that takes advantage of the sampled evader trajectories to compute a path that would "see" all the evaders if they followed only those trajectories in our sampled set. We then use a previous technique to append our path with actions that provide a complete solution for the visibility-based pursuit-evasion problem. The resulting plan guarantees that all evaders are located, even if they do not obey the given probabilistic motion model. We implemented the algorithm in a simulation and provide a quantitative comparison to existing methods.



  title        = {Visibility-Based Pursuit-Evasion with Probabilistic
		 Evader Models},
  author       = {Nicholas M. Stiffler and Jason M. O'Kane},
  booktitle    = {Proc. IEEE International Conference on Robotics and
  year	       = {2011}

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

Wed Sep 20 09:19:46 EDT 2017