Ambush games in discrete and continuous environments

Abstract

We consider an autonomous navigation problem, whereby a traveler aims at traversing an environment in which an adversary sets an ambush. A two players zero- sum game is introduced, describing the initial strategy of the traveler and the ambusher based on a description of the environment and the traveler initial location and desired goal. The process is single-step in the sense that agents do not reevaluate their strategy after the traveler has started moving. Players’ strategies are computed as probabilistic path distributions, a realization of which is the path chosen by the traveler and the ambush location chosen by the ambusher. A parallel is drawn between the discrete problem, where the traveler moves on a network, and the continuous problem, where the traveler moves in a compact subset of R2. Analytical optimal policies are derived. Assumptions from the Minimal Cut - Maximal Flow literature for continuous domains are used. The optimal value of the game is shown to be related to the maximum flow on the environment for sub-classes of games where the reward function for the ambusher is uniform. This proof is detailed in the discrete and continuous setups. In order to relax the assumptions for the computation of the players’ optimal strategies, a sampling-based approach is proposed, inspired by re- cent sampling-based motion planning techniques. Given a uniform reward function for the ambusher, optimal strategies of the sampled ambush game are proven to converge to the optimal strategy of the continuous ambush game under some sampling and connectivity constraints. A linear program is introduced that allows for the computation of optimal policies. The sampling-based approach is more general in the sense that it is compatible with constrained motion primitives for the traveler and non-uniform reward functions for the ambusher. The sampling-based game is used to create example applications for situ- ations where no analytic solution of the Continuous Ambush Game have been identified.This leads to more interesting games, applicable to real-world robots using modern motion planning algorithms. Examples of such games are setups where the traveler’s motion satis- fies Dubins’ kinematic constraints and setups where the reach of the ambusher is dependent on the speed of the traveler.