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

$${\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

$${\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:

$${\dot x}_1 = s_1 \cos\theta_1 \qquad {\dot x}_2 = s_2 \cos v$$

$${\dot y}_1 = s_1 \sin\theta_1 \qquad {\dot y}_2 = s_2 \sin v$$ (13.205)

$${\dot \theta}_1 = \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:

$$(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

$${\dot x}_1 = u_s \cos\theta_1 \qquad {\dot x}_2 = v_s \cos\theta_2$$

$${\dot y}_1 = u_s \sin\theta_1 \qquad {\dot y}_2 = v_s \sin\theta_2$$ (13.207)

$${\dot \theta}_1 = \displaystyle\strut {u_s \over L_1} \tan u_\phi \qquad {\dot \theta}_2 = \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$