The Hamilton–Jacobi–Isaacs Game Equation

From HJB to HJI

In optimal control theory, the value function V(x, t) satisfies the Hamilton–Jacobi–Bellman (HJB) equation. When a second player with opposing interests is introduced, the equation is modified: instead of a min over u, there is simultaneously a min over u and a max over v. This is the Hamilton–Jacobi–Isaacs (HJI) equation — the central equation of differential game theory. Its solution — the value function of the game V(x, t) — defines the optimal strategies for both players.

Value Function of the Game

Definition: V(x, t) = min_{u(·)} max_{v(·)} J(x, t; u(·), v(·)) is the value of the game started from state x at time t.

Terminal condition: V(x, T) = g(x), the cost of the terminal state.

V(x, t) must satisfy a partial differential equation.

Derivation of the HJI Equation

We use the principle of optimality: under optimal play,

V(x, t) = min_u max_v [F(x,u,v,t)dt + V(x + f(x,u,v)dt, t + dt)]

Expand V in a Taylor series: V(x + fdt, t + dt) ≈ V + V_t dt + ∇V·f dt.

min_u max_v [F dt + V_t dt + ∇V·f dt] = 0

Dividing by dt:

HJI equation: ∂V/∂t + H*(x, t, ∇V) = 0

where the game Hamiltonian: H*(x, t, p) = min_{u∈U} max_{v∈V} {F(x, u, v, t) + pᵀ f(x, u, v, t)}

here p = ∇_x V are the "co-state variables" (analogous to momentum).

Isaacs' Condition

Isaacs' condition: min_{u∈U} max_{v∈V} H(x,u,v,p) = max_{v∈V} min_{u∈U} H(x,u,v,p)

Where H(x,u,v,p) = F + pᵀf — the Lagrangian of the problem.

Meaning: the "game Hamiltonian" is the same upon swapping min and max. This is analogous to the "equilibrium" condition in static games.

When satisfied: with compact U, V and continuous H — always (Neumann minimax theorem). With disconnected controls there may be problems.

If violated: the value of the game may depend on the order of moves (who "announces" their strategy first). One must distinguish the "lower value" V⁻ = max_v min_u J and the "upper value" V⁺ = min_u max_v J.

Optimal Feedback Strategies

Given a known V(x, t), the optimal strategies are:

u*(x, t) = argmin_{u∈U} H(x, u, v*(x,t), ∇V) (for P) v*(x, t) = argmax_{v∈V} H(x, u*(x,t), v, ∇V) (for E)

If Isaacs' condition holds, these strategies exist and are simultaneously determined through the saddle point of H*.

Regularity and Viscosity Solutions

HJI is a nonlinear first-order PDE. A classical (smooth) solution does not always exist: "singular" surfaces can arise — barriers, switchings, discontinuities. These features have clear physical sense (the "capture zone" boundary), but disrupt the smoothness of V.

Viscosity solutions (Crandall–Lions, 1983): an extended notion of solution for nonlinear first-order PDEs. Uniqueness of the viscosity solution for HJI is established under reasonable conditions (Evans–Souganidis, 1984).

Numerical methods: finite differences with monotone schemes (Osher–Shu upwind), level-set methods (Osher–Sethian). These methods closely approximate the viscosity solution.

Complete Analysis: A Simple Pursuit Game in ℝ

Dynamics: ẋ = u − v, x ∈ ℝ, u ∈ [−1,1] (P), v ∈ [−a,a] (E, a < 1).

Cost functional: J = x(T)² (minimize the distance at T).

HJI: ∂V/∂t + min_{|u|≤1} max_{|v|≤a} [(u−v) ∂V/∂x] = 0.

Game Hamiltonian: H* = min_{u} max_{v} [(u−v) p] = min_u [up − a|p|] = −|p| − a|p| = −(1+a)|p|.

(u* = −sign(p), v* = a·sign(p))

HJI: ∂V/∂t − (1+a)|∂V/∂x| = 0, V(x,T) = x².

Seek solution as V(x, t) = φ(x − u*(T−t))... analytically complicated. For t close to T: V ≈ x² − (1+a)·2|x|·(T−t) + O((T−t)²). Optimal P strategy: u* = −sign(x), that is, move toward zero (toward equilibrium).

Applications

HJI is used in the theory of robust controllers (H∞ control), in aviation (interceptor control), in autonomous systems (safe navigation). Numerical solution of HJI on a grid is the standard method in the "Hamilton–Jacobi toolbox" (MATLAB) and BEACLS (C++).

Numerical Solution of HJI

Unlike linear PDEs, HJI requires specialized schemes. The classical monotone upwind scheme:

Discretize the state x on a grid xᵢ
Compute the gradient ∇V using one-sided differences taking sign into account
Compute H* via minimax at each cell
Advance one time step: V^{n+1} = V^n − Δt · H*

The scheme is stable under the CFL condition: Δt ≤ Δx / max|f|. Convergence to the viscosity solution is guaranteed by the Barles–Souganidis theorem.

Dimensionality as a Limitation

The main problem of HJI is the curse of dimensionality: for dimension n one needs N^n grid points, where N is the number of points per axis. For n = 6 (standard 3D kinematics problem of two bodies) and N = 100, this is 10¹² cells — at the limit of feasibility. Modern methods for high dimensions:

Decomposition: splitting the problem into subproblems of lower dimension (Mitchell, Tomlin)
Sparse grids (Smolyak): reducing the number of points to O(N log^n)
Neural network approximation: Deep BSDE (E–Han–Jentzen, 2017), PINNs — the neural network approximates V(x, t), solving HJI as a loss function
Reinforcement learning: instead of explicit HJI solution — learning the optimal policy via simulation

Real-Time Applications

For real-time tasks (aviation, autonomous vehicles), off-line computation of V on a grid is used, plus on-line lookup. The toolbox helperOC enables computation of the "safe set" for quadcopters within minutes, after which in-flight control is selected based on tabulated values of ∇V.