Strategy Synthesis for Surveillance-Evasion Games with Learning-enabled Visibility Optimization

Strategy Synthesis for Surveillance-Evasion Games with Learning-enabled Visibility Optimization

We study a two-player game with a quantitative surveillance requirement on an adversarial target moving in a discrete state space and a secondary objective to maximize short-term visibility of the environment. We impose the surveillance requirement as a temporal logic constraint. We then use a greedy approach to determine vantage points that optimize a notion of information gain, namely, the number of newly-seen states. By using a convolutional neural network trained on a class of environments, we can efficiently approximate the information gain at each potential vantage point. Subsequent vantage points are chosen such that moving to that location will not jeopardize the surveillance requirement, regardless of any future action chosen by the target. Our method combines guarantees of correctness from formal methods with the scalability of machine learning to provide an efficient approach for surveillance-constrained visibility optimization.

Simulations

We present videos demonstrating the agent's strategies synthesized by our algorithm. The blue circle corresponds to the controlled agent and the orange circle corresponds to the hostile target. Red cells are obstacles that cannot be passed through and obscure vision. Black cells correspond to states the agent cannot see. The video on the left shows an agent with the surveillance objective: always mantain visibility of the target. Notice the agent tends to stay still until it is necessary to move. On the right video, the agent must also patrol the environment, in addition to the surveillance requirement.

Publications

  • Suda Bharadwaj, Louis Ly, Bo Wu, Richard Tsai, and Ufuk Topcu. "Strategy synthesis for surveillance-evasion games with learning-enabled visibility optimization." 2019 Conference on Decision and Control (CDC). IEEE, 2019.