Numerical Analysis and Scientific Computing Seminar

Surveillance-Evasion Games Under Uncertainty

Speaker: Alexander Vladimirsky, Cornell

Location: Warren Weaver Hall 1302

Date: Oct. 5, 2018, 10 a.m.


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.