Time-Dependent Surveillance-Evasion Games
Authors
- Elliot Cartee, Cornell University
- Lexiao Lai, University of Hong Kong
- Qianli Song, University of Hong Kong
- Alexander Vladimirsky, Cornell University
Abstract
Surveillance-Evasion (SE) games form an important class of adversarial trajectory-planning problems. We consider time-dependent SE games, in which an Evader is trying to reach its target while minimizing the cumulative exposure to a moving enemy Observer. That Observer is simultaneously aiming to maximize the same exposure by choosing how often to use each of its predefined patrol trajectories. Following the framework introduced here, we develop efficient algorithms for finding the Nash Equilibrium policies for both players by blending techniques from semi-infinite game theory, convex optimization, and multiobjective dynamic programming on continuous planning spaces. We illustrate our method on several examples with Observers using omnidirectional and angle-restricted sensors on a domain with occluding obstacles.
Paper
E. Cartee, L. Lai, Q. Song and A. Vladimirsky, "Time-Dependent Surveillance-Evasion Games," 2019 IEEE 58th Conference on Decision and Control (CDC), Nice, France, 2019, pp. 7128-7133, doi: 10.1109/CDC40024.2019.9029329
Source Code
Examples
Acknowledgements
The authors are indebted to Marc Gilles, whose algorithms and implementation for the stationary case served as a foundation for this work. The source code for that project can be found on Github here. The authors are also grateful to Casey Garner and Tristan Reynoso for their help in implementation and testing during the summer REU-2018 program at Cornell University.
Much of this work was conducted in an REU program, partially supported by the NSF-RTG award (DMS-1645643). The 1st and 4th authors were also supported by the NSF ATD award (DMS-1738010). The last author's work is also supported by the Simons Foundation Fellowship.