Object of study homotopy type of the space of trajectories of a control system avoiding certain obstacles.

Why bother?

Such spaces often arise in the problems of motion planning or optimal control - that is the problems of finding a trajectory of an engineered system avoiding forbidden regions of the configuration space, and/or satisfying some optimality requirements, - and are common in robotics, control of autonomous systems, and many other areas, too numerous to list here.

Origins: Concurrency Problem

The original motivation for this research comes, however, from a special applied setting known in theoretical computer science under the moniker of the **spaces of directed paths**.

There is a significant literature dealing with the topology of such spaces motivated by the **concurrency problem**.

Consider joint execution of several algorithms (or processes) progressing asynchronously. The instantaneous state of the system is a vector $(x_1(t),\ldots, x_d(t))$ of states of each of the processes, which we can assume as taking values in the unit interval. The directed nature of the process implies that each $x_l$ is non-decreasing in time.

*Generalizing*:

In the picture above, the constraints are Cartesian products.

What happens if we consider more general obstacles?

The directed paths in the concurrency problem can be interpreted as the trajectories in $\Real^d$ whose velocities lie in the positive coordinate orthant $K=\Real_+^d$.

What happens if one replaces the hodograph $K=\Real_+^d$ by some other convex cone, perhaps not even of full dimension $d$?

Consider a linear control system, \[ \dot{\bx}=A\bx+B\bu, \bx(0)=\bx_* \] where $\bx\in V=\Real^d, \bu\in P$, $P$ a convex open subset of $U=\Real^m$.

As usual, one needs to introduce some analytic constraints on the control, so that the solutions make sense.

The space $\dipp$ of trajectories $\{\bx(t)\}, t\in I=[0,T]$ obtained this way is, obviously, convex.

Controllability of the system \[ \dot{\bx}=A\bx+B\bu, \bx(0)=\bx_* \] means that the trajectories are not contained in a proper linear subspace of $\Real^d$.

It also implies genericity:

**Proposition**

Consider a trajectory $\bx$ of the linear system, and an open subset $A\subset[0,T]$ of the time interval where the system is defined, and the space of trajectories $\dipp_{U,\bx}$ matching $\bx$ outside of $U$. If the system is controllable, then for any finite subset $\{t_1,\ldots,t_l\}\subset A$, the evaluation map on $\dipp_{U,\bx}$ given by
\[
e:\bx\mapsto (\bx(t_1),\ldots,\bx(t_k))
\]
is a submersion.

Here we deal primarily with the *instantaneous* obstacles:

Consider a sequence of instantaneous obstacles $\obs_k\subset V, k=1,\ldots,K$ realized at times
\(0\lt t_1\lt t_2\lt \ldots\lt t_k\lt\ldots\lt t_K\lt T\).

In this talk we will deal only with the obstacles that are affine subspaces of $V$.

We will denote these data as $\obss=\{(\obs_k,t_k)\}_k$.

We will be interested in the trajectories of the system *avoiding the obstacles*:
\[
\dipp_\obss=\{(\bx(\cdot): \bx(t_k)\notin \obs_k \mbox{ for } k=1,\ldots, K\}.
\]

One can see easily that if the obstacles are closed subsets of $V$, then the collection of obstacle avoiding trajectories (identified with, say, the collection of the initial conditions and controls $\{\bx_*,\bu(\cdot)\}\subset V\times L_1([0,T],P)$ realizing obstacle avoiding paths) forms an open subset in the space of trajectories.

Our primary goal is to understand the topology of the space $\dipp_\obss$.

Consider the simplest possible example (the * simple integrator*):
\[
\dot{x}=u, x,u\in\Real^1, x(0)=x_*, |u|\lt 1.
\]
Consider a finite collection of $0$-dimensional obstacles, - just a sequence of $K$ points on the $(t,x)$ plane ordered left-to-right:
\[
\obss=\{(t_1,x_1), (t_2,x_2), \ldots, (t_K,x_K)\}, 0\lt t_1\lt \ldots\lt t_K.
\]

**Theorem**

The space of obstacle avoiding trajectories in this system is a disjoint union of finitely many contractible components, which are in one-to-one correspondence with the * chains* of the ordering described above starting with $(0,x_*)$.

The space $V$ from which an $l$-dimensional affine linear subspace $\obs$ is removed is homotopy equivalent to the $c=d-l-1$-dimensional sphere $S^c$.

In particular, its $c$-dimensional cohomology group (reminder: all (co)-homology groups here are assumed over $\Int$) is cyclic, and generated by the class Poincare-dual to any properly cooriented $(l+1)$-dimensional affine half-plane in $V$ having $\obs$ as its boundary.

We will be referring to this class as the *avoidance class* $a(\obs)\in H^c(V-\obs)$.

Back to linear systems \[ \dot{\bx}=A\bx+B\bu, \bx(0)=\bx_* \]

An (ordered) sequence of obstacles
\[0\lt \obs_{k_1}\lt \obs_{k_2}\lt \ldots\lt \obs_{k_L}\]
forms a *chain* if there exists a trajectory of the linear system
starting at at $x_*$ and* passing* through all of the obstacles in the chain, for some admissible control $u(\cdot)$ in $P$.

**Lemma**
The collections of trajectories passing through a chain of obstacles $\chain$ is a convex subset of the space of trajectories.

**Example**

Consider the *double integrator* system,
\[
\dot{x}=v, \dot{v}=u; |u|\lt A
\]
and a collection of the codimension $2$ obstacles $\obs_k=(x_k, v_k; t_k)$. Then the following holds:

**Proposition**

The obstacles form a chain if for any pair of adjacent indices \(k\lt k\) in the sequence $0\lt k_1\lt k_2\lt \ldots$, forms a chain, which leads to the natural compatibility condition: $\obs_k, \obs_{k}$ is a chain if and only if the region in $(t,x)$ plane given by
\[
\begin{array}{c}
t_k\lt t\lt t_{k+1}\\
x_{k}+v_{k}(t-t_{k})-A(t-t_{k})^2/2\lt x\lt x_{k}+v_{k}(t-t_{k})+A(t-t_{k})^2/2\\
x_{k'}+v_{k'}(t-t_{k'})-A(t-t_{k'})^2/2\lt x\lt x_{k'}+v_{k'}(t-t_{k'})+A(t-t_{k'})^2/2\\
\end{array}
\]
is path-connected.

In this example, the conditions on the obstacle to form a chain are easy to check (are semialgebraic), - not the case in general.

Consider the graded ring $\ring_\obs$ generated by elements \(\bo_k\) of degree \(c_k\) (one generator for each obstacle; the degree equals the dimension of the corresponding avoidance class) and subject to the relations \[ \begin{array}{l} \bo_k^2=0 \mbox{ unless } c_k=0, \mbox{ in which case } \bo_k^2=\bo_k;\\ \bo_{k_1} \cdots \bo_{k_L}=0 \mbox{ unless the sequence of obstacles } \{\obs_{k_l}\}, k_1\lt \ldots\lt k_L \mbox{ forms a chain.} \end{array} \]

**Theorem**

The cohomology ring $H^*(\dipp_\obss)$ is isomorphic to $\ring_\obs$ under the homomorphism sending each $\bo_k$ to the corresponding avoidance class.

In the planar example, all obstacle classes are of dimension $0$, and we are in the *Heavyside functions ring* situation.

To each chain of obstacles $\chain$ one can associate a manifold $\gamma(\chain)$ in $\dipp_\obs$ homeomorphic to the product of spheres \[ \gamma(\chain)\cong\prod_{\obs_k\in\chain}S^{c_k-1}, \] where $c_k$ is the codimension of $\obs_k$ in $V$, by deforming a trajectory of the linear systems, hitting the obstacles $\obs_k$ which are part of the chain $\chain$, but avoiding all other obstacles, applying the submersion Lemma.

One can prove independence of the resulting classes $\gamma(\chain)$ by pairing them with the obstacle classes: \[ (\alpha_\chain,\gamma_{\chain'})=\delta_{\chain,\chain'}. \]

The results above imply that \[ \ring_\obs\to H^*(\dipp_\obss) \] is injective.

Surjectivity follows from a finite-dimensional approximation and Alexander duality.

**Proposition**

The evaluation map, mapping a trajectory $\bx$ to its values at $t_1,\ldots, t_K$ is a homotopy equivalence on $\dipp_\obss$.

This implies that one can focus on the pair $\ball(\obss)\subset \ball$, where $\ball$ is the (open convex) image of the space of trajectories under the evaluation map, and $\ball(\obss)$ is the space of all trajectories hitting an obstacle.

The big picture: the pair $\ball(\obss)\subset \ball$ is an intersection of a linear subspace arrangement and an open convex ball.

Compactifying, we can focus on the space $K\ball(\obss)$, and, via Alexander duality, on $\cup_{\obs\in\obss}K(\obs) \subset K\ball\cong S^D$.

Consider as the poset the collection $\chains$ of chains of obstacles $\chain$, ordered by reverse inclusion (i.e. $\chain\succ \chain'$ iff the latter is a subset of the former).

To construct the topological spaces associated to the chain we take the intersection \[ K(\obs_\chain):=\cup_{\obs\in\chain}K(\obs). \] The mappings $d_{\chain\chain'}:K(\obs_{\chain'})\to K(\obs_\chain)$ are just the inclusions. We will denote the resulting diagram of spaces as $K\obs$.

**Lemma**

The pair $(K\ball(\obs),K)$ is homotopy equivalent to $\Vert K\obs\Vert$.

**Lemma**

The homotopy limit $\Vert K\obs\Vert$ is homotopy equivalent to the wedge
\[
(K\cup \ball(\obs_\chain),K)\sim \left({\bigvee}_{\chain\in\chains} \Vert \chains_{\lt \chain}\Vert*S^{d(\chain)},\bullet\right)
\]
where $\Vert \chains_{\lt \chain}\Vert$ is the nerve of the poset $\chains_{\lt \chain}$ of ordered by inclusion proper sub-chains of $\chain$, and $d(\chain)$ is the dimension of $\ball(\obs_\chain)$.

**Proposition**

The spaces $\Vert \chains_{\lt \chain}\Vert$ are homeomorphic to $S^{|\chain|-2}$: here $|\chain|$ is the length of the chain $\chain$ (by convention, $S^{-1}=\emptyset$).

In other words, the ranks of the homogeneous components of $\ring_\obss$ matches those of $H^*(\dipp(\obss))$.

One can consider the space of trajectories avoiding some collections of obstacles: for example, one can allow trajectory to hit no more than $k$ obstacles.

The techniques of the diagrams of spaces port to this setting verbatim, but the combinatorics becomes more interesting.

Another interesting generalization deals with the obstacles that are non-instantaneous. The techniques of the diagrams of spaces would still apply, but necessitate some modifications.