MATH 613: Differential Games, Optimal Control, Front Propagation, and Dynamic Programming (Fall 2004)

Instructor: Alexander Vladimirsky

Meeting Time & Room

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; multi-valued solutions; variational inequalities.

Games & Control: deterministic & stochastic; discrete, continuous, & hybrid; finite & infinite time-horizon vs. exit-time problems; restricted state space and non-autonomous control; pursuer-evader 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.

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

Last modified: August 26, 2004