13.5.2 Differential Game Theory

The extension of sequential game theory to the continuous-time case is called differential game theory (or dynamic game theory [59]), a subject introduced by Isaacs [477]. All of the variants considered in Sections 9.3, 9.4, 10.5 are possible:

  1. There may be any number of players.
  2. The game may be zero-sum or nonzero-sum.
  3. The state may or may not be known. If the state is unknown, then interesting I-spaces arise, similar to those of Section 11.7.
  4. Nature can interfere with the game.
  5. Different equilibrium concepts, such as saddle points and Nash equilibria, can be defined.
See [59] for a thorough overview of differential games. Two players, $ {{\rm P}_1}$ and $ {{\rm P}_2}$, can be engaged in a differential game in which each has a continuous set of actions. Let $ U$ and $ V$ denote the action spaces of $ {{\rm P}_1}$ and $ {{\rm P}_2}$, respectively. A state transition equation can be defined as

$\displaystyle {\dot x}= f(x,u,v) ,$ (13.203)

in which $ x$ is the state, $ u \in U$, and $ v \in V$.

Linear differential games are an important family of games because many techniques from optimal control theory can be extended to solve them [59].

Example 13..17 (Linear Differential Games)   The linear system model (13.37) can be extended to incorporate two players. Let $ X = {\mathbb{R}}^n$ be a phase space. Let $ U =
{\mathbb{R}}^{m_1}$ and $ V = {\mathbb{R}}^{m_2}$ be an action spaces for $ m_1,m_2 \leq
n$. A linear differential game is expressed as

$\displaystyle {\dot x}= A x + B u + C v,$ (13.204)

in which $ A$, $ B$, and $ C$ are constant, real-valued matrices of dimensions $ n \times n$, $ n \times m_1$, and $ n \times m_2$, respectively. The particular solution to such games depends on the cost functional and desired equilibrium concept. For the case of a quadratic cost, closed-form solutions exist. These extend techniques that are developed for linear systems with one decision maker; see Section 15.2.2 and [59].

The original work of Isaacs [477] contains many interesting examples of pursuit-evasion differential games. One of the most famous is described next.

Example 13..18 (Homicidal Chauffeur)   In the homicidal chauffeur game, the pursuer is a Dubins car and the evader is a point robot that can translate in any direction. Both exist in the same world, $ {\cal W}= {\mathbb{R}}^2$. The speeds of the car and robot are $ s_1$ and $ s_2$, respectively. It is assumed that $ \vert s_1\vert > \vert s_2\vert$, which means that the pursuer moves faster than the evader. The transition equation is given by extending (13.15) to include two state variables that account for the robot position:

$\displaystyle {\dot x}_1$ $\displaystyle = s_1 \cos\theta_1$ $\displaystyle \qquad {\dot x}_2$ $\displaystyle = s_2 \cos v$    
$\displaystyle {\dot y}_1$ $\displaystyle = s_1 \sin\theta_1$ $\displaystyle \qquad {\dot y}_2$ $\displaystyle = s_2 \sin v$ (13.205)
$\displaystyle {\dot \theta}_1$ $\displaystyle = \displaystyle\strut {s_1 \over L} \tan u_\phi .$    

The state space is $ X$ is $ {\mathbb{R}}^4 \times {\mathbb{S}}^1$, and the action spaces are $ U = [-\phi_{max},\phi_{max}]$ and $ V = [0,2 \pi)$.

The task is to determine whether the pursuer can come within some prescribed distance $ \epsilon$ of the evader:

$\displaystyle (x_1 - x_2)^2 + (y_1-y_2)^2 < \epsilon^2 .$ (13.206)

If this occurs, then the pursuer wins; otherwise, the evader wins. The solution depends on the $ L$, $ s_1$, $ s_2$, $ \epsilon$, and the initial state. Even though the pursuer moves faster, the evader may escape because it does not have a limited turning radius. For given values of $ L$, $ s_1$, $ s_2$, and $ \epsilon$, the state space $ X$ can be partitioned into two regions that correspond to whether the pursuer or evader wins [59,477]. To gain some intuition about how this partition may appear, imagine the motions that a bullfighter must make to avoid a fast, charging bull (yes, bulls behave very much like a fast Dubins car when provoked). $ \blacksquare$

Another interesting pursuit-evasion game arises in the case of one car attempting to intercept another [694].

Example 13..19 (A Game of Two Cars)   Imagine that there are two simple cars that move in the same world, $ {\cal W}= {\mathbb{R}}^2$. Each has a transition equation given by (13.15). The state transition equation for the game is

$\displaystyle {\dot x}_1$ $\displaystyle = u_s \cos\theta_1$ $\displaystyle \qquad {\dot x}_2$ $\displaystyle = v_s \cos\theta_2$    
$\displaystyle {\dot y}_1$ $\displaystyle = u_s \sin\theta_1$ $\displaystyle \qquad {\dot y}_2$ $\displaystyle = v_s \sin\theta_2$ (13.207)
$\displaystyle {\dot \theta}_1$ $\displaystyle = \displaystyle\strut {u_s \over L_1} \tan u_\phi$ $\displaystyle \qquad {\dot \theta}_2$ $\displaystyle = \displaystyle\strut {v_s \over L_2} \tan v_\phi .$    

The pursuit-evasion game becomes very interesting if both players are restricted to be Dubins cars. $ \blacksquare$

Steven M LaValle 2012-04-20