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. We present an algorithm 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.
展开▼
