Linear Programming Approach to Deceptive Path Planning Game with Goal Selection
For multi-agent adversarial path planning, this work models observers as strategic decision-makers rather than passive, addressing a known limitation in prior work.
The paper tackles deceptive path planning where an agent selects a goal and plans a path to mislead an adversarial observer allocating defensive resources. It proposes a game-theoretic formulation solved via linear programming and Double Oracle, introducing metrics for deception effectiveness.
In adversarial settings, a mobile agent may strategically plan its motion to influence an opponent's inference about its intended goal. We study deceptive path planning in a scenario where a mobile agent aims to reach a privately selected goal while an adversarial observer allocates limited defensive resources based on the observed trajectory. Unlike classical path-planning and goal-recognition approaches that model observers as passive inference process, our game-theoretic formulation models them as strategic decision-makers. For the resulting dynamic asymmetric-information game, we develop an efficient solution method that combines a linear programming formulation with the Double Oracle algorithm. To evaluate performance, we introduce metrics that quantify both the risk and the effectiveness of deception and provide illustrative numerical examples.