Nonholonomic System Theory

This section gives some precision to the term nonholonomic, which was used loosely in Chapters 13 and 14. Furthermore, small-time controllability (STLC), which

Figure 15.12: Each of the nine base words is depicted [64]. The last two are only valid for small motions; they are magnified five times and the robot outline is not drawn.

Figure 15.13: The 40 optimal curve types for the differential-drive robot, sorted by symmetry class [64].

Figure 15.14: A slice of the optimal curves is shown for qI = (x, y, π ) and qG = (0, 0, 0) [64]. Level sets of the optimal cost-to-go G∗ are displayed. The coordinates correspond to a differential drive with r = L = 1 in (13.16).

4

was defined in Section 15.1.3, is addressed. The presentation given here barely scratches the surface of this subject, which involves deep mathematical principles from differential geometry, algebra, control theory, and mechanics. The intention is to entice the reader to pursue further study of these topics; see the suggested literature at the end of the chapter.

• • 1. Control-Affine Systems

Nonholonomic system theory is restricted to a special class of nonlinear systems. The techniques of Section 15.4 utilize ideas from linear algebra. The main concepts will be formulated in terms of linear combinations of vector fields on a smooth manifold X. Therefore, the formulation is restricted to control-affine systems, which were briefly introduced in Section 13.2.3. For these systems, x˙ = f(x, u) is of the form

m

-

x˙ = h0(x) + hi(x)ui, (15.52)

i=1

in which each hi is a vector field on X.

The vector fields are expressed using a coordinate neighborhood of X. Usually, m < n, in which n is the dimension of X. Unless otherwise stated, assume that U = Rm. In some cases, U may be restricted.

Each action variable ui ∈ R can be imagined as a coefficient that determines

how much of hi(x) is blended into the result x˙ . The drift term h0(x) always remains and is often such a nuisance that the driftless case will be the main focus. This

means that h0(x) = 0 for all x ∈ X, which yields

m

-

x˙ = hi(x)ui. (15.53)

i=1

The driftless case will be used throughout most of this section. The set h1, . . ., hm, is referred to as the system vector fields. It is essential that U contains at least an open set that contains the origin of Rm. If the origin is not contained in U, then the system is no longer driftless.7

Control-affine systems arise in many mechanical systems. Velocity constraints on the C-space frequently are of the Pfaffian form (13.5). In Section 13.1.1, it was explained that under such constraints, a configuration transition equation (13.6) can be derived that is linear if q is fixed. This is precisely the driftless form (15.53) using X = . Most of the models in Section 13.1.2 can be expressed in this form. The Pfaffian constraints on configuration are often called kinematic constraints because they arise due to the kinematics of bodies in contact, such as a wheel rolling. The more general case of (15.52) for a phase space X arises from dynamic constraints that are obtained from Euler-Lagrange equation (13.118) or Hamilton’s equations (13.198) in the formulation of the mechanics. These constraints capture conservation laws, and the drift term usually appears due to momentum.

C

Example 15.5 (A Simplified Model for Differential Drives and Cars) Both the simple-car and the differential-drive models of Section 13.1.2 can be expressed

in the form (15.53) after making simplifications. The simplified model, (15.48), can be adapted to conveniently express versions of both of them by using different

restrictions to define U. The third equation of (15.48) can be reduced to θ˙ = u2

without affecting the set of velocities that can be achieved. To conform to (15.53), the equations can then be written in a linear-algebra form as

x˙

 

y˙ =

cos θ

sin θ u

 

1

0

+

0

u . (15.54)

2

θ˙  0  1

This makes it clear that there are two system vector fields, which can be combined by selecting the scalar values u1 and u2. One vector field allows pure translation, and the other allows pure rotation. Without restrictions on U, this system be- haves like a differential drive because the simple car cannot execute pure rotation. Simulating the simple car with (15.54) requires restrictions on U (such as requiring that u1 be 1 or 1, as in Section 15.3.2). This is equivalent to the unicycle from Figure 13.5 and (13.18).

−

7Actually, if the convex hull of U contains an open set that contains the origin, then a driftless system can be simulated by rapid switching.

Note that (15.54) can equivalently be expressed as

x˙ 

y˙

cos θ 0 （u ＼

=

θ˙

sin θ 0 1

0 1 u2





(15.55)

by organizing the vector fields into a matrix. ．

In (15.54), the vector fields were written as column vectors that combine lin- early using action variables. This suggested that control-affine systems can be

alternatively expressed using matrix multiplication in (15.55). In general, the vector fields can be organized into an n × m matrix as

H(x) = h1(x) h2(x) · · · hm(x) . (15.56) In the driftless case, this yields

「

x˙ = H(x) u (15.57)

as an equivalent way to express (15.53)

It is sometimes convenient to work with Pfaffian constraints,

g1(x)x˙ 1 + g2(x)x˙ 2 + · · · + gn(x)x˙ n = 0, (15.58) instead of a state transition equation. As indicated in Section 13.1.1, a set of k

independent Pfaffian constraints can be converted into a state transition equation

with m = (n k) action variables. The resulting state transition equation is a driftless control-affine system. Thus, Pfaffian constraints provide a dual way of specifying driftless control-affine systems. The k Pfaffian constraints can be expressed in matrix form as

−

G(x) x˙ = 0, (15.59)

which is the dual of (15.57), and G(x) is a k n matrix formed from the gi coefficients of each Pfaffian constraint. Systems with drift can be expressed in a Pfaffian-like form by constraints

×

g0(x) + g1(x)x˙ 1 + g2(x)x˙ 2 + · · · + gn(x)x˙ n = 0. (15.60)

• • 1. Determining Whether a System Is Nonholonomic

The use of linear algebra in Section 15.4.1 suggests further development of alge- braic concepts. This section briefly introduces concepts that resemble ordinary linear algebra but apply to linear combinations of vector fields. This provides the concepts and tools needed to characterize important system properties in the remainder of this section. This will enable the assessment of whether a system is nonholonomic and also whether it is STLC. Many of the constructions are named after Sophus Lie (pronounced “lee”), a mathematician who in the nineteenth cen- tury contributed many ideas to algebra and geometry that happen to be relevant in the study of nonholonomic systems (although that application came much later).

• • • 1. Completely integrable or nonholonomic?

Every control-affine system must be one or the other (not both) of the following:

• • • • 1. Completely integrable: This means that the Pfaffian form (15.59) can be obtained by differentiating k equations of the form fi(x) = 0 with respect to time. This case was interpreted as being trapped on a surface in Section

13.1.3. An example of being trapped on a circle in R2 was given in (13.22).

• • • • 1. Nonholonomic: This means that the system is not completely integrable. In this case, it might even be possible to reach all of X, even if the number of action variables m is much smaller than n, the dimension of X.

In this context, the term holonomic is synonymous with completely integrable, and nonintegrable is synonymous with nonholonomic. The term nonholonomic is sometimes applied to non-Pfaffian constraints [588]; however, this will be avoided here, in accordance with mechanics literature [112].

The notion of integrability used here is quite different from that required for (14.1). In that case, the state transition equation needed to be integrable to obtain integral curves from any initial state. This was required for all systems considered in this book. By contrast, complete integrability implies that the system can be expressed without even using derivatives. This means that all integral curves can eventually be characterized by constraints that do not involve derivatives.

To help understand complete integrability, the notion of an integral curve will be generalized from one to m dimensions. A manifold M ⊆ X is called an integral manifold of a set of Pfaffian constraints if at every x ∈ M, all vectors in the tangent

space Tx(M) satisfy the constraints. For a set of completely integrable Pfaffian constraints, a partition of X into integral manifolds can be obtained by defining maximal integral manifolds from every x X. The resulting partition is called a foliation, and the maximal integral manifolds are called leaves [872].

∈

Example 15.6 (A Foliation with Spherical Leaves) As an example, sup- pose X = Rn and consider the Pfaffian constraint

x1x˙ 1 + x2x˙ 2 + · · · xn_x˙ _n = 0. (15.61)

This is completely integrable because it can be obtained by differentiating the equation of a sphere,

x2 + x2 + · · · x2 − r2 = 0, (15.62)

1

2

n

with respect to time (r is a constant). The particular sphere that is obtained via integration depends on an initial state. The foliation is the collection of all

concentric spheres that are centered at the origin. For example, if X = R3, then a maximal integral manifold arises for each point of the form (0, 0, r). In each case,

it is a sphere of radius r. The foliation is generated by selecting every r ∈ [0, ∞).

．

The task in this section is to determine whether a system is completely inte- grable. Imagine someone is playing a game with you. You are given an control- affine system and asked to determine whether it is completely integrable. The person playing the game with you can start with equations of the form hi(x) = 0 and differentiate them to obtain Pfaffian constraints. These can then be converted into the parametric form to obtain the state transition equation (15.53). It is easy to construct challenging problems; however, it is very hard to solve them. The concepts in this section can be used to determine only whether it is possible to win such a game. The main tool will be the Frobenius theorem, which concludes whether a system is completely integrable. Unfortunately, the conclusion is ob- tained without producing the integrated constraints hi(x) = 0. Therefore, it is important to keep in mind that “integrability” does not mean that you can inte- grate it to obtain a nice form. This is a challenging problem of reverse engineering. On the other hand, it is easy to go in the other direction by differentiating the constraints to make a challenging game for someone else to play.

• • • 1. Distributions

A distribution8 expresses a set of vector fields on a smooth manifold. Suppose that a driftless control-affine system (15.53) is given. Recall the vector space defi- nition from Section 8.3.1 or from linear algebra. Also recall that a state transition equation can be interpreted as a vector field if the actions are fixed and as a vector

space if the state is instead fixed. For U = Rm and a fixed x ∈ X, the state

transition equation defines a vector space in which each hi evaluated at x is a basis vector and each ui is a coefficient. For example, in (15.54), the vector fields h1 and h2 evaluated at q = (0, 0, 0) become [1 0 0]T and [0 0 1]T , respectively. These serve as the basis vectors. By selecting values of u R2, a 2D vector space results. Any vector of the form [a 0 b]T can be represented by setting u1 = a and u2 = b. More generally, let (x) denote the vector space obtained in this way for any x X.

∈

∈

△

The dimension of a vector space is the number of independent basis vectors. Therefore, the dimension of (x) is the rank of H(x) from (15.56) when evaluated at the particular x X. Now consider defining (x) for every x X. This yields a parameterized family of vector spaces, one for each x X. The result could just as well be interpreted as a parameterized family of vector fields. For example,

∈

∈ △ ∈

△

consider actions for i from 1 to m of the form ui = 1 and uj = 0 for all i j. If

the action is held constant over all x X, then it selects a single vector field hi

∈

from the collection of m vector fields:

x˙ = hi(x). (15.63)

Using constant actions, an m-dimensional vector space can be defined in which each vector field hi is a basis vector (assuming the hi are linearly independent),

8This distribution has nothing to do with probability theory. It is just an unfortunate coin- cidence of terminology.

and the ui ∈ R are the coefficients:

u1h1(x) + u2h2(x) + · · · + um_h_m(x). (15.64)

This idea can be generalized to allow the ui to vary over X. Thus, rather than having u constant, it can be interpreted as a feedback plan π : X U, in which the action at x is given by u = π(x). The set of all vector fields that can be obtained as

→

π1(x)h1(x) + π2(x)h2(x) + · · · + πm(x)hm(x) (15.65)

is called the distribution of the set h1, . . . , hm of vector fields and is denoted as

{ }

. If is obtained from an control-affine system, then is called the system distribution. The resulting set of vector fields is not quite a vector space because

△ △ △

the nonzero coefficients πi do not necessarily have a multiplicative inverse. This is required for the coefficients of a vector field and was satisfied by using R in the case of constant actions. A distribution is instead considered algebraically as a

module [469]. In most circumstances, it is helpful to imagine it as a vector space (just do not try to invert the coefficients!). Since a distribution is almost a vector space, the span notation from linear algebra is often used to define it:

△ = span{h1, h2, . . . , hm}. (15.66)

Furthermore, it is actually a vector space with respect to constant actions u Rm. Note that for each fixed x X, the vector space (x) is obtained, as defined earlier. A vector field f is said to belong to a distribution if it can be expressed using (15.65). If for all x X, the dimension of (x) is m, then is called a nonsingular distribution (or regular distribution). Otherwise, is called a singular

△

∈ △ △

△

∈ △

∈

distribution, and the points x X for which the dimension of (x) is less than m are called singular points. If the dimension of (x) is a constant c over all x X, then c is called the dimension of the distribution and is denoted by dim( ). If the vector fields are smooth, and if π is restricted to be smooth, then a smooth distribution is obtained, which is a subset of the original distribution.

△

△ ∈

∈ △

As depicted in Figure 15.15, a nice interpretation of the distribution can be given in terms of the tangent bundle of a smooth manifold. The tangent bundle was defined for X = Rn in (8.9) and generalizes to any smooth manifold X to

obtain

I

T (X) = Tx(X). (15.67)

x∈X

The tangent bundle is a 2n-dimensional manifold in which n is the dimension of X. A phase space for which x = (q, q˙) is actually T ( ). In the current setting, each element of T (X) yields a state and a velocity, (x, x˙ ). Which pairs are possible for

C

a driftless control-affine system? Each △(x) indicates the set of possible x˙ values

for a fixed x. The point x is sometimes called the base and △(x) is called the

fiber over x in T (X). The distribution △ simply specifies a subset of Tx(X) for every x ∈ X. For a vector field f to belong to △, it must satisfy f(x) ∈ △(x) for all x ∈ X. This is just a restriction to a subset of T (X). If m = n and the

Tx(X)

△(x)

X x

Figure 15.15: The distribution △ can be imagined as a slice of the tangent bundle

T (X). It restricts the tangent space at every x ∈ X.

system vector fields are independent, then any vector field is allowed. In this case,

△ includes any vector field that can be constructed from the vectors in T (X).

Example 15.7 (The Distribution for the Differential Drive) The system in (15.54) yields a two-dimensional distribution:

△ = span{[cos θ sin θ 0] , [0 0 1] }. (15.68)

T T

The distribution is nonsingular because for any (x, y, θ) in the coordinate neigh- borhood, the resulting vector space △(x, y, θ) is two-dimensional. ．

Example 15.8 (A Singular Distribution) Consider the following system, which is given in [478]:

x˙ 1

x˙





2 = h1(x)u1 + h2(x)u2 + h3(x)u3

x˙ 3

 x1   x1x2 



=

1 + x

u

+

(1 + x )x

x1

u

+

x

(15.69)

u .

 3 1 

1

3 2 2 1 3

x2 0





The distribution is

△ = span{h1, h2, h3}. (15.70)

The first issue is that for any x R3, h2(x) = h1(x)x2, which implies that the vector fields are linearly dependent over all of R3. Hence, this distribution is singular because m = 3 and the dimension of ∆(x) is 2 if x1 = 0. If x1 = 0, then

∈

△

/

the dimension of ∆(x) drops to 1. The dimension of is not defined because the dimension of ∆(x) depends on x. ．

(a) (b)

Figure 15.16: (a) The effect of the first two primitives. (b) The effect of the last two primitives.

A distribution can alternatively be defined directly from Pfaffian constraints. Each gi(x) = 0 is called an annihilator because enforcing the constraint eliminates many vector fields from consideration. At each x X, (x) is defined as the set of all velocity vectors that satisfy all k Pfaffian constraints. The constraints themselves can be used to form a codistribution, which is a kind of dual to the distribution. The codistribution can be interpreted as a vector space in which each constraint is a basis vector. Constraints can be added together or multiplied by any c R, and there is no effect on the resulting distribution of allowable vector fields.

∈

∈ △

• • • 1. Lie brackets

The key to establishing whether a system is nonholonomic is to construct mo- tions that combine the effects of two action variables, which may produce motions in a direction that seems impossible from the system distribution. To motivate the coming ideas, consider the differential-drive model from (15.54). Apply the following piecewise-constant action trajectory over the interval [0, 4∆t]:

 (1, 0) for t ∈ [0, ∆t)

(−1, 0) for t ∈ [2∆t, 3∆t)

u(t) =  (0, 1) for t ∈ [∆t, 2∆t)

 (0, −1) for t ∈ [3∆t, 4∆t] .

(15.71)

The action trajectory is a sequence of four motion primitives: 1) translate forward,

1. rotate forward, 3) translate backward, and 4) rotate backward.

The result of all four motion primitives in succession from qI = (0, 0, 0) is shown in Figure 15.16. It is fun to try this at home with an axle and two wheels (Tinkertoys work well, for example). The result is that the differential drive moves sideways!9 From the transition equation (15.54) such motions appear impossible. This is a beautiful property of nonlinear systems. The state may wiggle its way in directions that do not seem possible. A more familiar example is parallel parking a car. It is known that a car cannot directly move sideways; however, some wiggling motions can be performed to move it sideways into a tight parking space. The actions we perform while parking resemble the primitives in (15.71).

Algebraically, the motions of (15.71) appear to be checking for commutativity. Recall from Section 4.2.1 that a group G is called commutative (or Abelian) if ab = ba for any a, b G. A commutator is a group element of the form aba−1b−1. If the group is commutative, then aba−1b−1 = e (the identity element) for any a, b G. If a nonidentity element of G is produced by the commutator, then the group is not commutative. Similarly, if the trajectory arising from (15.71) does not form a loop (by returning to the starting point), then the motion primitives do not commute. Therefore, a sequence of motion primitives in (15.71) will be referred to as the commutator motion. It will turn out that if the commutator motion cannot produce any velocities not allowed by the system distribution, then the system is completely integrable. This means that if we are trapped on a surface, then it is impossible to leave the surface by using commutator motions.

∈

∈

Now generalize the differential drive to any driftless control-affine system that has two action variables:

x˙ = f(x)u1 + g(x)u2. (15.72)

Using the notation of (15.53), the vector fields would be h1 and h2; however, f and g are chosen here to allow subscripts to denote the components of the vector field in the coming explanation.

Suppose that the commutator motion (15.71) is applied to (15.72) as shown in Figure 15.17. Determining the resulting motion requires some general computa- tions, as opposed to the simple geometric arguments that could be made for the differential drive. If would be convenient to have an expression for the velocity obtained in the limit as ∆t approaches zero. This can be obtained by using Tay- lor series arguments. These are simplified by the fact that the action history is piecewise constant.

The coming derivation will require an expression for x¨ under the application of a constant action. For each action, a vector field of the form x˙ = h(x) is obtained. Upon differentiation, this yields

dh

x¨ =

dt

∂h dx

= =

∂x dt

∂h

x˙ =

dx

∂h

h(x). (15.73)

dx

This follows from the chain rule because h is a function of x, which itself is a function of t. The derivative ∂h/∂x is actually an n × n Jacobian matrix, which

9It also moves slightly forward; however, this can be eliminated by either lengthening the time of the third primitive or by considering the limit as ∆ approaches zero.

x(3∆t)

−f

x(2∆t)

−g

g

f

x(0)

x(∆t)

Figure 15.17: The velocity obtained by the Lie bracket can be approximated by a sequence of four motion primitives.

is multiplied by the vector x˙ . To further clarify (15.73), each component can be expressed as

d n ∂h

x¨ = h (x(t)) = - i h . (15.74)

j=1

j

j=1

j

i

dt

i

∂x

j

Now the state trajectory under the application of (15.71) will be determined using the Taylor series, which was given in (14.17). The state trajectory that results from the first motion primitive u = (1, 0) can be expressed as

x(∆t) = x(0) + ∆t x˙ (0) + 1 (∆t)2 x¨(0) + · · ·

2

1 ∂f

2 I

= x(0) + ∆t f(x(0)) + (∆t) I

f(x(0)) + · · · ,

(15.75)

2 ∂x Ix(0)

which makes use of (15.73) in the second line. The Taylor series expansion for the second primitive is

1 ∂g

2 I

x(2∆t) = x(∆t) + ∆t g(x(∆t)) + (∆t) I

g(x(∆t)) + · · · . (15.76)

2 ∂x Ix(∆t)

An expression for g(x(∆t)) can be obtained by using the Taylor series expansion in (15.75) to express x(∆t). The first terms after substitution and simplification are

x(2∆t) = x(0) + ∆t (f + g) + (∆t)2 （ 1

2 ∂x

∂f ∂g 1 ∂g

f + f + g + · · · . (15.77)

＼

∂x

2 ∂x

To simplify the expression, the evaluation at x(0) has been dropped from every occurrence of f and g and their derivatives.

The idea of substituting previous Taylor series expansions as they are needed can be repeated for the remaining two motion primitives. The Taylor series ex- pansion for the result after the third primitive is

x(3∆t) = x(0) + ∆t g + (∆t)2 （ ∂g f − ∂f g + 1

∂x

∂x

2 ∂x

∂g

g + · · · . (15.78)

＼

Finally, the Taylor series expansion after all four primitives have been applied is

x(4∆t) = x(0) + (∆t)2 （ ∂g f − ∂f g＼ + · · · . (15.79)

∂x

∂x

Taking the limit yields

lim

x(4∆t) − x(0) = ∂g f − ∂f g, (15.80)

∆t→0

(∆t)2

∂x ∂x

which is called the Lie bracket of f and g and is denoted by [f, g]. Similar to (15.74), the ith component can be expressed as

[f, g]i

j

n

= f

• （

j=1

∂gi j ∂x

− g ∂fi ＼ . (15.81)

j

The Lie bracket is an important operation in many subjects, and is related to the Poisson and Jacobi brackets that arise in physics and mathematics.

j ∂x

Example 15.9 (Lie Bracket for the Differential Drive) The Lie bracket should indicate that sideways motions are possible for the differential drive. Consider tak-

ing the Lie bracket of the two vector fields used in (15.54). Let f = [cos θ sin θ 0]T and g = [0 0 1]T . Rename h1 and h2 to f and g to allow subscripts to denote the components of a vector field.

By applying (15.81), the Lie bracket [f, g] is

[f, g]1

[f, g]2

[f, g]3

∂g1

= f1 ∂x − g

∂g2

= f1 ∂x − g

∂g3

= f1 ∂x − g

∂f1 + f

1 ∂x

∂f2 + f

1 ∂x

∂f3 + f

1 ∂x

∂g1

2 ∂y − g

∂g2

2 ∂y − g

∂g3

2 ∂y − g

∂f1 + f

2 ∂y

∂f2 + f

2 ∂y

∂f3 + f

2 ∂y

∂g1

3 ∂θ − g

∂g2

3 ∂θ − g

∂g3

3 ∂θ − g

∂f1 = sin θ

3 ∂θ

∂f2 = − cos θ

3 ∂θ

∂f3 = 0.

3 ∂θ

(15.82)

The resulting vector field is [f, g] = [sin θ cos θ 0] , which indicates the side- ways motion, as desired. When evaluated at q = (0, 0, 0), the vector [0 1 0] is obtained. This means that performing short commutator motions wiggles the differential drive sideways in the y direction, which we already knew from Figure

T

T

−

−

−

15.16. ．

Example 15.10 (Lie Bracket of Linear Vector Fields) Suppose that each vector field is a linear function of x. The n n Jacobians ∂f/∂x and ∂g/∂x are constant.

×

As a simple example, recall the nonholonomic integrator (13.43). In the linear- algebra form, the system is

x˙ 1 1

 



x˙ = 0

 u +

 0 

1

u . (15.83)

 2   1   2

x˙ 3

−x2

x1

x˙ 3

−x2

x1

Let f = h1 and g = h2. The Jacobian matrices are

Using (15.80),

∂f 0 0 0

∂x 0 −1 0

0 0 0

=

and

∂g 0 0 0

∂x 1 0 0

0 0 0

=

. (15.84)

∂g ∂f

−

0 0 0  1  0 0 0  0 

0

f g =

∂x ∂x

0 0 0 0 − 0 0 0 1 = 0

. (15.85)

1 0 0 −x2 0 −1 0 −x1

2

This result can be verified using (15.81).

．

• • • 1. The Frobenius Theorem

The Lie bracket is the only tool needed to determine whether a system is com- pletely integrable (holonomic) or nonholonomic (not integrable). Suppose that a system of the form (15.53) is given. Using the m system vector fields h1, . . ., hm there are (m) Lie brackets of the form [hi, hj ] for i < j that can be formed. A

2

distribution △ is called involutive [133] if for each of these brackets there exist m

coefficients ck ∈ R such that

m

-

[hi, hj ] = ck_h_k. (15.86)

k=1

In other words, every Lie bracket can be expressed as a linear combination of the system vector fields, and therefore it already belongs to . The Lie brackets are unable to escape and generate new directions of motion. We did not need to consider all n2 possible Lie brackets of the system vector fields because it turns out that [hi, hj ] = [hj , hi] and consequently [hi, hi] = 0. Therefore, the definition of involutive is not altered by looking only at the (m) pairs.

△

△

−

2

If the system is smooth and the distribution is nonsingular, then the Frobenius theorem immediately characterizes integrability:

A system is completely integrable if and only if it is involutive.

Proofs of the Frobenius theorem appear in numerous differential geometry and control theory books [133, 156, 478, 846]. There also exist versions that do not require the distribution to be nonsingular.

Determining integrability involves performing Lie brackets and determining whether (15.86) is satisfied. The search for the coefficients can luckily be avoided by using linear algebra tests for linear independence. The n m matrix H(x), which was defined in (15.56), can be augmented into an n (m + 1) matrix H′(x) by adding [hi, hj ] as a new column. If the rank of H′(x) is m + 1 for any pair hi and hj , then it is immediately known that the system is nonholonomic. If the

×

×

rank of H′(x) is m for all Lie brackets, then the system is completely integrable.

Driftless linear systems, which are expressed as x˙ = Bu for a fixed matrix B, are completely integrable because all Lie brackets are zero.

Example 15.11 (The Differential Drive Is Nonholonomic) For the differ-

ential drive model in (15.54), the Lie bracket [f, g] was determined in Example 15.9 to be [sin θ − cos θ 0] . The matrix H (q), in which q = (x, y, θ), is

T ′

cos θ 0 sin θ





H′(q) = sin θ 0 − cos θ . (15.87)

 0 1 0 

The rank of H′(q) is 3 for all q (the determinant of H′(q) is 1). Therefore, by the Frobenius theorem, the system is nonholonomic. ．

∈ C

Example 15.12 (The Nonholonomic Integrator Is Nonholonomic) We would hope that the nonholonomic integrator is nonholonomic. In Example 15.10, the

Lie bracket was determined to be [0 0 2]T . The matrix H′(q) is

H′(q) = 



1 0 0

0 1 0 , (15.88)

−x2 x1 2

which clearly has full rank for all q ∈ C. ．

Example 15.13 (Trapped on a Sphere) Suppose that the following system is given:

 







x˙ 1

x˙ 2

x2

= −x1

u1 + 0 

x3

u2, (15.89)

x˙ 3  0  −x1

for which X = R3 and U = R2. Since the vector fields are linear, the Jacobians are constant (as in Example 15.10):

∂f  0 1 0 ∂g  0 0 1

= −1 0 0 and

∂x  0 0 0

 

= 0 0 0 . (15.90)

∂x −1 0 0

Using (15.80),

∂g ∂f

 0 0 1  x2 

 0 1 0  x3   0 

f g =

−

∂x ∂x

0 0 0 −x1

− −1 0 0 0 = x3

. (15.91)

−1 0 0  0 

This yields the matrix

 0 0 0 −x1

−x2

H′(x) =

x2 −x1 0

x3 0 −x1





. (15.92)

 0 x3 −x2

The determinant is zero for all x R3, which means that [f, g] is never linearly independent of f and g. Therefore, the system is completely integrable.10

∈

The system can actually be constructed by differentiating the equation of a sphere. Let

f(x) = x2 + x2 + x2 − r2 = 0, (15.93)

1

2

3

and differentiate with respect to time to obtain

x1x˙ 1 + x2x˙ 2 + x3x˙ 3 = 0, (15.94)

which is a Pfaffian constraint. A parametric representation of the set of vectors that satisfy (15.94) is given by (15.89). For each (u1, u2) R2, (15.89) yields a vector that satisfies (15.94). Thus, this was an example of being trapped on a

∈

sphere, which we would expect to be completely integrable. It was difficult, how- ever, to suspect this using only (15.89). ．

• • 1. Determining Controllability

Determining complete integrability is the first step toward determining whether a driftless control-affine system is STLC. The Lie bracket attempts to produce motions in directions that do not seem to be allowed by the system distribution. At each q, a velocity not in (q) may be produced by the Lie bracket. By work- ing further with Lie brackets, it is possible to completely characterize all of the directions that are possible from each q. So far, the Lie brackets have only been applied to the system vector fields h1, . . ., hm. It is possible to proceed further by applying Lie bracket operations on Lie brackets. For example, [h1, [h1, h2]] can be computed. This might generate a vector field that is linearly independent of all of the vector fields considered in Section 15.4.2 for the Frobenius theorem. The main idea in this section is to apply the Lie bracket recursively until no more independent vector fields can be found. The result is called the Lie algebra. If the number of independent vector fields obtained in this way is the dimension of X, then it turns out that the system is STLC.

△

10This system is singular at the origin. A variant of the Frobenius theorem given here is technically needed.

• • • 1. The Lie algebra

The notion of a Lie algebra is first established in general. Let V be any vector space with coefficients in R. In V , the vectors can be added or multiplied by elements of R; however, there is no way to “multiply” two vectors to obtain a third. The Lie algebra introduces a product operation to V . The product is called

a bracket or Lie bracket (considered here as a generalization of the previous Lie bracket) and is denoted by [ , ] : V V V .

· · × →

To be a Lie algebra obtained from V , the bracket must satisfy the following three axioms:

• • • • 1. Bilinearity: For any a, b ∈ R and u, v, w ∈ V ,

[au + bv, w] = a[u, w] + b[v, w]

(15.95)

[u, av + bw] = a[u, w] + b[u, w].

• • • • 1. Skew symmetry: For any u, v ∈ V ,

[u, v] = −[v, u]. (15.96)

This means that the bracket is anti-commutative.

• • • • 1. Jacobi identity: For any u, v, w ∈ V ,

[[u, v], w] + [[v, w], u] + [[w, u], v] = 0. (15.97)

Note that the bracket is not even associative.

Let (V ) denote the Lie algebra of V . This is a vector space that includes all elements of V and any new elements that can be obtained via Lie bracket oper- ations. The Lie algebra (V ) includes every vector that can be obtained from any finite number of nested Lie bracket operations. Thus, describing a Lie algebra requires characterizing all vectors that are obtained under the algebraic closure of the bracket operation. Since (V ) is a vector space, this is accomplished by find- ing a basis of independent vectors of which all elements of (V ) can be expressed as a linear combination.

L

L

L

L

Example 15.14 (The Vector Cross Product) Let V be the vector space over R3 that is used in vector calculus. The basis elements are often denoted as ˆı,

ˆ, and kˆ. A bracket for this vector space is simply the cross product

[u, v] = u × v. (15.98)

It can be verified that the required axioms of a Lie bracket are satisfied.

One interesting property of the cross product that is exploited often in analytic geometry is that it produces a vector outside of the span of u and v. For example, let W be the two-dimensional subspace of vectors

W = span{ˆı,ˆ}. (15.99)

The cross product always yields a vector that is a multiple of kˆ, which lies outside

of V if the product is nonzero. This behavior is very similar to constructing vector fields that lie outside of △ using the Lie bracket in Section 15.4.2. ．

Example 15.15 (Lie Algebra on Lie Groups) Lie groups are the most im- portant application of the Lie algebra concepts. Recall from Section 4.2.1 the notion of a matrix group. Important examples throughout this book have been SO(n) and SE(n). If interpreted as a smooth manifold, these matrix groups are examples of Lie groups [63]. In general, a Lie group G is both a differentiable

manifold and a group with respect to some operation ◦ if and only if:

1. The product a ◦ b, interpreted as a function from G × G → G, is smooth.
2. The inverse a−1, interpreted as a function from G to G, is smooth.

The two conditions are needed to prevent the group from destroying the nice properties that come with the smooth manifold. An important result in the study of Lie groups is that all compact finite-dimensional Lie groups can be represented as matrix groups.

For any Lie group, a Lie algebra can be defined on a special set of vector fields. These are defined using the left translation mapping Lg : x 1→ gx. The vector

field formed from the differential of Lg is called a left-invariant vector field. A Lie algebra can be defined on the set of these fields. The Lie bracket definition depends on the particular group. For the case of GL(n), the Lie bracket is

[A, B] = AB − BA. (15.100)

In this case, the Lie bracket clearly appears to be a test for commutativity. If the matrices commute with respect to multiplication, then the Lie bracket is zero. The Lie brackets for SO(n) and SE(n) are given in many texts on mechanics and control [156, 846]. The Lie algebra of left-invariant vector fields is an important

structure in the study of nonlinear systems and mechanics. ．

• • • 1. Lie algebra of the system distribution

Now suppose that a set h1, . . ., hm of vector fields is given as a driftless control- affine system, as in (15.53). Its associated distribution is interpreted as a vector space with coefficients in R, and the Lie bracket operation was given by (15.81). It can be verified that the Lie bracket operation in (15.81) satisfies the required axioms for a Lie algebra.

△

As observed in Examples 15.9 and 15.10, the Lie bracket may produce vector fields outside of . By defining the Lie algebra of to be all vector fields that can be obtained by applying Lie bracket operations, a potentially larger distribution

△ △

L(△) is obtained. The Lie algebra can be expressed using the span notation by

including h1, . . ., hm and all independent vector fields generated by Lie brackets. Note that no more than n independent vector fields can possibly be produced.

Example 15.16 (The Lie Algebra of the Differential Drive) The Lie al- gebra of the differential drive (15.54) is

T

T

T

L(△) = span{[cos θ sin θ 0] , [0 0 1] , [sin θ − cos θ 0] }. (15.101)

This uses the Lie bracket that was computed in (15.82) to obtain a three-dimensional Lie algebra. No further Lie brackets are needed because the maximum number of

independent vector fields has been already obtained. ．

Example 15.17 (A Lie Algebra That Involves Nested Brackets) The pre- vious example was not very interesting because the Lie algebra was generated after computing only one bracket. Suppose that X = R5 and U = R2. In this case,

there is room to obtain up to three additional, linearly independent vector fields.

The dimension of the Lie algebra may be any integer from 2 to 5.

Let the system be

x˙ 1

 

x˙

 1 

0

0

1

x˙



3

x˙

2

4

x

x





=

2 u1

3

• 0

0



0



u2. (15.102)

x˙ 5

x4

0

This is a chained-form system, which is a concept that becomes important in Section 15.5.2.



The first Lie bracket produces

[h1, h2] = [0 0 − 1 0 0] . (15.103)

T

Other vector fields that can be obtained by Lie brackets are

[h1, [h1, h2]] = [0 0 0 1 0]T (15.104)

and

[h1, [h1, [h1, h2]]] = [0 0 0 0 1]T . (15.105)

The resulting five vector fields are independent over all x ∈ R5. This includes

h1, h2, and the three obtained from Lie bracket operations. Independence can be established by placing them into a 5 × 5 matrix,

 1 0 0 0 0



0 , (15.106)



which has full rank for all x R5. No additional vector fields can possibly be independent. Therefore, the five-dimensional Lie algebra is

0

∈

L(△) = span{h1, h2, [h1, h2], [h1, [h1, h2]], [h1, [h1, [h1, h2]]]}. (15.107)

．

• • • 1. Philip Hall basis of a Lie algebra

Determining the basis of a Lie algebra may be a long and tedious process. The combinations of Lie brackets in Example 15.17 were given; however, it is not known in advance which ones will produce independent vector fields. Numerous Lie brackets may be needed, including some that are nested, such as [[h1, h2], h3]. The maximum depth of nested Lie bracket operations is not known a priori. Therefore, a systematic search must be performed (this can in fact be modeled as a discrete planning problem) by starting with h1, . . ., hm and iteratively generating new, independent vector fields using Lie brackets.

One popular approach is to generate the Philip Hall basis (or P. Hall basis) of the Lie algebra ( ). The construction of the basis essentially follows breadth- first search, in which the search depth is defined to be the number of nested levels of bracket operations. The order (or depth) d of a Lie product is defined recursively as follows. For the base case, let d(hi) = 1 for any of the system vector fields. For any Lie product [φ1, φ2], let

L △

d([φ1, φ2]) = d(φ1) + d(φ2). (15.108)

Thus, the order is just the nesting depth (plus one) of the Lie bracket operations. For example, d([h1, h2]) = 2 and d([h1, [h2, h3]]) = 3.

In addition to standard breadth-first search, pruning should be automatically

performed to ensure that the skew symmetry and Jacobi identities are always utilized to eliminate redundancy. A P. Hall basis is a sequence, = (φ1, φ2,

PH

. . .), of Lie products for which:

• • • • 1. The system vector fields hi are the first m elements of PH.
        2. If d(φi) < d(φj ), then i < j.
        3. Each [φi, φj ] ∈ PH if and only if: a) φi, φj ∈ PH and i < j, and b) either

φj = hi for some i or φj = [φl, φr] for some φl, φr ∈ PH such that l ≤ i.

It is shown in many algebra books (e.g., [861]) that this procedure results in a basis for the Lie algebra ( ). Various algorithms for computing the basis are evaluated in [299].

L △

Example 15.18 (P. Hall Basis Up to Depth Three) The P. Hall basis sorts the Lie products into the following sequence, which is obtained up to depth d = 3:

So far, the only Lie product eliminated by the Jacobi identity is [h1, [h2, h3]] be- cause

[h1, [h2, h3]] = [h2, [h1, h3]] − [h3, [h1, h2]]. (15.109)

Note that all of the Lie products given here may not be linearly independent vector

fields. For a particular system, linear independence tests should be performed to delete any linearly dependent vector fields from the basis. ．

When does the sequence PH terminate? Recall that dim(L(△)) can be no greater than n, because x( ) Tx(X). In other words, at every state x X, the number of possible independent velocity vectors is no more than the dimension of the tangent space at x. Therefore, can be terminated once n independent vector fields are obtained because there is no possibility of finding more. For some systems, there may be a depth k after which all Lie brackets are zero. Such systems are called nilpotent of order k. This occurs, for example, if all components of all vector fields are polynomials. If the system is not nilpotent, then achieving termination may be difficult. It may be the case that dim( ( )) is strictly less than n, but this is usually not known in advance. It is difficult to determine whether more Lie brackets are needed to increase the dimension or the limit has already been reached.

PH

L △

L △ ⊆ ∈

• • • 1. Controllability of driftless systems

The controllability of a driftless control-affine system (15.53) can be characterized using the Lie algebra rank condition (or LARC). Recall the definition of STLC from Section 15.1.3. Assume that either U = Rm or U at least contains an open

set that contains the origin of Rm. The Chow-Rashevskii theorem [112, 156, 846]

states:

A driftless control-affine system, (15.53), is small-time locally controllable (STLC) at a point x ∈ X if and only if dim(Lx(△)) = n, the dimension of X.

If the condition holds for every x X, then the whole system is STLC. In- tegrability can also be expressed in terms of dim( ( )). Assume as usual that m < n. The three cases are:

L △

∈

• • • • 1. dim(L(△)) = m the system is completely integrable;
        2. m < dim(L(△)) < n the system is nonholonomic, but not STLC;
        3. dim(L(△)) = n the system is nonholonomic and STLC.

(15.110)

Example 15.19 (Controllability Examples) The differential drive, nonholo- nomic integrator, and the system from Example 15.17 are all STLC by the Chow- Rashevskii theorem because dim( ( )) = n. This implies that the state can be changed in any direction, even though there are differential constraints. The state can be made to follow arbitrarily close to any smooth curve in X. A method that achieves this based on the Lie algebra is given in Section 15.5.1. The fact that these systems are STLC assures the existence of an LPM that satisfies the

L △

topological property of Section 14.6.2. ．

• • • 1. Handling Control-Affine Systems with Drift

Determining whether a system with drift (15.52), is STLC is substantially more difficult. Imagine a mechanical system, such as a hovercraft, that is moving at a high speed. Due to momentum, it is impossible from most states to move in certain directions during an arbitrarily small interval of time. One can, however, ask whether a system is STLC from a state x X for which h0(x) = 0. For a mechanical system, this usually means that it starts at rest. If a system with drift is STLC, this intuitively means that it can move in any direction by hovering around states that are close to zero velocity for the mechanical system.

∈

The Lie algebra techniques can be extended to determine controllability for sys- tems with drift; however, the tools needed are far more complicated. See Chapter 7 of [156] for more complete coverage. Even if dim( ( )) = n, it does not nec- essarily imply that the system is STLC. It does at least imply that the system is accessible, which motivates the definition given in Section 15.1.3. Thus, the set of achievable velocities still has dimension n; however, motions in all directions may not be possible due to drift. To obtain STLC, a sufficient condition is that the set

L △

of possible values for x˙ contains an open set that contains the origin.

The following example clearly illustrates the main difficultly with establishing whether a system with drift is STLC.

Example 15.20 (Accessible, Not STLC) The following simple system clearly illustrates the difficulty caused by drift and was considered in [741]. Let X = R2,

U = R, and the state transition equation be

x˙ 1 = u

1

x˙ 2

= x2. (15.111)

This system is clearly not controllable in any sense because x2 cannot be decreased. The vector fields are h0(x) = [0 x2]T and h1(x) = [1 0]T . The first independent

1

Lie bracket is

[h1, [h0, h1]] = [0 − 2]. (15.112)

The two-dimensional Lie algebra is

L(△) = span{h1, [h1, [h0, h1]]}, (15.113)

which implies that the system is accessible. It is not STLC, however, because the bracket [h1, [h0, h1]] was constructed using h0 and was combined in an unfortunate way. This bracket is indicating that changing x2 is possible; however, we already

know that it is not possible to decrease x2. Thus, some of the vector fields obtained from Lie brackets that involve h0 may have directional constraints. ．

In Example 15.20, [h1, [h0, h1]] was an example of a bad bracket [925] because it obstructed controllability. A method of classifying brackets as good or bad has been developed, and there exist theorems that imply whether a system with drift is STLC by satisfying certain conditions on the good and bad brackets. Intuitively, there must be enough good brackets to neutralize the obstructions imposed by the bad brackets [156, 925].