$\def\conf{\mathtt{conf}} \def\cov{\mathtt{cov}} \def\Int{\mathbb{Z}} \def\Real{\mathbb{R}} \def\Comp{\mathbb{C}} \def\ZN{\Int_N} \def\one{{\mathbf 1}} \def\attr{{\mathfrak{a}}} \def\U{{\mathcal U}} \def\Ed{{\mathcal E}} \def\Rd{{\Real}^d} \def\cN{{\mathbf N}} \def\OO{{\mathcal O}} \def\DD{{\mathcal D}} \def\HH{{\mathcal H}} \def\NN{{\mathcal N}} \def\VV{{\mathcal V}} \def\domain{{\mathcal{B}}} \def\ii{{\mathbf i}} \def\T{{\mathbb T}} \def\S{{\mathbb S}} \def\mod{{\mathit mod}} \def\Cycle{{\mathbf \sigma}} \def\prob{{\mathbb P}} \def\ex{{\mathbb E}} \def\codim{{\mathit{codim}}} \def\paths{{\mathcal P}} \def\sens{{\mathcal S}} \def\measurements{{\mathcal E}} \def\indep{{\mathcal I}} \def\one{\mathbb{1}} $

topological perplexity in feedback stabilization




yuliy baryshnikov


mathematics and ECE University of Illinois






supported by onr and afosr

introduction

Consider a nonlinear control system $$ \dot{x}=f(x,u), x\in M, u\in U. $$
Here $x\in M$, the configuration space of the system, and $u$ is the control. We will assume that $M$ is a smooth manifold with boundary, for example a domain in $\Real^d$.

Given an attractor, does there exist a feedback control, stabilizing on it?

An attractor is an embedded submanifold $A\subset M$ equipped with a tangent vector field ${\xi_\attr}$.
Such an attractor can be a fixed point, a periodic trajectory or some more general limiting behavior.

More precisely,

Given an attractor $\attr=(A,\xi_\attr)$, find a vector field $\xi$ on $M$, such that $\xi|_A=\xi_\attr$, and any trajectory of $\xi$ converges to $A$.

In this talk we will concentrate on the fully actuated systems, such that $U_x=T_xM$ for all $x\in M$.

The full rank condition makes the local stabilization task look trivial. (It is useful to contrast this with the situation of Brockett's theorem.)
However, globally such a vector field might fail to exist.

Consider the simplest task of stabilizing at a given point $\attr$ in an annulus $M$. If a continuous feedback control did exist, it would result in a vector field on $M$ such that the flow along it would retract $M$ onto $\attr$.

This is clearly impossible, as $M$ is not contractible. Hence, the vector field \[ \xi=f(x, k(x)) \] whose trajectories converge to $\attr$ necessarily is discontinuous.

emergence of topological perplexity

The standard approach to handle this difficulty is to add a barrier function expunging the system away from the infeasible region.

This leads, however, to appearance of regions where the system slows down dramatically.

To avoid arbitrary slowdowns of the system, it is necessary to introduce the interfaces where the vector field is discontinuous.
It is important to differentiate these interfaces from those in hybrid systems, where discontinuity does not lead to loss of the uniqueness.

We call a feedback function $k$ nonstalling if the vector field $\xi=f(x,k(x))$ is nonvanishing outside the attractor $\attr$ (where the stationary points might be part fo the design) and the set of discontinuities of $k$.


The locus where the nonstalling feedback function $k$ is discontinuous is called a cut.

Control-theoretic literature tends to ignore the cuts as long as they have measure zero (or are small in some other sense). We argue that cuts are important both from conceptual and applied viewpoints.

Philosophically, discontinuities are related to the perplexities of choice. Buridan's donkey, and analysis paralysis are among the example of the perplexities caused by impossibility to create a continuously depending on the environment course of actions.
As a decision maker approaches the positions where the feedback control is discontinuous, a different regime (of decision making) should be adopted, at significant overhead.

From the control-theoretic viewpoint, the nontrivial structure of the cut set increases the complexity of the algorithms driving the system.

One way to approach this rigorously is to use the topological lower bounds on decision problems. To exploit this set of ideas, we need to measure the size of the cut in an appropriate fashion.

measures of set complexity

What are the natural measures of the cut size? (Lebesgue measure zero? small Hausdorff volumes?) The natural candidates do not capture the essential non-triviality of the cuts.
Worse, any such measure depends on somewhat arbitrary metrics on $M$.

There is a different measure of complexity, a topological one.

Betti numbers

Just to recall, the Betti numbers measure how many "holes" of different dimensions are there.

Two connected components are separated by a 0-dimensional "hole", and the zeroth Betti number is the number of components less one.
A disk with $k$ punctures has $k$ one-dimensional holes, giving $\beta_1=k$, etc.

The formal apparatus of (co)homology theory formalizes this intuition in a simple and natural way, via the notions of cycles, boundaries, and elementary algebra (of exact sequences and diagram chasing).

The Topological Perplexity $\beta$ of a cut $C$ is the sum total of its Betti numbers modulo the boundary of its one-point compactification.

In other words, if the cut is a stratified closed subset of $M$, $$ \beta(C,\partial C):=\sum_k \beta_k(C, \partial C), $$ where $\partial C=C\cap \partial M$, and $\beta_k$ is the ranks of the $k$-th homology group $H_k(C, \partial C; \mathbb{Q})$.

One natural question to ask is on the dependence of the topological perplexity on the structure of the cut: for given data $(M,\attr)$, there might be many wildly different closed loop stabilizing controls, and many different cuts $C$.

Perhaps surprisingly, the topology of the cut set is fixed by the attractor $\attr$:



The (co)homology groups of $(C,\partial C)$ are (almost) determined by the embedding $A\hookrightarrow M$.

Warning: the topology of the cut is not determined solely by the topology of $\attr$ and of $M$: the embedding of $\attr\subset M$ is important.

If $M$ is the solid torus, and $\attr$ a circle, the cut might be empty (on the left) or nontrivial (right).

uses of topological perplexity

Topological Perplexity allows to measure the complexity of the decision problem inherent in realization of discontinuous feedback controls.

Consider a membership problem for a semialgebraic set $S\subset \Real^d$ and an algebraic decision tree solving it.

The depth of the algebraic decision trees deciding membership in a semi-algebraic pair $(C,\partial C)$ is bounded from below by \begin{equation} \Omega\left(\log \beta(C, \partial C)\right) \end{equation} (the constants depending on the degrees of the polynomials $P_j$ and on the dimension $d$).

The problem of mere detection whether or not the system is at the feedback discontinuity set can be complicated if the topology of the cut set is highly nontrivial.

example: RHex, its geometry and topology (B, Shapiro 2013)

Let us consider a couple of examples where the topological perplexity is nontrivial. We start with RHex.


RHex is a versatile robotic platform developed by Prof. Koditschek's group at UPenn's GRASP.

The configuration space of RHex is, in the first approximation, the $6$-dimensional torus, $\T^6$.
The controller attempts to stabilize the motion on a (terrain specific) gait, which is a certain periodic trajectory in $\T^6$ representing homology class $(1,1,\ldots,1)$ in $H_1(\T^6,\Int)\cong \Int^6$.

Any (set)-minimal cut for the feedback stabilization problem is homotopy equivalent to $S^1\times K_4$, where $K_4$ is the $4$-skeleton of $\T^5$.

In fact, the configuration space of RHex is a proper subset of $\T^6$: there are some positions, which are forbidden: for example, all legs on the right cannot point up simultaneously.
As a result, the actual configuration space is a $6$-dimensional manifold with boundary $M\subset \T^6$.

A $2D$ caricature of the configuration space of RHex.

The desired attractor is one of the periodic gaits, that is a smooth embedding of $S^1$ into $M\subset T^d-\Sigma$ representing a given class (the diagonal) in $1$-dimensional homology group.

The stabilization at the steady gait is impossible on all of $M$.

In this case, the homotopy type of $(C,\partial C)$ is forced to be that of $(\S^1, \mathtt{pt})$.

More generally, the configuration space of a $d$-legged robot can be naturally identified with the a subset of the $d$-dimensional torus $M=\T^d-\Sigma$, the exceptional set $\Sigma^o$ a tubular neighborhood of a coordinate toric arrangement.

a union of coordinate tori $T_I=\{\phi_{i_k}=0, i_k\in I\}$, where $I\subset \{1,2,\ldots,d\}$ is an arbitrary collection of coordinates.

(The interpretation of this toric arrangement is simple: it identifies the collections of ``legs'' which cannot be simultaneously in an upward position.)

Coordinate toric arrangements are encoded by positive Boolean polynomials $$ P=\bigwedge_\alpha x_{\alpha_1}\vee x_{\alpha_2}\vee\ldots\vee x_{\alpha_{k_\alpha}}; $$ their complements are homotopy equivalent again to the coordinate toric arrangements defined by $$ P^\bullet=\bigvee_\alpha x_{\alpha_1}\wedge x_{\alpha_2}\wedge\ldots\wedge x_{\alpha_{k_\alpha}}. $$

The cohomology ring of $M_P$ is $\bigwedge (x_1,\ldots,x_d)/I$, where the degrees of $x_i$ are $1$, and $I$ is generated by the monomials $x_{\alpha_1}\wedge x_{\alpha_2}\wedge\ldots\wedge x_{\alpha_{k_\alpha}}$

For the case of stabilization on a diagonal gait $\attr$, there exists a universal cut $\tilde{C}\supset \T^d$ which is set-theoretically minimal. That means that for the complement $M_P$ to any coordinate toric arrangement arrangement in $\T^d$, there exists a feedback stabilization of $M-C$ on $\attr$.

example: spaces of coverings (B, Chen, Wang, 2014)

Another class of configuration spaces with rich topology is given by the configurations of coverings.

Given a bounded metric space $X$, the covering space $\cov_X(n,r)$ consists of all configurations $(x_1,\ldots, x_n), x_i\in X$ such that \[ \cup_i B(x_i, r)\supset X, \] where $B(x,r)$ is a metric ball or radius $r$ around $x$.

In other words, $\cov_X(n,\epsilon)$ is the space of $\epsilon$-networks of size $n$ in $X$.

Such spaces are of obvious importance in the theory of control of robotic swarms.
Consider the simplest example: $M(r)$ is the configuration space of $n$ identical intervals (of length $r$ each) covering the unit interval.

This is the configuration space of positions of patrol cars on a highway.

Let $k$ be the minimal number of intervals needed to cover the interval.
Define the permutahedron as the convex hull of points $$ (\sigma_1,\ldots,\sigma_n)=:\sigma, $$ where $\sigma$ is a permutation of $\{1,2,\ldots,n\}$.

The manifold (with corners) $M(r)$ is homotopic to the $(n-k)$-skeleton of the permutahedron $P_n$.

In general, the spaces of coverings are complicated. We do not have a universal lower bound, but an upper bound of the topological perplexity of the spaces of coverings of a semi-algebraic domain $\domain\subset \Real^d$ by $n$ disks of radii $r=C/n$ behaves as $$ \beta=O(n! \exp(cn)), $$ with $c$ depending on the dimension $d$, domain $\domain$, scale $C$.

For the coverings of the interval, the topological perplexity is known precisely, and is similarly given by $n!$ scaled by an exponential of $n$.

An important multi-agent coordination task is a stable closed-loop feedback control stabilizing a team of agents on a periodic trajectory (contained within the space of coverings) such that each of the agents visits a point of the interval (the base) during the motion.
We call such a periodic motion a patrol.

As discussed above, any nonstalling feedback control stabilizing on an patrol will have a complicated cut, due to the mismatch between the topology of the covering space and the trajectory of a patrol.

With Chen and Wang, we created an implementation of such a feedback control stabilizing on a patrolling trajectory.

conclusion

  • We introduced new notion of topological perplexity, measuring the complexity of the set of the discontinuity of stabilizing feedback.
  • Topological perplexity bounds from below the complexity of decision problems associated with any realization of the stabilizing feedback.
  • Topological perplexity is evaluated for two classes of control systems, of independent interest.
  • Rigidity of TP with respect to cut realization was shown.

In the works: topology of cuts for non-holonomic systems









the end