An autonomous navigation problem is considered, whereby a traveler aims at traversing an environment in which an adversary sets an ambush. A two-player zero-sum game is introduced describing the players’ initial strategy based on the traveler’s initial location and desired goal, and the description of the environment. The process is single step in the sense that agents do not reevaluate their strategy after the traveler has started moving. The players’ strategies are computed as probabilistic distributions, a realization of which is the path chosen by the traveler and the ambush location chosen by the ambusher. 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 subclasses of games in which the reward function for the ambusher is uniform over the environment. To relax the assumptions for the computation of the players’ optimal strategies, a sampling-based approach is proposed, inspired by sampling-based motion-planning techniques. Given a uniform reward function for the ambusher, optimal strategies of the sampling-based ambush game are proven to converge to the optimal strategy of the continuous ambush game. 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 nonuniform reward functions for the ambusher.
Optimal Player Policies for Continuous Ambush Games
Journal of Guidance, Control, and Dynamics ; 41 , 9 ; 1963-1975
2018-07-11
13 pages
Article (Journal)
Electronic Resource
English
NTIS | 1994
Ambush. The Road War in Afghanistan
NTIS | 1988
|An Attempted Amateur Ambush of Supersports 200
British Library Online Contents | 1997
Contact - Ambush (VHS 1/2 inch) (Video)
NTIS | 1966
Mine Resistant Ambush Protected Vehicle, A Case Study
NTIS | 2008
|