Efficient Algorithm for a Visibility-Based Surveillance-Evasion Game.

摘要

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. Compared to closed-loop (feedback strategy) games which require solving a PDE in high dimensions, we demonstrate that the static game can be solved directly in the state space by the proposed PDE-based technique. This results in significant savings in both memory and computational cost, at the expense of a simpler information pattern that is more conservative towards one player. 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.