Keywords
Algorithms, TSP, Traveling Salesman, Pursuit Evasion
Presentation Type
Poster
Research Abstract
Unmanned Aerial Vehicles (UAV) have many military and civilian applications, one of which is monitoring a given area (such as a road network) for threats. An important question in this application is to determine the latest time to dispatch UAVs for the guaranteed capture of threats attempting to travel through the network. In this work, we consider a pursuit evasion scenario with multiple pursuers (UAVs) trying to catch a single evader (ground vehicle), where information about the evader’s path is provided by ground sensors. In this scenario, we consider the problem of finding the maximum delay with which the pursuers can enter the network and still guarantee capture of the evader; we call this the Maximum Pursuer Delay Problem, or MPDP. We consider policies that split the graph into multiple instances of the single pursuer MPDP. We provide a recursive algorithm to calculate such policies by splitting the graph into multiple forests and assigning a pursuer to each forest. We also propose a dynamic programming solution that considers a class of “sweeping” policies by K pursuers and has polynomial time-complexity in the number of pursuers.
Session Track
Sensing and Measurement
Recommended Citation
Blake Wilson, Shreyas Sundaram, and Amritha Prasad,
"Pursuit Evasion with Multiple Pursuers : Capturing a Ground Vehicle on a Road Network with Multiple Drones"
(August 3, 2017).
The Summer Undergraduate Research Fellowship (SURF) Symposium.
Paper 54.
https://docs.lib.purdue.edu/surf/2017/presentations/54
Included in
Pursuit Evasion with Multiple Pursuers : Capturing a Ground Vehicle on a Road Network with Multiple Drones
Unmanned Aerial Vehicles (UAV) have many military and civilian applications, one of which is monitoring a given area (such as a road network) for threats. An important question in this application is to determine the latest time to dispatch UAVs for the guaranteed capture of threats attempting to travel through the network. In this work, we consider a pursuit evasion scenario with multiple pursuers (UAVs) trying to catch a single evader (ground vehicle), where information about the evader’s path is provided by ground sensors. In this scenario, we consider the problem of finding the maximum delay with which the pursuers can enter the network and still guarantee capture of the evader; we call this the Maximum Pursuer Delay Problem, or MPDP. We consider policies that split the graph into multiple instances of the single pursuer MPDP. We provide a recursive algorithm to calculate such policies by splitting the graph into multiple forests and assigning a pursuer to each forest. We also propose a dynamic programming solution that considers a class of “sweeping” policies by K pursuers and has polynomial time-complexity in the number of pursuers.