Optimal navigation policy for an autonomous agent operating in adversarial environments

We consider an autonomous vehicle navigation problem, whereby a traveler aims at traversing an environment in which an adversary tries to set an ambush. Optimal strategies are computed as random path distributions, a realization of which is the path chosen by the traveler. Theoretical optimal policies are derived under assumptions from the Minimal Cut-Maximal Flow literature. Numerical approaches to compute such optimal strategies are proposed. These numerical approaches, which borrow from randomized path planning techniques, can be implemented for high-dimensional configuration spaces. The methodology developed allows for the application of ambush games on complex environments for realistic applications regarding vehicle routing in adversarial settings.