Lefschetz numbers in control theory

Introduction

The goal is to develop some applications of the Lefschetz fixed point theory techniques, already available in dynamics, in control theory.

A discrete dynamical system on a manifold $M$ is simply a map $f:M\rightarrow M.$ Then the next state $f(x)$ of the system depends only on the current one, $x\in M$. The equilibrium set $C=\{x\in M:f(x)=x\}$ of the system is the set of fixed points of $f.$

It is treated via the so-called Coincidence Problem: Given two maps $f,g:N\rightarrow M$ between two $n$-dimensional manifolds, what can be said about the coincidence set $C$ of all $x$ such that $f(x)=g(x)$?

One of the main tools is the Lefschetz number $\lambda_{fg}$. The famous Lefschetz coincidence theorem states that if $\lambda_{fg}\neq0$ then there is at least one coincidence, i.e., $C\neq\varnothing.$

In case of a controlled dynamical system, the next state $f(x,u)$ depends not only on the current one, $x\in M,$ but also on the input, $u\in U.$

A discrete time control system is given by a pair:

• a fiber bundle with the bundle projection $U\rightarrow N^{\underrightarrow{~\ \ \ g\ \ \ ~~}}M$, and
• a map $f:N\rightarrow M.$

Here,

• $U$ is the space of inputs,
• $M$ is the space of states, and
• $N$ is the space of pairs of states and inputs of the system.

Just as before, the equilibrium set of the system $C=\{x\in M:f(x,u)=x\}$ is the coincidence set of the pair $(f,g).$ However now we have to deal with the fact that the dimensions of $N$ and $M$ are not equal anymore! As a result, the Lefschetz number does not do as good a job detecting coincidences and has to be replaced with the Lefschetz homomorphism $\Lambda_{fg}:H_{k}(N,A)\rightarrow H_{k-n}(M),$ $k=0,1,...$. See Lefschetz theory for coincidences.

In many applications the state space $M$ is a nontrivial manifold. For example,

• $M=\mathbf{T}^{n}=(\mathbf{S}^{1})^{n},$ where $\mathbf{T}^{n}$ is the $n$ dimensional torus, is the configuration space of a robotic arm with $n$ revolving joints; or
• $M={\bf R}^{3}\times SO(3)$, where $SO(3)$ is the rotation group, is the configuration space of a rigid body in space (or the operational space of a robotic arm).

Typically, the space of pairs of states and inputs is the product of the two: $N=M\times U.$ However nontrivial bundles are also common. For example, if $M=T\mathbf{S}^{2}$, the tangent bundle of the $2$-sphere $\mathbf{S}^{2},$ is the state space of a spherical pendulum with a gas jet control which is always directed in the tangent space, then $N$ is an $\mathbf{R}^{2}$-bundle over $M$ not homeomorphic to $\mathbf{R}^{2}\times M$.

Since our knowledge of the model is inevitably imprecise, we have to deal with perturbations of the system. The space of inputs $U$ is the set of known, or uncertain, parameters. On the other hand, perturbations may be understood as variations of the unknown, or certain, parameters of the system. Therefore, if the system depends continuously on these parameters, the change of $M,N,$ and $f$ is also continuous. This means that we have to consider spaces homeomorphic (or homotopy equivalent) to $M,N$ and maps homotopic to $f.$ An appropriate tool for such a study is homology. Indeed, the homology of $M,N,f$ remains constant under homeomorphisms and homotopies and can be rigorously and effectively computed.

Normally the perturbations, and homotopies, of $f$ are assumed to be small. However unless actual estimates are available, we don't know how small these perturbations are in real life. For example, cascading failures of the electric grid may be explained by the lack of robustness of the system and the underestimation of the magnitude of possible disturbances. Therefore in order to take into account the worst possible scenario we should consider arbitrary homotopies of $f.$ An example of such a control system is the human organism as it preserves stability inside under extraordinary amount of uncertainty on the outside.

We apply Lefschetz coincidence theory to study existence of equilibria and reachability/controllability for (discrete and continuous time) systems determined by maps homotopic to $f$.

The secondary objective is to study robustness of some of these properties under small perturbations because sometimes they may produce dramatic changes in the behavior of the system. We consider situations when this change is the loss of equilibria of the system.

Equilibria of discrete time control systems

Suppose that $(M,\partial M)$ is a compact orientable manifold with $\dim M=n$. A map $g:U\times M\rightarrow M$ determines a discrete time control system $D_{g}$, with $U$ the space of inputs, $M$ the space of states of the system. The systems corresponding to maps homotopic to $g$ we will perturbations of $D_g$.

As before suppose $\{a_{1}^{k},...,a_{m_{k}}^{k}\}$ is a basis for $H_{k}(M)$ and $\{x_{1}^{k},...,x_{m_{k}}^{k}\}$ the corresponding dual basis for $H^{k}(M).$ The Lefschetz class of $g$ corresponding to $v\in H_{\ast}(U)$ is defined via the same trace formula as before: $$L(g_{v})=(-1)^{n|v|}\sum_{k}(-1)^{k}\sum_{j}x_{j}^{k}\frown g_{\ast}(a_{j} ^{k}\otimes v)\neq 0.$$

Theorem (Existence of equilibria). If $L(g_{v})\neq 0$ for some $v\in H_{\ast}(U)$, then every perturbation of the discrete time system $D_{g}$ has an equilibrium, $g(a,u)=a$.

For example, if $$M=\mathbf{T}^{2},U=\mathbf{S}^{1},g(x_{1},x_{2} ,u)=(x_{1},u),$$ then a simple computation shows that $L(g_{v})=2(1\otimes v).$ Therefore every perturbation of $D_{g}$ has an equilibrium.

Corollary. Suppose $M=\mathbf{S}^{n},$ and suppose one of the following conditions is satisfied:

• (1) $g_{\ast}(1\otimes v)\neq0$ for some $v\in H_{n}(U);$ or
• (2) $g_{\ast}(O_{M}\otimes1)\neq(-1)^{n+1}O_{M};$

Then the discrete time system $D_{f}$ has an equilibrium.

Proof. Since $\dim M=n,$ only $v\in H_{0}(U),...,H_{n}(U)$ can appear in the formula for $L(g_{v})$. In fact, $k+|v|\leq n.$ Now, for $M=\mathbf{S}^{n}$ we have \[ L(g_{v})=(-1)^{n|v|}(1\frown g_{\ast}(1\otimes v)+(-1)^{n}\overline{O} _{M}\frown g_{\ast}(O_{M}\otimes v)), \] where $\overline{O}_{M}$ is the dual of $O_{M}.$ The first term vanishes unless $|v|=0$ or $n.$ The second term vanishes unless $|v|=0.$ Therefore,

• if $|v|=n,$ then $L(g_{v})=$ $g_{\ast}(1\otimes v);$
• if $|v|=0,$ then $L(g_{v})=1+(-1)^{n}\overline{O}_{M}\frown g_{\ast}(O_{M}\otimes1).$ $\blacksquare$

If $f:M\times M\rightarrow M$ is the multiplication of a compact Lie group, then $D_{f}$ has a equilibrium.

The following condition ensures that the space is nice enough to make our analysis possible. Subset $F$ satisfies condition (*) if one of the following three conditions holds:

• (a1) $M$ is a surface, i.e., $n=2;$ or
• (a2) $F$ is acyclic, i.e., $H_{k}(F)=0$ for $k=1,2,...$; or
• (a3) every component of $F$ is a homology $m$-sphere, i.e., $H_{k}(F)=0$ for $k\neq0,m,$ for the following values of $m$ and $n$:

1. $m=4$ and $n\geq6;$
2. $m=5$ and $n\geq7;$
3. $m=12$ and $n=7,8,9,14,15,16,....$.

In the new setting we restate the corollary about removability of coincidences.

Theorem (Robustness of equilibria). Suppose $U$ is a manifold, $D_{g}$ has only one equilibrium state, $g(a,u)=a\in M\backslash\partial M$, and suppose condition (*) is satisfied for the equilibrium manifold $F=\{u\in U:g(a,u)=a\}$ and $F\cap A=\varnothing$. Suppose also that $$L(g_{1})=\sum_{k}(-1)^{k}Trace(\overline{g}_{\ast k})=0,$$ where $\overline{g}(\cdot)=g(\cdot,u_{0})$. Then there is an arbitrarily small perturbation of the discrete time system $D_{g}$ which has no equilibria.

In particular the trace condition above is satisfied if $M=\mathbf{S}^{n},$ $n$ odd, and $\overline{g}:\mathbf{S}^{n}\rightarrow\mathbf{S}^{n}$ has degree $1$ (compare to condition (2) of the above Corollary).

One can say now that in the former case the equilibrium is robust and in the latter it's not.

Equilibria of continuous systems

Suppose $K$ is a compact orientable connected manifold with boundary $\partial K$, $\dim K=k,$ $N$ is a manifold. Then $\dim TK=2k,$ where the tangent bundle $TK$ on $K$.

A continuous time control system $C_{f}$ is defined as a commutative diagram \[ \begin{matrix} {} N & ^{\underrightarrow{\quad f\quad}} & TK,\\ \downarrow^{p} & \swarrow_{\pi_{K}} & \\ K & & \end{matrix} \ \ \ \] where $p:N\rightarrow K$ is a fiber bundle over $K$ and $\pi_{K}$ is its projection$.$ In other words we have a parametrized vector field on $K.$

To apply the coincidence result from the last section we need the target manifold to be compact. Therefore instead of $TK$ we consider $T_{d}K\subset TK,$ the tangent disk bundle, with $T_{s}K=\partial T_{d}K$ its sphere bundle. This simply means that the velocity of the system is bounded. Assume that we have $f:(N,A)\rightarrow(T_{d}K,T_{s}K).$ This means that some inputs produce the maximal velocity at some states.

Now $(x,u)\in N$ is an equilibrium pair, and $x$ is an equilibrium state, if $f(x,u)=(x,0)\in T_{d}K.$ In other words, it is a coincidence of the pair $f,g,$ where $g(x,u)=(x,0)$ for all $x.$

Theorem (Existence of equilibria). If

• $\chi(N,A)\neq 0$, and
• $f_{\ast}:H_{2k}(N,A)\rightarrow H_{2k}(T_{d} K,T_{s}K)=\mathbf{Q}$ is nonzero,

then every perturbation of the continuous time system $C_{f}$ has an equilibrium.

Proof. Since $f,g:N\rightarrow T_{d}K=M$ are homotopic, we can use the naturality of the Lefschetz homomorphism to obtain the following: $$\Lambda_{fg}(z)=\Lambda_{ff}(z)=\Lambda_{Id,Id}f_{\ast}(z), z\in H_{\ast}(N,A),$$ where $Id:N\rightarrow N$ is the identity. But $\Lambda_{Id,Id}(w)\neq0$ only if $|w|=2k=\dim T_{d}K$. Therefore

• $\Lambda_{fg}(z)=\chi(N,A)f_{\ast}(z)$ if $|z|=2k$ or
• $\Lambda_{fg}(z)=0$ otherwise.

Now we apply the theorem from the last section to complete the proof. $\blacksquare$

The second condition of the theorem is satisfied, in particular, when

• $(N,A)=(T_{d}K,T_{s}K)$ and
• $f_{\ast}=Id_{\ast}.$

In case of a dynamical system we have $N=K,$ and $f$ is homotopic to the inclusion $M\hookrightarrow TM.$ Therefore the theorem implies the well known corollary to the Poincare-Hopf theorem (more general than the Hairy Ball Theorem):

Corollary. A vector field on a manifold with a nonzero Euler characteristic has a zero.

Now about removing equilibria. The corollary from the last section implies the following.

Theorem (Robustness of equilibria). Suppose $C_{f}$ has only one equilibrium state, $f(a,u)=(a,0)\in TK.$ Suppose condition (*) (with $n=2k)$ is satisfied for the equilibrium manifold $F=\{u\in U:f(a,u)=(a,0)\}.$ Then, if

• $\chi(N,A)=0$, or
• $f_{\ast}:H_{2k}(N,A)\rightarrow H_{2k}(T_{d}K,T_{s}K)=\mathbf{Q}$ is zero,

then there is an arbitrarily small perturbation of the continuous time system $C_{f}$ which has no equilibria.

Even when we know only the state and input spaces, we can gain insight from this theorem into the possible dynamics of the system. For example, the condition of the theorem holds if $H_{2k}(N,A)=0.$ In particular, it holds if the dimension of the state space $K$ is larger than that of the input space $U=p^{-1}(x)$, $k>m.$

Controllability of discrete systems

The results in the last two section involve only a single application of the map while most problems of control theory deal with multiple iterations.

Suppose system $D_{f}$ is given by $f:N=M\times U\rightarrow M.$ We make two assumptions about the behavior of the system.

• First, $f(\partial M\times U)\subset\partial M,$ i.e., the trajectories never leave the boundary.
• Second, there is some $U^{\prime}\subset U$ such that $f(K\times U^{\prime})\subset\partial K,$ i.e., inputs from a certain set of controls always take the system to the boundary.

As a result $f$ can be treated as a map of pairs, $$f:(N,A)=(M,\partial M)\times(U,U^{\prime})\rightarrow(M,\partial M).$$

The system $D_{f}$ is called controllable if any state can be reached from any other state, i.e., for each pair of states $x,y\in M$ there are inputs $u_{0},...,u_{s}\in U$ such that $x_{1}=f(u_{0},x),x_{2}=f(u_{1},x_{1}),...,y=f(u_{s},x_{s}),$ notation $x\rightsquigarrow_{f}y.$ This notion is generalized in two ways. First, we will allow the possibility of an arbitrary state reached from any state in a particular subset of $M.$ Second, we allow for (arbitrary) perturbations of $f.$

Definition. Given $L\subset M,$ let $$f^{\prime}:(L,L^{\prime})\times(U,U^{\prime })\rightarrow(M,\partial M)$$ be the restriction of $f,$ where $L^{\prime }=L\cap\partial M.$ Then the system is called robustly controllable from $L$ if for any map $f_{0}$ homotopic to $f^{\prime},$ maps $f_{1},...,f_{s}$ homotopic to $f,$ and for each $y\in M$ there are $x\in L$ and inputs $u_{0},...,u_{s}\in U,$ such that $$x_{1}=f_{0}(x,u_{0}),x_{2}=f_{1}(x_{1},u_{1}),...,y=f_{s}(x_{s},u_{s}).$$

Theorem (Sufficient condition of robust controllability). Suppose that there are $a_{0}\in H_{\ast}(L,L^{\prime}),$ $v_{0},...,v_{s}\in H_{\ast}(U,U^{\prime})$ such that $$a_{1}=f_{\ast}^{\prime}(a_{0}\otimes v_{0}),a_{2}=f_{\ast}(a_{1}\otimes v_{1}),...,a_{s}=f_{\ast}(a_{s-1}\otimes v_{s-1}),$$ where $a_{s}=O_{M}\in H_{n}(M,\partial M),$ the fundamental class of $M.$ Then the discrete time system $D_{f}$ is robustly controllable from $L$.

Proof. Define a map $F_{s}:(L,L^{\prime})\times(U,U^{\prime})^{s+1}\rightarrow (M,\partial M)$ for $s=1,2,...$ by \[ F_{s}(x,u_{0},...,u_{s})=f_{s}(...f_{1}(f_{0}(x,u_{0}),u_{1}),...,u_{s}). \] Then $x\rightsquigarrow_{f}F_{s}(x,u_{0},...,u_{s}).$ Therefore controllability from $L$ means that $F_{s}:L\times U^{s}\rightarrow M$ is onto for some $s$. By the Surjectivity Corollary, if \[ F_{s\ast}:H_{n}((L,L^{\prime})\times(U,U^{\prime})\times...\times(U,U^{\prime }))\rightarrow H_{n}(M,\partial M)=\mathbf{Q} \] is nonzero then every map $F_{s}^{\prime}$ homotopic to $F_{s}$ is onto. But $F_{s\ast}$ is given by the composition \begin{align*} F_{s\ast} & :H_{\ast}(L,L^{\prime})\otimes H_{\ast}(U,U^{\prime})\otimes...\otimes H_{\ast}(U,U^{\prime})^{\underrightarrow{~\ \ \ f_{\ast }^{\prime}\otimes Id\ \ \ ~~}}\\ & H_{\ast}(M,\partial M)\otimes H_{\ast}(U,U^{\prime})\otimes...\otimes H_{\ast}(U,U^{\prime})^{\underrightarrow{~\ \ \ f_{\ast}\otimes Id\ \ \ ~~} }...\text{.} \end{align*} Now if $f_{\ast}(...f_{\ast}(f_{\ast}^{\prime}(a_{0}\otimes v_{0})\otimes v_{2})\otimes...\otimes v_{s})\neq0$ for some $a_{0}\in H_{\ast}(L,L^{\prime }),$ $v_{0},...,v_{s}\in H_{\ast}(U,U^{\prime})$ such that $|a_{0}|+|v_{0}|+...+|v_{s}|=n,$ then $F_{s\ast}$ is nonzero. $\blacksquare$

If $U=\mathbf{S}^{m}$ then the theorem applies only if $m$ divides $n.$ Indeed, we have \[ a_{i+1}=f_{\ast}(a_{i}\otimes z)\in H_{(i+1)m}(M), \] where $z$ is the generator of $H_{m}(\mathbf{S}^{m}).$

The theorem involves multiple iterations of $f_{\ast}$ while it is preferable to have a condition involving only $f_{\ast}$ itself. Let's consider a case when this is possible.

Consider first a simple example, $$M_{i}=U=\mathbf{S}^{1},f:\mathbf{S}^{1}\times\mathbf{T}^{n}\rightarrow\mathbf{T}^{n},$$ and let $$f(u,x_{1} ,...,x_{n})=(u,x_{1},...,x_{n-1}).$$ This setup may serve as a model for a robotic arm with $n$ joints where only the first joint can be controlled directly and the next state of a joint is read from the current state of the previous joint. Then this system is robustly controllable by the theorem. Indeed after $n$ iterations with inputs $u_{1},...,u_{n}$ the system's state is $(u_{n},...,u_{1}).$

More generally, suppose the state space $M$ has the product structure, $$M=K_{1}\times...\times K_{s},$$ where $K_{i}$ are manifolds of dimensions $n_{i}.$ Suppose $f=(f_{1},...,f_{s})$, where $f_{i}:U\times M\rightarrow K_{i}.$ Suppose for $i=1,...,s,$ maps $f_{i}^{a}:K_{i-1}\rightarrow K_{i},$ where $K_{0}=U,$ are given by $$f_{i}^{a}(x_{i-1})=f_{i}(a_{0},...,a_{i-2},x_{i-1},a_{i},...,a_{s}).$$ If all $f_{i}^{a}$ are onto then the system is controllable. According to the Surjectivity Corollary it suffices to require this:

• all $f_{i\ast}^{a}:H_{n_{i}}(K_{i-1})\rightarrow H_{n_{i}}(K_{i})$ are nonzero, $i=1,...,s$.

It is clear that what we have is the finite time reachability, i.e., every state can be reached in a finite number, $s,$ of steps and that number is common for all states.

The above theorem can be understood as follows. The restrictions of $f,$ $$f_{0}:L\times U\rightarrow M_{1},f_{1}:M_{1}\times U\rightarrow M_{2},...,f_{s}:M_{s-1}\times U\rightarrow M_{s}=M,$$ are onto, where $M_{0},M_{1},...$ are submanifolds of $M$ with $\dim M_{i}=|a_{i}|.$ The robustness of each of these properties can be tested by means of Removability Corollary.

Note: Our definition is a stronger version of a more common definition of robustness when only "local", or "small", perturbations are allowed. In our context they are $\varepsilon $-homotopies.

Note: Controllability of continuous time systems requires dealing with infinite dimensional spaces.

Proofs are in P. Saveliev, Applications of Lefschetz numbers in control theory, SIAM Journal of Control and Optimization (2005) 5, 1677-1690