We deviate from the standard \((C,D,F,G)\) formalism of the hybrid systems, focussing instead on the paradigm \[ \hbrd\subset X\times Q, \] where \(Q\) is a space (with arbitrary topology) modeling the internal, logical structure of the system, \(X\) is the "physical" configuration space, and \(\hbrd\) is the collection of admissible pair \((x,q)\) projecting to \(X\) surjectively.

To accommodate both closed and open systems, we take as the primitive the space of trajectories

Liberzon will talk about requirements for control-enabling tasks such localization and mapping in an unknown environment. A key example, simultaneous localization and mapping (SLAM) based on a generalized discrete landmark observation can be described as recovering a trajectory \(\traj\) by observing its \(Q\)-projection.

The problem of characterizing initial configurations that cannot be distinguished based on such information, is the key, leading to an algorithm for computing indistinguishable sets.

He also addresses the problem of reconstructing possible configurations of multiple unknown landmarks (signal sources) from the total signal that they provide.

Mitra considers open hybrid control systems where the plant state is also available through \(Q\)-projection. He will discuss initial results on simultaneous algorithmic design of controllers and observers for such open hybrid systems, a variation of the simultaneous localization and mapping (SLAM) problem with discrete measurements.

He considers the notion of indistinduishable relations define the limits of solving this SLAM problem and algorithms for computing such indistinguishability relations.

Further, he looks into the notion of perception contracts as an assume-guarantee method for analyzing hybrid systems with rough measurements and discusses how they can be used to identify sufficient safe environments.

Koditschek deals with the interplay between the spaces of trajectories $\trajs$, and the stable pieces of the phase space $X$ decomposition (modeled on Conley theory). Those stable pieces, attractors, commands a central focus in the folklore and practice of applied dynamical systems theory.

He will review recent progress within a robotics research agenda that has sought to bypass the need to formalize the concept of an “open” hybrid system by recourse to behavior synthesis via parallel and sequential compositions of pre-synthesized anchored templates.

He will also address, how to frame the characterization of hybrid guardset affordance in the robotics setting.

Tabuada will describe our progress on the following controller synthesis problem: given a specification system $S$ and a plant $P$, when does there exist (and how to compute) and controller $C$ so that the composition of $C$ with $P$ is “equivalent” to $S$.

Different notions of “equivalence” and their categorical formalizations will be reviewed. In doing so, he will also establish bridges with other work being done in our team.

He will conclude with a working version of a result relating this controller synthesis problem to stabilizability of a certain sub-object of an open hybrid systems.

Moeller (working with Ames) discusses Lyapunov functions used to establish stability for dynamical systems. Their categorical framework for Lyapunov theory relies on morphisms between spaces of trajectories $\trajs$ in the original and model systems. Core to their approach is the axioms underlying a setting for stability, which give the necessary ingredients for “doing Lyapunov theory” in a category of interest.

With these minimal assumptions they define stability, formulate Lyapunov morphisms, and demonstrate that the existence of Lyapunov morphisms imply stability. This is applied to systems, framed as coalgebras, recovering the classic Lyapunov conditions for stability and asymptotic stability.

The origins of the notion of topological perplexity are in the well-known failure to construct a feedback control stabilizing on an attractor, if the homotopy types of the domain of attraction and of the attractor don't match.

In this example, there is no section of the evaluation fibrations \[ e(\traj,0)\mapsto \traj(0) \] which takes every initial point to a trajectory converging to a desired equilibrium.

While the traditional workaround relies on the fact that generic navigation functions or barrier/control Lyapunov functions have stable manifolds of measure zero (and nuisance local minima can be eliminated, by cobordism theory), the realities of engineered solutions force one to look for non-stalling solutions.

The hybrid systems paradigm provides this way out, by allowing families of paths, which are not sections, but are multi-valued over some subsets, referred to as cuts.

To quantify the mismatch between the domain of attraction and the the attractor, we introduced the notion of topological perplexity, \[ \perp_k:=\max(|\beta_k(\conf,\confb)-\beta_k(\attrn,\attrb)|,|\beta_{k+1}(\attrn,\attrb)-\beta_{k+1}(\conf,\confb)|) \] of the pair $(\conf,\attrn)$.

Then the Betti numbers of the cut set are lower-bounded by the Topological Perplexity: \[ \beta_k(\cut,\cutb)\geq \perp_k. \] In the simplest example, the mismatch of homologies happens in dimension $1$, forcing an unremovable $1$-dimensional cut.

One of the situations where the perplexity provides strong lower bounds is the multi-agent systems with volume exclusion constraints (or other interaction constraints).

In the classical situation of the configuration spaces in $\Real^d$, the Poincare polynomial for the configuration space of $n$ particles is $\prod_{k=1}^n (1+(k-1)x)$, so that the total Betti number grows superexponentially.

Another novel (application driven) generalization of the perplexity bounds deals with the time-dependent systems.

One of the approaches to overcome emergence of the nuisance equilibria is to make the elements of the control apparatus (Lyapunov or navigation functions, etc) time-dependent, say, rotated by an independently timed periodic process.

Perhaps not surprisingly, the same homological considerations predict existence of (time-dependent) cuts, singular chains preserved, set-wise, by the flow, and representing nontrivial homology classes.

These cuts represent points that stay away from the desired equilibria, no matter what continuous transformation one deploys, whether or not nuisance equilibria are present.

In the picture from Gonçalves et al, at any instant there is a line connecting the to the infinity, which is flow invariant, and is away from the attractor.

One version of the paradigm introduced above deals with the control systems in the presence of obstacles.

Consider the simplest version of a space of trajectories, defined by the linear control problems: \[ \dot{\xx}=A\xx+B\uu, \] where $\xx\in V \cong \Real^n, \uu\in U\subset\Real^m$, and $U$ is open and convex.

Assume that the obstacles are instantaneous, happening at the times $t_1\lt \ldots\lt t_k$, \[ \obs_j\in V. \]

The data: \[ \dot{\xx}=A\xx+B\uu, \xx\in V, \uu\in U; \obs_j\in V. \] We are interested in the space of paths avoiding those obstacles.

Namely, we developed a consistent approach to derive the homotopy invariants of such spaces of trajectories and quantify the impact these invariants can have on the system design.

We will be interested in the topology of the space of the trajectories 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.

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

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.

Double Integrator, Codimension 2 \[\dot{x}=v, \dot{v}=u, |u|<1.\]

Poincare polynomial is \[ \sum_k \mathbf{rk}H^m(\dipp_\obss) t^m=1+3t+2t^2. \]

The topology of the space of obstacle-avoiding trajectories has far reaching impact on the behavior of the algorithms of motion planning and optimization in robotic and natural system, especially in multi-component ones. The quantification via topological perplexity leads to lower bounds on execution metrics.

There are many variations and generalizations of the presented model. One of the more interesting generalizes to non-instantaneous obstacles (see on the right), and more general arrangements.

Perhaps the most interesting among the new results is the computation of the homologies of the spaces of paths with violation tolerance: e.g., paths which are allowed to intersect no more than $k$ obstacles.

These spaces are nontrivial already in the simplest cases, such is paths in $\Real^2$ with pointlike obstacles.

The apparatus of homotopy limits for the diagrams of spaces (coupled with finite-dimensional approximation techniques) allows one to compute the cohomologies of such spaces of paths.

Thus for the collection of obstacles on the right, with trajectories allowed to hit at most one of them, one has $\beta_0=1, \beta_1=5$.