Automation-Assisted Capture-the-Flag: A Differential Game Approach

Abstract

Capture-the-flag is a complex, challenging game that is a useful proxy for many problems in robotics and other application areas. The game is adversarial, with multiple, potentially competing, objectives. This interplay among different factors makes the problem complex, even in the case of only two players. To make analysis tractable, previous approaches often make various 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 according to the current player positions, assuming only an upper bound on the movement speeds. Using numerical solutions to Hamilton-Jacobi-Isaacs equations, we compute winning regions for each player as subsets of the joint configuration space and derive the corresponding winning strategies. The computational method and simulations are presented, along with experiments with human agents in the Berkeley autonomy and robotics in capture-the-flag testbed. These experiments demonstrate the use of the solutions in realistic conditions and highlight their potential applications in automation-aided decision making for humans and mixed human-robot teams.