## 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
**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.

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

*Last updated 2020-09-23.*