15.1 Basic System Properties
This section provides a brief overview of two fundamental concepts in control theory: stability and controllability. Either can be considered as characterizing how a goal state is reached. Stability usually involves feedback and may only converge to the goal as time approaches infinity. Controllability assesses whether an action trajectory exists that leads exactly to a specified goal state. In both cases, there is no obstacle region in X.
15.1.1 Stability
The subject of stability addresses properties of a vector field with respect to a given point. Let X denote a smooth manifold on which the vector field is defined; X may be a C-space or a phase space. The given point is denoted as xG and can be interpreted in motion planning applications as the goal state. Stability characterizes how xG is approached from other states in X by integrating the vector field.
The given vector field f is considered as a velocity field, which is represented
as
x˙ = f(x). (15.1)
This looks like a state transition equation that is missing actions. If a system of
the form x˙ = f(x, u) is given, then u can be fixed by designing a feedback plan
π : X U. This yields x˙ = f(x, π(x)), which is a vector field on X without any further dependency on actions. The dynamic programming approach in Section
→
- computed such a solution. The process of designing a stable feedback plan is referred to in control literature as feedback stabilization.
Equilibrium points and Lyapunov stability At the very least, it seems that the state should remain fixed at xG, if it is reached. A point xG ∈ X is called
an equilibrium point (or fixed point) of the vector field f if and only if f(xG) = 0.
This does not, however, characterize how trajectories behave in the vicinity of xG. Let xI ∈ X denote some initial state, and let x(t) refer to the state obtained at
time t after integrating the vector field f from xI = x(0).
- (b)
Figure 15.1: Lyapunov stability: (a) Choose any open set O1 that contains xG, and (b) there exists some open set O2 from which trajectories will not be able to escape O1. Note that convergence to xG is not required.
See Figure 15.1. An equilibrium point xG X is called Lyapunov stable if for any open neighborhood1 O1 of xG there exists another open neighborhood O2 of xG such that xI O2 implies that x(t) O1 for all t > 0. If X = Rn, then some intuition can be obtained by using an equivalent definition that is expressed in
∈
∈ ∈
terms of the Euclidean metric. An equilibrium point xG ∈ Rn is called Lyapunov stable if, for any t > 0, there exists some δ > 0 such that IxI − x_G_I < δ implies
that x(t) xG < ǫ. This means that we can choose a ball around xG with a radius as small as desired, and all future states will be trapped within this ball, as long as they start within a potentially smaller ball of radius δ. If a single δ can be chosen independently of every ǫ and x, then the equilibrium point is called uniform Lyapunov stable.
I − I
Asymptotic stability Lyapunov stability is weak in that it does not even imply that x(t) converges to xG as t approaches infinity. The states are only required to hover around xG. Convergence requires a stronger notion called asymptotic stability. A point xG is an asymptotically stable equilibrium point of f if:
- It is a Lyapunov stable equilibrium point of f.
- There exists some open neighborhood O of xG such that, for any xI O, x(t) converges2 to xG as t approaches infinity.
∈
For X = Rn, the second condition can be expressed as follows: There exists some
δ > 0 such that, for any xI ∈ X with IxI − x_G_I < δ, the state x(t) converges to
xG as t approaches infinity. It may seem strange that two requirements are needed for asymptotic stability. The first one bounds the amount of wiggling room for the integral curve, which is not captured by the second condition.
1An open neighborhood of a point x means an open set that contains x.
2This convergence can be evaluated using the metric ρ on X.
Asymptotic stability appears to be a reasonable requirement, but it does not imply anything about how long it takes to converge. If xG is asymptotically stable and there exist some m > 0 and α > 0 such that
Ix(t) − xG_I ≤ me−αtIx_I − x_G_I, (15.2)
then xG is also called exponentially stable. This provides a convenient way to express the rate of convergence.
For use in motion planning applications, even exponential convergence may not seem strong enough. This issue was discussed in Section 8.4.1. For example, in practice, one usually prefers to reach xG in finite time, as opposed to only being “reached” in the limit. There are two common fixes. One is to allow asymptotic stability and declare the goal to be reached if the state arrives in some small, predetermined ball around xG. In this case, the enlarged goal will always be reached in finite time if xG is asymptotically stable. The other fix is to require a stronger form of stability in which xG must be exactly reached in finite time. To enable this, however, discontinuous vector fields such as the inward flow of Figure 8.5b must be used. Most control theorists are appalled by this because infinite energy is usually required to execute such trajectories. On the other hand, discontinuous vector fields may be a suitable representation in some applications, as mentioned in Chapter 8. Note that without feedback this issue does not seem as important. The state trajectories designed in much of Chapter 14 were expected to reach the goal in finite time. Without feedback there was no surrounding vector field that was expected to maintain continuity or smoothness properties. Section
15.1.3 introduces controllability, which is based on actually arriving at the goal in finite time, but it is also based on the existence of one trajectory for a given
system x˙
x = f(x).
= f(x, u), as opposed to a family of trajectories for a given vector field
Time-varying vector fields The stability notions expressed here are usually
introduced in the time-varying setting x˙ = f(x, t). Since the vast majority of
planning problems in this book are time-invariant, the presentation was confined to time-invariant vector fields. There is, however, one fascinating peculiarity in the topic of finding a feedback plan that stabilizes a system. Brockett’s condition implies that for some time-invariant systems for which continuous, time-varying feedback plans exist, there does not exist a continuous time-invariant feedback plan [143, 156, 996]. This includes the class of driftless control systems, such as the simple car and the unicycle. This implies that to maintain continuity of the vector field, a time dependency must be introduced to allow the vector field to vary as xG is approached! If continuity of the vector field is not important, then this concern vanishes.
Domains of attraction The stability definitions given so far are often called local because they are expressed in terms of a neighborhood of xG. Global versions can also be defined by extending the neighborhood to all of X. An equilibrium
point is globally asymptotically stable if it is Lyapunov stable, and the integral curve from any x0 ∈ X converges to xG as time approaches infinity. It may be
the case that only points in some proper subset of X converge to xG. The set of all points in X that converge to xG is often called the domain of attraction of xG. The funnels of Section 8.5.1 are based on domains of attraction. Also related is the backward reachable set from Section 14.2.1. In that setting, action trajectories were considered that lead to xG in finite time. For the domain of attraction only asymptotic convergence to xG is assumed, and the vector field is given (there are no actions to choose).
Limit cycles For some vector fields, states may be attracted into a limit cycle. Rather than stabilizing to a point, the state trajectories converge to a loop path in X. For example, they may converge to following a circle. This occurs in a wide variety of mechanical systems in which oscillations are possible. Some of the basic issues, along with several interesting examples for X = R2, are covered in [44].
- Lyapunov Functions
Suppose a velocity field x˙ = f(x) is given along with an equilibrium point, xG.
Can the various forms of stability be easily determined? One of the most powerful
methods to prove stability is to construct a Lyapunov function. This will be introduced shortly, but first some alternatives are briefly mentioned.
If f(x) is linear, which means that f(x) = Ax for some constant n n matrix A and X = Rn, then stability questions with respect to the origin, xG = 0, are answered by finding the eigenvalues of A [192]. The state x = 0 is asymptotically stable if and only if all eigenvalues of A have negative real parts. Consider the
×
scalar case, x˙ = ax, for which X = R and a is a constant. The solution to
this differential equation is x(t) = x(0) eat, which converges to 0 only if a < 0. This can be easily extended to the case in which X = Rn and A is an n n diagonal matrix for which each diagonal entry (or eigenvalue) is negative. For
×
a general matrix, real or complex eigenvalues determine the stability (complex eigenvalues cause oscillations). Conditions also exist for Lyapunov stability. Every
equilibrium state of x˙ = Ax is Lyapunov stable if the eigenvalues of A all have
nonpositive real parts, and the eigenvalues with zero real parts are distinct roots of the characteristic polynomial of A.
If f(x) is nonlinear, then stability can sometimes be inferred by linearizing f(x) about xG and performing linear stability analysis. In many cases, however, this procedure is inconclusive (see Chapter 6 of [156]). Proving the stability of a vector field is a challenging task for most nonlinear systems. One approach is based on LaSalle’s invariance principle [39, 156, 585] and is particularly useful for showing convergence to any of multiple goal states (see Section 5.4 of [846]). The other major approach is to construct a Lyapunov function, which is used as an intermediate tool to indirectly establish stability. If this method fails, then it still may be possible to show stability using other means. Therefore, it is a sufficient
condition for stability, but not a necessary one.
Determining stability Suppose a velocity field x˙ = f(x) is given along with
an equilibrium point xG. Let φ denote a candidate Lyapunov function, which will be used as an auxiliary device for establishing the stability of f. An appropriate φ must be determined for the particular vector field f. This may be quite challenging in itself, and the details are not covered here. In a sense, the procedure can be characterized as “guess and verify,” which is the way that many solution techniques for differential equations are described. If φ succeeds in establishing stability, then it is promoted to being called a Lyapunov function for f.
It will be important to characterize how φ varies in the direction of flow induced by f. This is measured by the Lie derivative,
n ∂φ
φ˙ (x) = - ∂x fi(x). (15.3)
i=1
i
This results in a new function φ˙ (x), which indicates for each x the change in φ
along the direction of x˙ = f(x).
Several concepts are needed to determine stability. Let a function h : [0, ) [0, ) be called a hill if it is continuous, strictly increasing, and h(0) = 0. This can be considered as a one-dimensional navigation function, which has a single
∞
∞ →
local minimum at the goal, 0. A function φ : X → [0, ∞) is called locally positive definite if there exists some open set O ⊆ X and a hill function h such that
φ(xG) = 0 and φ(x) h( x ) for all x O. If O can be chosen as O = X, and if X is bounded, then φ is called globally positive definite or just positive definite. In some spaces this may not be possible due to the topology of X; such issues arose when constructing navigation functions in Section 8.4.4. If X is unbounded, then h must additionally approach infinity as x approaches infinity to yield a positive definite φ [846]. For X = Rn, a quadratic form xT Mx, for which M is a positive definite matrix, is a globally positive definite function. This motivates the use of quadratic forms in Lyapunov stability analysis.
I I
≥ I I ∈
The Lyapunov theorems can now be stated [156, 846]. Suppose that φ is locally positive definite at xG. If there exists an open set O for which xG ∈ O, and φ˙ (x) ≤ 0 on all x ∈ O, then f is Lyapunov stable. If −φ˙ (x) is also locally positive
definite on O, then f is asymptotically stable. If φ and φ˙ are both globally positive definite, then f is globally asymptotically stable.
−
Example 15.1 (Establishing Stability via Lyapunov Functions) Let X =
R. Let x˙ = f(x) = x5, and we will attempt to show that x = 0 is stable. Let the candidate Lyapunov function be φ(x) = 1 x2. The Lie derivative (15.3) produces
−
2
φ˙ (x) = −x6. It is clear that φ and −φ˙ are both globally positive definite; hence,
0 is a global, asymptotically stable equilibrium point of f. ．
Lyapunov functions in planning Lyapunov functions are closely related to navigation functions and optimal cost-to-go functions in planning. In the optimal discrete planning problem of Sections 2.3 and 8.2, the cost-to-go values can be considered as a discrete Lyapunov function. By applying the computed actions, a kind of discrete vector field can be imagined over the search graph. Each ap- plied optimal action yields a reduction in the optimal cost-to-go value, until 0 is reached at the goal. Both the optimal cost-to-go and Lyapunov functions en- sure that the trajectories do not become trapped in a local minimum. Lyapunov functions are more general than cost-to-go functions because they do not require optimality. They are more like navigation functions, as considered in Chapter 8. The requirements for a discrete navigation function, as given in Section 8.2.2, are very similar to the positive definite condition given in this section. Imagine that
the navigation function shown in Figure 8.3 is a discrete approximation to a Lya- punov function over R2. In general, a Lyapunov function indicates some form of distance to xG, although it may not be optimal. Nevertheless, it is based on mak- ing monotonic progress toward xG. Therefore, it may serve as a distance function in many sampling-based planning algorithms of Chapter 14. Since it respects the differential constraints imposed by the system, it may provide a better indication of how to make progress during planning in comparison to a Euclidean metric that ignores these considerations. Lyapunov functions should be particularly valuable in the RDT method of Section 14.4.3, which relies heavily on the distance function
over X.
- Controllability
Now suppose that a system x˙ = f(x, u) is given on a smooth manifold X as defined throughout Chapter 13 and used extensively in Chapter 14. The system can be considered as a parameterized family of vector fields in which u is the parameter. For stability, it was assumed that this parameter was fixed by a feedback plan
to obtain some x˙ = f(x). This section addresses controllability, which indicates
whether one state is reachable from another via the existence of an action tra- jectory u˜. It may be helpful to review the reachable set definitions from Section 14.2.1.
Classical controllability Let denote the set of permissible action trajectories for the system, as considered in Section 14.1.1. By default, this is taken as any
U
u˜ for which (14.1) can be integrated. A system x˙ = f(x, u) is called controllable
if for all xI , xG ∈ X, there exists a time t > 0 and action trajectory u˜ ∈ U such
that upon integration from x(0) = xI , the result is x(t) = xG. Controllability can alternatively be expressed in terms of the reachable sets of Section 14.2.1. The
system is controllable if xG ∈ R(xI , U) for all xI , xG ∈ X.
A system is therefore controllable if a solution exists to any motion planning problem in the absence of obstacles. In other words, a solution always exists to the two-point boundary value problem (BVP).
Example 15.2 (Classical Controllability) All of the vehicle models in Section
13.1.2 are controllable. For example, in an infinitely large plane, the Dubins car can be driven between any two configurations. Note, however, that if the plane is restricted by obstacles, then this is not necessarily possible with the Dubins
car. As an example of a system that is not controllable, let X = R, x˙ = u, and
U = [0, 1]. In this case, the state cannot decrease. For example, there exists no action trajectory that brings the state from xI = 1 to xG = 0. ．
Many methods for determining controllability of a system are covered in stan- dard textbooks on control theory. If the system is linear, as given by (13.37) with dimensions m and n, then it is controllable if and only if the n nm controllability matrix
×
M = [B .. AB .. A2B ..
.
.
.
.
· · · A B] (15.4)
. n−1
.
has full rank [192]. This is called the Kalman rank condition [501]. If the system is nonlinear, then the controllability matrix can be evaluated on a linearized version of the system. Having full rank is sufficient to establish controllability from a single point (see Proposition 11.2 in [846]). If the rank is not full, however, the system may still be controllable. A fascinating property of some nonlinear systems is that they may be able to produce motions in directions that do not seem to be allowed at first. For example, the simple car given in Section 13.1.2 cannot slide sideways; however, it is possible to wiggle the car sideways by performing parallel- parking maneuvers. A method for determining the controllability of such systems is covered in Section 15.4.
For fully actuated systems of the form q¨ = h(q, q˙, u), controllability can be
determined by converting the system into double-integrator form, as considered in Section 14.4.1. Let the system be expressed as q¨ = u′, in which u′ U′(q, q˙). If U′(q, q˙) contains an open neighborhood of the origin of Rn, and the same neigh- borhood can be used for any x X, then the system is controllable. If a nonlinear
∈
∈
system is underactuated, as in the simple car, then controllability issues become considerably more complicated. The next concept is suitable for such systems.
STLC: Controllability that handles obstacles The controllability concept discussed so far has no concern for how far the trajectory travels in X before xG is reached. This issue becomes particularly important for underactuated systems and planning among obstacles. These concerns motivate a natural question: Is there a form of controllability that is naturally suited for obstacles? It should declare that if a state is reachable from another in the absence of differential constraints, then
it is also reachable with the given system x˙ = f(x, u). This can be expressed using time-limited reachable sets. Let R(x, U, t) denote the set of all states reachable
in time less than or equal to t, starting from x. A system x˙ = f(x, u) is called
small-time locally controllable (STLC) from xI if there exists some t > 0 such that
xI ∈ int(R(xI , U, t′)) for all t′ ∈ (0, t] (here, int denotes the interior of a set, as
Figure 15.2: If the system is STLC, then motions can be made in any direction, in an arbitrarily small amount of time.
defined in Section 4.1.1). If the system x˙ = f(x, u) is STLC from every xI ∈ X,
then the whole system is said to be STLC.
Consider using this definition to answer the question above. Since int(R(xI , U, t′))
is an open set, there must exist some small ǫ > 0 for which the open ball B(xI , ǫ) is a strict subset of int(R(xI , U, t′)). See Figure 15.2. Any point on the boundary
of B(xI , ǫ) can be reached, which means that a step of size ǫ can be taken in any direction, even though differential constraints exist. With obstacles, however, we have to be careful that the trajectory from xI to the surface of B(xI , ǫ) does not wander too far away.
Suppose that there is an obstacle region Xobs, and a violation-free state trajec- tory x˜ is given that terminates in xG at time tF and does not necessarily satisfy a given system. If the system is STLC, then it is always possible to find an- other trajectory, based on x˜, that satisfies the differential constraints. Apply the plan-and-transform method of Section 14.6.2. Suppose that intervals for potential replacement are chosen using binary recursive subdivision. Also suppose that an LPM exists that computes that shortest trajectory between any pair of states; this trajectory ignores obstacles but respects the differential constraints. Initially, [0, tF ] is replaced by a trajectory from the LPM, and if it is not violation-free, then [0, tF ] is subdivided into [0, tF /2] and [tF /2, tF ], and replacement is attempted on the smaller intervals. This idea can be applied recursively until eventually the segments are small enough that they must be violation-free.
This final claim is implied by the STLC property. No matter how small the intervals become, there must exist a replacement trajectory. If an interval is large, then there may be sufficient time to wander far from the original trajectory. How- ever, as the time interval decreases, there is not enough time to deviate far from the original trajectory. (This discussion assumes mild conditions on f, such as being Lipschitz.) Suppose that the trajectory is protected by a collision-free tube of radius ǫ. Thus, all points along the trajectory are at least ǫ from the boundary of Xfree. The time intervals can be chosen small enough to ensure that the tra- jectory deviations are less than ǫ from the original trajectory. Therefore, STLC is a very important property for a system to possess for planning in the presence of
obstacles. Section 15.4 covers some mathematical tools for determining whether a nonlinear system is STLC.
A concept closely related to controllability is accessibility, which is only con- cerned with the dimension of the reachable set. Let n be the dimension of X. If
there exists some t > 0 for which the dimension of R(xI , U, t) is n, then the system
is called accessible from xI . Alternatively, this may be expressed as requiring that int(R(xI , U, t)) /= ∅.
Example 15.3 (Accessibility) Recall the system from Section 13.1.3 in which the state is trapped on a circle. In this case X = R2, and the state transition
equation was specified by x˙ = yu and y˙ = −xu. This system is not accessible
because the reachable sets have dimension one. ．
A small-time version of accessibility can also be defined by requiring that there exists some t such that int(R(xI , , t′)) = for all t′ (0, t]. Accessibility is particularly important for systems with drift.
U / ∅ ∈