Communications in Mathematical Sciences

Volume 12 (2014)

Number 7

An efficient algorithm for a visibility-based surveillance-evasion game

Pages: 1303 – 1327



Ryo Takei (Department of Electrical Engineering and Computer Sciences, University of California at Berkeley)

Richard Tsai (Institute for Computational Engineering and Sciences, University of Texas at Austin, Tx., U.S.A.)

Zhengyuan Zhou (Dept. of Electrical Engineering and Dept. of Computer Sciences and Mathematics, University of California at Berkeley)

Yanina Landa


We present an algorithm which computes the value function and optimal paths for a two-player static game, where the goal of one player is to maintain visibility of an adversarial player for as long as possible, and that of the adversarial player is to minimize this time. In a static game both players choose their controls at initial time and run in open-loop for $t \gt 0$ until the end-game condition is met. Closed-loop (feedback strategy) games typically require solving PDEs in high dimensions and thus pose insurmountable computational challenges. We demonstrate that, at the expense of a simpler information pattern that is more conservative towards one player, more memory and computationally efficient static games can be solved iteratively in the state space by the proposed PDE-based technique. In addition, we describe how this algorithm can be easily generalized to games with multiple evaders. Applications to target tracking and an extension to a feedback control game are also presented.


multi-player differential games, visibility, target tracking, motion planning, closed-loop v.s. open-loop, model predictive control

2010 Mathematics Subject Classification

49K35, 68T40, 91A23, 91A24, 91A25, 93A14, 93B40, 93B52

Published 14 May 2014