離散・連続待ち伏せゲーム:最適方策と近似解法
Discrete and Continuous ambush games: optimal policies and approximate solutions
旅行者と待ち伏せ者のゼロサムゲームとして経路選択問題を定式化し、最大流との関係を示すとともに、サンプリングベースの経路計画を用いた連続空間での近似解法を提案した。
著者: Emmanuel Boidot, Aude Marzuoli, Eric Feron
分類: cs.RO
原文アブストラクト
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.
