MATH 6230 - Differential Games, Optimal Control, Front Propogation, and Dynamic Programming

Alex Vladimirsky, fall 2016.

A Homicidal Chauffeur tries to run over a Pedestrian. The Chauffeur’s speed is much greater, but he is constrained by a minimum turn-radius. Can the Pedestrian survive this encounter? …in the presence of obstacles? …until the arrival of Police?

We will explore the theory of non-linear Hamilton-Jacobi PDEs using and comparing two natural perspectives: differential games/control theory and front propagation modeling. We will use the Optimality Principle to establish the properties of viscosity solutions and to build fast numerical methods by determining the direction of information flow. Throughout the course, we will highlight similarities and differences between the continuous and discrete control problems (e.g., an optimal path for a rover on the surface of Mars vs. optimal driving directions from Ithaca to New York City).

No prior knowledge of non-linear PDEs or numerical analysis will be assumed. In the numerical part of the course, the emphasis will be on the fundamental ideas rather than on implementation details. The participants’ interests will determine a subset of topics to be discussed in detail:

Hamilton-Jacobi PDEs: general theory of viscosity solutions; interpretation of characteristics; connections to the calculus of variations; relationship to hyperbolic conservation laws; homogenization; multi-valued solutions; variational inequalities.

Games & Control: deterministic and stochastic; discrete, continuous, and hybrid; finite and infinite time-horizon vs. exit-time problems; worst-case and on-average optimality; restricted state space and non-autonomous controls; robust, risk-sensitive and likelihood-maximizing controls; Pareto-optimal controls; pursuer-evader games; surveillance-evasion games; pusher-chooser games; tug-of-war games; mean-field games; optimal behavior in uncertain environments.

Front propagation: Legendre transform; Wulff shapes; (anisotropic) Huygens’ principle; geometric optics; motion by mean curvature and degenerate ellipticity.

Numerical Approaches: Lagrangian, semi-Lagrangian, and Eulerian discretizations; controlled Markov chains; iterative and causal (non-iterative) methods; level set methods; model reductions and approximate dynamic programming.

Applications: robotics, computational geometry, path-planning, image segmentation, shape-from-shading, seismic imaging, photolithography, crystal growth, financial engineering, crowd dynamics, aircraft collision avoidance.