A Differential Game Approach to Planning in Adversarial Scenarios: A Case Study on Capture-the-Flag
Haomiao Huang, Jerry Ding, Wei Zhang and Claire Tomlin
Air Force Office of Scientific Research and ONR/MURI
Capture-the-flag is a challenging and interesting game that is also a useful proxy for many real-world problems in robotics and other application areas. The game is adversarial, with multiple, potentially competing, objectives. This interplay between different factors makes the problem complex, even in the case of only two players. In order for the analysis to be tractable, previous approaches often make some limiting assumptions upon player actions. In this paper, we present a framework for analyzing and solving a two-player capture-the-flag game as a zero-sum differential game. Our problem formulation allows each player to make decisions rationally based upon the current player positions, with only an upper bound on the movement speeds. Using Hamilton-Jacobi reachability analysis, we compute winning regions for each player as subsets of the joint configuration space and derive the corresponding winning strategies. Simulation results are presented along with implications of the work as a tool for automation-aided decision-making for humans and mixed human-robot teams.