Adversarial path planning

Marc Gilles and Alex Vladimirsky (CAM and Math, Cornell University)

Path planning is a problem of interest for many communities: traffic engineering, autonomous driving, robotics and military. In the classical setting, the path planner is assumed to have full information about the environment and chooses a path minimizing some undesirable quantity: total time, distance, fuel or threat exposure. In this talk, we discuss a generalization to adversarial/robust path planning where the environment is possibly changing in response to the path planner’s routing choices. A particular application is to evader/observer games. In the usual framework, an evader is choosing a path to minimize its exposure to an observer at a known, fixed position. In our framework, we can treat the case where the observer is also choosing its position (or a probability distribution over its possible positions) to maximize the evader’s expected visibility. The proposed approach draws on methods from game theory, convex optimization, optimal control, and multiobjective dynamic programming. We also discuss generalization to the case of a large group of evaders under selfish decision making in the framework of “mean field games”.