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

Point Obstacles on the Plane

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

Example

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.

Thank you!