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 anattractor, 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.

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.

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*.

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).

TheTopological Perplexity$\beta$ of a cut $C$ is the sum total of itsBetti numbersmodulo 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).

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.

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 auniversal cut$\tilde{C}\supset \T^d$ which is set-theoretically minimal. That means that for the complement $M_P$ toanycoordinate toric arrangement arrangement in $\T^d$, there exists a feedback stabilization of $M-C$ on $\attr$.

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.

- 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