Visibility-Based Pursuit-Evasion with Probabilistic Evader Models

<p>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.</p>

Name thesis:degree_name

M.S.

Level thesis:degree_level

Campus Access Thesis

Discipline thesis:degree_discipline

Computer Science and Engineering

Year

2012

Author dc:creator

• Stiffler, Nicholas Michael

Contributors dc:contributor

• Jason M O'Kane

• Computer Sciences
• Electrical and Computer Engineering
• Engineering
• Physical Sciences and Mathematics
• evader models
• probabilistic
• pursuit-evasion
• robotics
• visibility

Statement dc:rights

• © 2012, Nicholas Michael Stiffler

Repository record dc:identifier

https://scholarcommons.sc.edu/etd/802

OAI identifier oai:identifier

oai:scholarcommons.sc.edu:etd-1803