Discrete and Continuous ambush games: optimal policies and approximate solutions
This work addresses navigation security for autonomous systems in adversarial settings, presenting a novel game-theoretic approach with practical computational methods.
The paper tackles the problem of autonomous navigation in adversarial environments by modeling it as a two-player zero-sum game, deriving analytical optimal policies and showing that the optimal value relates to maximum flow in both discrete and continuous cases, with a linear program introduced for non-uniform reward functions.
We consider an autonomous navigation problem, whereby a traveler aims at traversing an environment in which an adversary tries to set an ambush. A two players zero sum game is introduced. Players' strategies are computed as random path distributions, a realization of which is the path chosen by the traveler. A parallel is drawn between the discrete problem, where the traveler moves on a network, and the continuous problem, where the traveler moves in the plane. Analytical optimal policies are derived. Using assumptions from the Minimal Cut - Maximal Flow literature, the optimal value of the game is shown to be related to the maximum flow on the environment in both the discrete and the continuous cases, when the reward function for the ambusher is uniform. A linear program is introduced that allows for the computation of optimal policies, compatible with non-uniform reward functions. In order to relax the assumptions for the computation of the players' optimal strategies of the continuous game, a network is created, inspired by recently introduced sampling based motion planning techniques, and the linear program is adapted for continuous constraints.