Pursuit on a graph under partial information from sensors
Shreyas Sundaram, Krishna Kalyanam, David W. Casbeer · 2017
We consider a class of pursuit-evasion problems where an evader enters a directed acyclic graph and attempts to reach one of the terminal nodes. A pursuer enters the graph at a later time and attempts to capture the evader before it reaches a terminal node. The pursuer can only obtain information about the evader's path via sensors located at each node in the graph; the sensor measurements are either green or red (indicating whether or not the evader has passed through that node). We first show that it is NP-hard to determine whether the pursuer can enter with some nonzero delay and still be guaranteed to capture the evader. We further show that it is NP-hard to approximate (within any constant factor) the largest delay at which the pursuer can enter and still guarantee capture. Finally, we provide a linear-time algorithm to compute the maximum pursuer delay for a class of node-sweeping policies on bounded-degree tree networks.