×

An efficient algorithm for a visibility-based surveillance-evasion game. (English) Zbl 1307.91036

Summary: 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>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.

MSC:

91A24 Positional games (pursuit and evasion, etc.)
91A23 Differential games (aspects of game theory)
49N75 Pursuit and evasion games
93B52 Feedback control
93B40 Computational methods in systems theory (MSC2010)
65K10 Numerical optimization and variational techniques
68T40 Artificial intelligence for robotics

Software:

ToolboxLS
PDFBibTeX XMLCite
Full Text: DOI