PURSUIT OF A MOVING TARGET WITH KNOWN CONSTANT SPEED ON A DIRECTED ACYCLIC GRAPH UNDER PARTIAL INFORMATION

摘要

We consider the optimal control of a "blind" pursuer searching for an evader moving on a road network with fixed speed toward a set of goal locations. To aid the pursuer and provide feedback information, certain roads in the network have been instrumented with unattended ground sensors (UGSs) that detect the evader's motion. When the pursuer arrives at an instrumented node, the UGS therein informs the pursuer whether and when the evader visited that node. The pursuer is also made aware of the evader's speed. Moreover, the embedded graph comprised of the UGSs as vertices and connecting roads as edges is restricted to being a directed acyclic graph (DAG). The pursuer's motion is not restricted to the road network. In addition, the pursuer can choose to wait/loiter for an arbitrary time at any UGS locationode. At time 0, the evader's entry into the road network is registered at UGS 1, the entry node to the graph. The pursuer also arrives at the entry node after some delay d and is thus informed about the presence of the intruder/evader in the network, whereupon the chase is on the pursuer is tasked with capturing the evader. Capture entails the pursuer and evader being co-located at an UGS location. If this happens, the UGS is triggered, and this information is instantaneously relayed to the pursuer, thereby enabling capture. On the other hand, if the evader reaches one of the exit nodes of the graph without being captured, he is deemed to have escaped. We provide an algorithm that computes the maximum initial delay d for which capture is guaranteed. The algorithm also returns the corresponding optimal pursuit policy.