Volume 26 Issue 3 - Publication Date: 1 March 2007
Surveillance Strategies for a Pursuer with Finite Sensor Range
R. Murrieta-Cid Centro de Investigación en Matemáticas CIMAT, Guanajuato México T. Muppirala, A. Sarmiento, S. Bhattacharya and S. Hutchinson University of Illinois at Urbana-Champaign Urbana, IL 61801 USA
This paper addresses the pursuit–evasion problem of maintaining surveillance by a pursuer of an evader in a world populated by polygonal obstacles. This requires the pursuer to plan collision-free motions that honor distance constraints imposed by sensor capabilities, while avoiding occlusion of the evader by any obstacle. The paper extends the three-dimensional cellular decomposition of Schwartz and Sharir to represent the four-dimensional conf iguration space of the pursuer–evader system, and derive necessary conditions for surveillance (equivalently, suff icient conditions for escape) in terms of this new representation. A game theoretic formulation of the problem is then given, and this formulation is used to characterize optimal escape trajectories for the evader. A shooting algorithm is proposed that f inds these trajectories using the minimum principle. Finally, noting the similarities between this surveillance problem and the problem of cooperative manipulation by two robots, several cooperation strategies are presented that maximize system performance for cooperative motions.
Return to Contents