Visibility-Based Pursuit-Evasion with Probabilistic Evader Models
Nicholas M. Stiffler, Jason M. O'Kane
Proc. IEEE International Conference on Robotics and Automation, 2011
Abstract
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.
Download
BibTeX
@inproceedings{StiOKa11,
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
Automation},
year = {2011},
}
Mon Apr 30 13:52:25 EDT 2012