15.2.3 Pontryagin's Minimum Principle

*Pontryagin's minimum principle*^{15.5} is closely related to the HJB equation and provides
conditions that an optimal trajectory must satisfy. Keep in mind,
however, that the minimum principle provides *necessary*
conditions, but not *sufficient conditions*, for optimality. In
contrast, the HJB equation offered sufficient conditions. Using the
minimum principle alone, one is often not able to conclude that a
trajectory is optimal. In some cases, however, it is quite useful for
finding candidate optimal trajectories. Any trajectory that fails to
satisfy the minimum principle cannot be optimal.

To understand the minimum principle, we first return to the case of discrete planning. As mentioned previously, the minimum principle is essentially given by (15.7). This can be considered as a specialization of the HJB equation to the special case of applying the optimal action . This causes the to disappear, but along with it the global properties of the HJB equation also vanish. The minimum principle expresses conditions along the optimal trajectory, as opposed to the cost-to-go function over the whole state space. Therefore, it can at best assure local optimality in the space of possible trajectories.

The minimum principle for the continuous case is essentially given by (15.15), which is the continuous-time counterpart to (15.7). However, it is usually expressed in terms of adjoint variables and a Hamiltonian function, in the spirit of Hamiltonian mechanics from Section 13.4.4.

Let denote an -dimensional vector of *adjoint
variables*, which are defined as

The

which is exactly the expression inside of the of the HJB equation (15.14) after using the adjoint variable definition from (15.25). This can be compared to the Hamiltonian given by (13.192) in Section 13.4.4 ( from that context becomes here). The two are not exactly the same, but they both are motivated by the same basic principles.

Under the execution of the optimal action trajectory , the HJB equation implies that

for all . This is just an alternative way to express (15.15). The fact that remains constant appears very much like a conservation law, which was the basis of Hamiltonian mechanics in Section 13.4.4. The use of the Hamiltonian in the minimum principle is more general.

Using the HJB equation (15.14), the optimal action is given by

In other words, the Hamiltonian is minimized precisely at .

The missing piece of information so far is how evolves over time. It turns out that a system of the form

can be derived by differentiating the Hamiltonian (or, equivalently, the HJB equation) with respect to . This yields two coupled systems, and (15.29). These can in fact be interpreted as a single system in a -dimensional phase space, in which each phase vector is . This is analogous to the phase interpretation in Section 13.4.4 for Hamiltonian mechanics, which results in (13.198).

Remember that is defined in (15.25) just to keep track of the change in . It would be helpful to have an explicit form for (15.29). Suppose that is selected by a feedback plan to yield . In this case, the Hamiltonian can be interpreted as a function of only and . Under this assumption, differentiating the Hamiltonian (15.26) with respect to yields

This validity of this differentiation requires a technical lemma that asserts that the derivatives of can be disregarded (see Lemma 3.3.1 of [95]). Also, it will be assumed that is convex in the arguments that follow, even though there exist proofs of the minimum principle that do not require this.

The second term in (15.30) is actually , although it is hard to see at first. The total differential of with respect to the state is

(15.31) |

Dividing both sides by yields

(15.32) |

Each is given by the state transition equation: . Therefore,

Substituting (15.33) into (15.30) and setting the equation to zero (because the Hamiltonian is zero along the optimal trajectory) yields

Solving for yields

Conveniently, this is the same as

which yields the

The transition equations given by and (15.36) specify the evolution of the system given by the minimum principle. These are analogous to Hamilton's equations (13.198), which were given in Section 13.4.4. The generalized momentum in that context becomes the adjoint variables here.

When applying the minimum principle, it is usually required to use the fact that the optimal action at all times must satisfy (15.28). Often, this is equivalently expressed as

which indicates that the Hamiltonian increases or remains the same whenever deviation from the optimal action occurs (the Hamiltonian cannot decrease).

Using (15.26), the Hamiltonian is defined as

The optimal action trajectory is obtained from (15.28) as

If , then , and if , then . Thus, the action may be assigned as , if . Note that these two cases are the ``bangs'' of the bang-bang control from Section 14.6.3, and they are also the extremal actions used for the planning algorithm in Section 14.4.1. At the boundary case in which , any action in may be chosen.

The only remaining task is to determine the values of the adjoint variables over time. The adjoint transition equation is obtained from (15.36) as and . The solutions are and , in which and are constants that can be determined at from (15.38) and (15.39). The optimal action depends only on the sign of . Since its solution is the equation of a line, it can change signs at most once. Therefore, there are four possible kinds of solutions, depending on the particular and :

- Pure acceleration, , is applied for all time.
- Pure deceleration, , is applied for all time.
- Pure acceleration is applied up to some time and is followed immediately by pure deceleration until the final time.
- Pure deceleration is applied up to some time followed immediately by pure acceleration until the final time.

This was one of the simplest possible examples, and the optimal solution was easily found because the adjoint variables are linear functions of time. Section 15.3 covers optimal solutions for the Dubins car, the Reeds-Shepp car, and the differential drive, all of which can be established using the minimum principle combined with some geometric arguments. As systems become more complicated, such analysis is unfortunately too difficult. In these cases, sampling-based methods, such as those of Chapter 14, must be used to determine optimal trajectories.

One common complication is the existence of *singular arcs* along
the solution trajectory. These correspond to a degeneracy in with
respect to over some duration of time. This could be caused, for
example, by having independent of . In Example
15.4, became independent of when
; however, there was no singular arc because this could only occur
for an instant of time. If the duration had been longer, then there
would be an interval of time over which the optimal action could not
be determined. In general, if the Hessian (recall definition from
(8.48)) of with respect to is a positive definite
matrix, then there are no singular arcs (this is often called the
Legendre-Clebsch condition). The minimum principle in this case
provides a sufficient condition for local optimality in the space of
possible state trajectories. If the Hessian is not positive definite
for some interval with , then additional
information is needed to determine the optimal trajectory over the
singular arc from to .

Note that all of this analysis ignores the existence of obstacles. There is nothing to prevent the solutions from attempting to enter an obstacle region. The action set and cost can be adjusted to account for obstacles; however, determining an optimal solution from the minimum principle becomes virtually impossible, except in some special cases.

There are other ways to derive the minimum principle. Recall from Section 13.4.4 that Hamilton's equations can be derived from the Euler-Lagrange equation. It should not be surprising that the minimum principle can also be derived using variational principles [95,789]. The minimum principle can also be interpreted as a form of constrained optimization. This yields the interpretation of as Lagrange multipliers. A very illuminating reference for further study of the minimum principle is Pontryagin's original works [801].