Abstract: Adversarial path planning problems are important in robotics applications and in modeling the behavior of humans in dangerous environments. Surveillance-Evasion (SE) games form an important subset of such problems and require a blend of numerical techniques from multiobjective dynamic programming, game theory, numerics for Hamilton-Jacobi PDEs, and convex optimization. We model the basic SE problem as a semi-infinite zero-sum game between two players: an Observer (O) and an Evader (E) traveling through a domain with occluding obstacles. O chooses a pdf over a finite set of predefined surveillance plans, while E chooses a pdf over an infinite set of trajectories that bring it to a target location. The focus of this game is on "E's expected cumulative exposure to O", and we have recently developed an algorithm for finding the Nash Equilibrium open-loop policies for both players. I will use numerical experiments to illustrate algorithmic extensions to handle multiple Evaders, moving Observes, and anisotropic observation sensors. Time permitting, I will also show preliminary results for a very large number of selfish/independent Evaders modeled via Mean Field Games.
Joint work with M.Gilles, E.Cartee, and REU-2018 participants.
Bio: Alex Vladimirsky is an applied mathematician from Cornell University, whose interests span nonlinear PDEs, dynamical systems, optimal control & differential games, numerical analysis, and algorithms on graphs. His past and current projects include efficient numerics for (& homogenization of) Hamilton-Jacobi PDEs, multiobjective & randomly-terminated optimal control, surveillance-evasion games under uncertainty, seismic imaging, dimensional reduction in turbulent combustion, approximation of invariant manifolds, and macro-scale models of pedestrian interactions. He is currently on sabbatical at ORFE/Princeton, supported by the Simons Foundation Fellowship in studying applications of Mean Field Games and piecewise-deterministic models in robotics.