Lie Algebraic Methods in Nonlinear Control

Abstract

Lie algebraic methods generalize matrix methods and algebraic rank conditions to smooth nonlinear systems. They capture the essence of noncommuting flows and give rise to noncommutative analogues of Taylor expansions. Lie algebraic rank conditions determine controllability, observability, and optimality. Lie algebraic methods are also employed for state-space realization, control design, and path planning.

¹

Definition

This article considers generally nonlinear control systems (affine in the control) of the form

$$\displaystyle{ \begin{array}{ccl} \dot{x}& =&f_{0}(x) + u_{1}f_{1}(x) +\ldots u_{m}f_{m}(x) \\ y & =&\varphi (x) \end{array} }$$

(1)

where the state x takes values in $\mathbb{R}^{n}$, or more generally in an n-dimensional manifold Mⁿ, the f _i are smooth vector fields, $\varphi : \mathbb{R}^{n}\mapsto \mathbb{R}^{p}$ is a smooth output function, and the controls $u = (u_{1},\ldots,u_{m}): [0,T]\mapsto U$ are piecewise continuous, or, more generally, measurable functions taking values in a closed convex subset $U \subseteq R^{m}$ that contains 0 in its interior.

Lie algebraic techniques refers to analyzing the system (1) and designing controls and stabilizing feedback laws by employing relations satisfied by iterated Lie brackets of the system vector fields f _i .

Introduction

Systems of the form (1) contain as a special case time-invariant linear systems $\dot{x} = Ax + Bu,\;y = Cx$ (with constant matrices $A \in \mathbb{R}^{n\times n}$, $B \in \mathbb{R}^{n\times m}$, and $C \in \mathbb{R}^{p\times n}$) that are well-studied and are a mainstay of classical control engineering. Properties such as controllability, stabilizability, observability, and optimal control and various others are determined by relationships satisfied by higher-order matrix products of A, B, and C.

Since the early 1970s, it has been well understood that the appropriate generalization of this matrix algebra, and, e.g., invariant linear subspaces, to nonlinear systems is in terms of the Lie algebra generated by the vector fields f _i , integral submanifolds of this Lie algebra, and the algebra of iterated Lie derivatives of the output function.

The Lie bracket of two smooth vector fields $f,\,g: M\mapsto TM$ is defined as the vector field $[f,g]: M\mapsto TM$ that maps any smooth function $\varphi \in C^{\infty }(M)$ to the function $[f,g]\varphi = fg\varphi - gf\varphi$.

In local coordinates, if

$$\displaystyle\begin{array}{rcl} f(x)& =& \sum \limits _{i=1}^{n}f^{i}(x) \frac{\partial } {\partial x^{i}}\;\mbox{ and }\; {}\\ g(x)& =& \sum \limits _{i=1}^{n}g^{i}(x) \frac{\partial } {\partial x^{i}}, {}\\ \end{array}$$

then

$$\displaystyle\begin{array}{rcl} [f,g](x)& & =\sum \limits _{ i,j=1}^{n}\left (f^{j}(x) \frac{\partial g^{i}} {\partial x^{j}}(x)\right. {}\\ & & \left.\quad - g^{j}(x)\frac{\partial f^{i}} {\partial x^{j}}(x)\right ) \frac{\partial } {\partial x^{i}}. {}\\ \end{array}$$

With some abuse of notation, one may abbreviate this to $[f,g] = (Dg)f - (Df)g$, where f and g are considered as column vector fields and Df and Dg denote their Jacobian matrices of partial derivatives.

Note that with this convention the Lie bracket corresponds to the negative of the commutator of matrices: If $P,\,Q \in \mathbb{R}^{n\times n}$ define, in matrix notation, the linear vector fields f(x) = Px and g(x) = Qx, then $[f,g](x) = (QP - PQ)x = -[P,Q]x$.

Noncommuting Flows

Geometrically the Lie bracket of two smooth vector fields f₁ and f₂ is an infinitesimal measure of the lack of commutativity of their flows. For a smooth vector field f and an initial point x(0) = p ∈ M, denote by e^tfp the solution of the differential equation $\dot{x} = f(x)$ at time t. Then

$$\displaystyle\begin{array}{rcl} [f_{1},f_{2}]\varphi (p)& & =\lim _{t\rightarrow 0} \frac{1} {2t^{2}}\left (\varphi \left (e^{-tf_{2} }e^{-tf_{1} }e^{tf_{2} }e^{tf_{1} }p\right )\right. {}\\ & & \quad -\left.\varphi (p)\right ). {}\\ \end{array}$$

As a most simple example, consider parallel parking a unicycle, moving it sideways without slipping. Introduce coordinates (x, y, θ) for the location in the plane and the steering angle. The dynamics are governed by $\dot{x} = u_{1}\cos \theta$, $\dot{y} = u_{1}\sin \theta$, and $\dot{\theta }= u_{2}$ where the control u₁ is interpreted as the signed rolling speed and u₂ as the angular velocity of the steering angle. Written in the form (1), one has $f_{1} = (\cos \theta,\sin \theta,0)^{T}$ and $f_{2} = (0,0,1)^{T}$. (In this case the drift vector field f₀ ≡ 0 vanishes.) If the system starts at (0, 0, 0)^T, then via the sequence of control actions of the form turn left, roll forward, turn back, and roll backwards, one may steer the system to a point (0, Δ y, 0)^T with Δ y > 0. This sideways motion corresponds to the value (0, 1, 0)^T of the Lie bracket $[f_{1},f_{2}] = (-\sin \theta,\cos \theta,0)^{T}$ at the origin. It encapsulates that steering and rolling do not commute. This example is easily expanded to model, e.g., the sideways motion of a car, or a truck with multiple trailers; see, e.g., Bloch (2003), Bressan and Piccoli (2007), and Bullo and Lewis (2005). In such cases longer iterated Lie brackets correspond to the required more intricate control actions needed to obtain, e.g., a pure sideways motion.

In the case of linear systems, if the Kalman rank condition $\mathrm{rank}[B,\,AB,\,A^{2}B,\,\ldots A^{n-1}B] = n$ is not satisfied, then all solutions curves of the system starting from the same point x(0) = p are at all times T > 0 constrained to lie in a proper affine subspace. In the nonlinear setting the role of the compound matrix of that condition is taken by the Lie algebra $L = L(f_{0},f_{1},\ldots f_{m})$ of all finite linear combinations of iterated Lie brackets of the vector fields f _i . As an immediate consequence of the Frobenius integrability theorem, if at a point x(0) = p the vector fields in L span the whole tangent space, then it is possible to reach an open neighborhood of the initial point by concatenating flows of the system (1) that correspond to piecewise constant controls. Conversely, in the case of analytic vector fields and a compact set U of admissible control values, the Hermann-Nagano theorem guarantees that if the dimension of the subspace $L(p) =\{ f(p): f \in L\} <n$ is not maximal, then all such trajectories are confined to stay in a lower-dimensional proper integral submanifold of L through the point p. For a comprehensive introduction, see, e.g., the textbooks Bressan and Piccoli (2007), Isidori (1995), and Sontag (1998).

Controllability

Define the reachable set $\mathcal{R}_{T}(p)$ as the set of all terminal points x(T; u, p) at time T of trajectories of (1) that start at the initial point x(0) = p and correspond to admissible controls. Commonly known as the Lie algebra rank condition (LARC), the above condition determines whether the system is accessible from the point p, which means that for arbitrarily small time T > 0, the reachable set $\mathcal{R}_{T}(p)$ has nonempty n-dimensional interior. For most applications one desires stronger controllability properties. Most amenable to Lie algebraic methods, and practically relevant, is small-time local controllability (STLC): The system is STLC from p if p lies in the interior of $\mathcal{R}_{T}(p)$ for every T > 0. In the case that there is no drift vector field f₀, accessibility is equivalent to STLC. However, in general, the situation is much more intricate, and a rich literature is devoted to various necessary or sufficient conditions for STLC. A popular such condition is the Hermes condition. For this define the subspaces $\mathcal{S}^{1} = \mathrm{span}\{(\mathrm{ad}^{j}f_{0},f_{i}): 1 \leq j \leq m,\;j \in \mathbb{Z}^{+}\}$, and recursively $\mathcal{S}^{k+1} = \mathrm{span}\{[g_{1},g_{k}]: g_{1} \in \mathcal{S}^{1},\;g_{k} \in \mathcal{S}^{k}\}$. Here $(ad^{0}f,g) = g$, and recursively $(ad^{k+1}f,g) = [f,(ad^{k}f,g)]$. The Hermes condition guarantees in the case of analytic vector fields and, e.g., $U = [-1,1]^{m}$ that if the system satisfies the (LARC) and for every k ≥ 1, $\mathcal{S}^{2k}(p) \subseteq \mathcal{S}^{2k-1}(p)$, then the system is (STLC). For more general conditions, see Sussmann (1987) and also Kawski (1990) for a broader discussion.

The importance and value of Lie algebraic conditions may in large part be ascribed to their geometric character, their being invariant under coordinate changes and feedback. In particular, in the analytic case, the Lie relations completely determine the local properties of the system, in the sense that Lie algebra homomorphism between two systems gives rise to a local diffeomorphism that maps trajectories to trajectories (Sussmann 1974).

Exponential Lie Series

A central analytic tool in Lie algebraic methods that takes the role of Taylor expansions in classical analysis of dynamical system is the Chen-Fliess series which associates to every admissible control $u: [0,T]\mapsto U$ a formal power series

$$\displaystyle{ \mathrm{CF}(u,T) =\sum _{I}\int _{0}^{T}du^{I} \cdot X_{ i_{1}}\ldots X_{i_{s}} }$$

(2)

over a set $\{X_{0},X_{1},\ldots X_{m}\}$ of noncommuting indeterminates (or letters). For every multi-index $I = (i_{1},i_{2},\ldots \imath _{s}) \in \{ 0,1,\ldots m\}^{s}$, s ≥ 0, the coefficient of X _I is the iterated integral defined recursively

$$\displaystyle{ \int _{0}^{T}du^{(I,j)} =\int _{ 0}^{T}\left (\int _{ 0}^{t}u^{I}\right )\,du_{ j}(t). }$$

(3)

Upon evaluating this series via the substitutions $X_{i}\longleftarrow f_{j}$, it becomes an asymptotic series for the propagation of solutions of (1): For $f_{j},\varphi$ analytic, U compact, p in a compact set, and T ≥ 0 sufficiently small, one has

$$\displaystyle{ \varphi (x(t;u,p)) =\sum _{I}\int _{0}^{T}du^{I} \cdot \left (f_{ i_{1}}\ldots f_{i_{s}}\varphi \right )(p). }$$

(4)

One application of particular interest is to construct approximating systems of a given system (1) that preserve critical geometric properties, but which have an simpler structure. One such class is that of nilpotent systems, that is, systems whose Lie algebra $L = L(f_{0},f_{1},\ldots f_{m})$ is nilpotent, and for which solutions can be found by simple quadratures. While truncations of the Chen-Fliess series never correspond to control systems of the same form, much work has been done in recent years to rewrite this series in more useful formats. For example, the infinite directed exponential product expansion in Sussmann (1986) that uses Hall trees immediately may be interpreted in terms of free nilpotent systems and consequently helps in the construction of nilpotent approximating systems. More recent work, much of it of a combinatorial algebra nature and utilizing the underlying Hopf algebras, further simplifies similar expansions and in particular yields explicit formulas for a continuous Baker-Campbell-Hausdorff formula or for the logarithm of the Chen-Fliess series (Gehrig and Kawski 2008).

Observability and Realization

In the setting of linear systems a well-defined algebraic sense dual to the concept of controllability is that of observability. Roughly speaking the system (1) is observable if knowledge of the output $y(t) =\varphi (x(t;u,p))$ over an arbitrarily small interval suffices to construct the current state x(t; u, p) and indeed the past trajectory x( ⋅  ; u, p). In the linear setting observability is equivalent to the rank condition $\mathrm{rank}[C^{T},(CA)^{T},\ldots,(CA^{n-})^{T}] = n$ being satisfied. In the nonlinear setting, the place of the rows of this compound matrix is taken by the functions in the observation algebra, which consists of all finite linear combinations of iterated Lie derivatives $f_{i_{s}}\cdots f_{i_{1}}\varphi$ of the output function.

Similar to the Hankel matrices introduced in the latter setting, in the case of a finite Lie rank, one again can use the output algebra to construct realizations in the form of (1) for systems which are initially only given in terms of input-output descriptions, or in terms of formal Fliess operators; see, e.g., Fliess (1980), Gray and Wang (2002), and Jakubczyk (1986) for further reading.

Optimal Control

In a well-defined geometric way, conditions for optimal control are dual to conditions for controllability and thus are directly amenable to Lie algebraic methods. Instead of considering a separate functional

$$\displaystyle{ J(u) =\psi (x(T;u,p)) +\int _{ 0}^{T}L(t,x(t;u,p),u(t))\,dt }$$

(5)

to be minimized, it is convenient for our purposes to augment the state by, e.g., defining $\dot{x}_{0} = 1$ and $\dot{x}_{n+1} = L(x_{0},x,u)$. For example, in the case of time-optimal control, one again obtains an enlarged system of the same form (1); else one utilizes more general Lie algebraic methods that also apply to systems not necessarily affine in the control.

The basic picture for systems with a compact set U of admissible values of the controls involves the attainable funnel $\mathcal{R}_{\leq T}(p)$ consisting of all trajectories of the system (1) starting at x(0) = p that correspond to admissible controls. The trajectory corresponding to an optimal control u^∗ must at time T lie on the boundary of the funnel $\mathcal{R}_{\leq T}(p)$ and hence also at all prior times (using the invariance of domain property implied by the continuity of the flow). Hence one may associate a covector field along such optimal trajectory that at every time points in the direction of an outward normal. The Pontryagin Maximum Principle is a first-order characterization of such trajectory covector field pairs. Its pointwise maximization condition essentially says that if at any time t₀ ∈ [0, T] one replaces the optimal control $u^{{\ast}}(\cdot )$ by any admissible control variation on an interval $[t_{0},t_{0}+\varepsilon ]$, then such variation may be transported along the flow to yield, in the limit as $\varepsilon \searrow 0$, an inward pointing tangent vector to the reachable set $\mathcal{R}_{T}(p)$ at $x(T;u^{{\ast}},p)$. To obtain stronger higher-order conditions for maximality, one may combine several such families of control variations. The effects of such combinations are again calculated in terms of iterated Lie brackets of the vector fields f _i . Indeed, necessary conditions for optimality, for a trajectory to lie on the boundary of the funnel $\mathcal{R}_{\leq T}(p)$, immediately translate into sufficient conditions for STLC, for the initial point to lie in the interior of $\mathcal{R}_{T}(p)$, and vice versa. For recent work employing Lie algebraic methods in optimality conditions, see, e.g., Agrachev et al. (2002).

Summary and Future Research

Lie algebraic techniques may be seen as a direct generalization of matrix linear algebra tools that have proved so successful in the analysis and design of linear systems. However, in the nonlinear case, the known algebraic rank conditions still exhibit gaps between necessary and sufficient conditions for controllability and optimality. Also, new, not yet fully understood, topological and resonance obstructions stand in the way of controllability implying stabilizability. Systems that exhibit special structure, such as living on Lie groups, or being second order such as typical mechanical systems, are amenable to further refinements of the theory; compare, e.g., the use of affine connections and the symmetric product in Bullo et al. (2000). Other directions of ongoing and future research involve the extension of Lie algebraic methods to infinite dimensional systems and to generalize formulas to systems with less regularity; see, e.g., the work by Rampazzo and Sussmann (2007) on Lipschitz vector fields, thereby establishing closer connections with nonsmooth analysis (Clarke 1983) in control.

Cross-References

• Differential Geometric Methods in Nonlinear Control

• Feedback Linearization of Nonlinear Systems

• Lie Algebraic Methods in Nonlinear Control