\[ \def\Real{\mathbb{R}} \def\cjs{\mathcal{C}} \def\xx{\mathbf{x}} \def\bu{\mathbf{u}} \def\zz{\mathbf{z}} \def\dipp{\mathcal{D}} \def\obs{\mathbf{O}} \def\obss{\mathcal{O}} \def\ring{\mathbf{R}} \]

HyDDRA: Hybrid Dynamics - Deconstruction and Aggregation

Yuliy Baryshnikov
Math & ECE
University of Illinois

MURI kickoff, September 15, 2023, Arlington VA

Overview of the project.

HyDDRA, Hybrid Dynamics — Deconstruction and Aggregation

Started in June 2023, combining

• University of Illinois,
• University of Pennsylvania,
• UCLA and
• CalTex.

Overarching philosophy: depart from analysis-driven paradigm; bring algebraic tools (via algebraic topology, ringed spaces, categorical tools) to the forefront.

Working within five thrusts (RCAs):

• Describing and composing hybrid systems
• Invariants of hybrid (sub)systems
• Rules of and obstacles to composition
• Compositions and Invariants
• Formal Verification and Analysis
  

This talk — how we see current lines of attack (some more detailed, some less, relegated to PIs talks).

Describing and Composing

Two approaches (intensional vs extensional):

• One using a patchwork of (open or closed) dynamical systems, with explicitly codified transition mechanisms. Compositionality often requires arcane retrofitting efforts.

• Another, taking the space of trajectories as its primitive, deriving the phase space from it. Conceptually, “Die Welt is Alles was der Fall ist”.

We will be following both threads, with more attention in this talk to the former, - as less traditional.

Hybrid Spaces as Intensional Systems

Definition (Hybrid System). A hybrid system \(H\) in the collection of objects and morphisms \[ (G \to E \to P \to M , F, R), \] where \(E\to M\) is a local covering over a stratification of \(P\) , \(G \to E\) is an inclusion morphism, and \(F:E\times \mathbb{R}\) is a locally defined semiflow such that all trajectories are either complete, or enter \(G\) Finally, \(R:G\to E\) is the reset map, a morphism preserving fibers of \(E \to M\).

We did not specify the category in which those objects and morphisms reside: one can force a more restrictive setup (o-minimality) or more permissive, — depending on the semantics of the problems at hand.

Hybrid Spaces as Extensional Systems

Alternatively, one operates directly in the space of trajectories, reformulating the questions in terms of the objects (morphisms, functors) expressible in this setting.

One can surmise that in many situation, one is not losing any information, but rather enriches the structure, enabling deployment of tools otherwise hard to incorporate into the traditional setup.

In open loop dynamics, it is often beneficial to focus on the bundles of trajectories rather than on the “differential systems” generating them. One can see this approach more explicitly when we will be talking about the topology of the spaces of trajectories, and effective safety certificates.

Hybrid Spaces as Extensional Systems

Trajectory spaces: an open loop system can be seen as collections of fragments of trajectories, the restrictions to open subintervals of the timeline \(\mathcal{T}\). The consistency of those fragments can be rendered as a condition of forming a sheaf over the timeline (or some extended version, incorporating parameters).

In general, the problem might be hopeless. However, if there is an underlying structure, it can be potentially recovered through holistically modeled finite-dimensional approximations, along the lines of George Pappas and coauthors:

NOMAD, Nonlinear Manifold Decoder for Operator Learning: generic, model-free operator learning tool.

Recovering Templates and Anchors

More model based approach is to rely on the models of the dynamics of animal or robotic complex bodies in the physical space.

One assumes that in a high-dimensional feature space, there is a low-dimensional submanifold \(M\) (posture space) and a vector field \(v\) on \(M\).

The anchor-template postulate asserts that there are several stereotyped behaviors modeled as attracting submanifolds (templates) with nontrivial basins of attraction (anchors). Their recovery is of utmost importance in data-driven understanding of the animal and robotic locomotion, and addressed by Dan Koditschek

Recovering the Topology of the Phase Space

Extensional approach, an example: CJS construction

Starting with the closed loop dynamics, reconstruction of the standard (phase space, controlled vector field) model from trajectory space can be addressed using the formalism inspired by the Cohen-Jones-Segal (’95 preprint) construction.

CJS Construction Consider a smooth manifold \(M\) equipped with a smooth Morse function \(f\) and a gradient-like vector-field \(v\).

CJS Category \(\cjs(M,f,v)\) has critical points of \(f\) as objects and the spaces of continuous paths that are (reparametrizations) of the gradient trajectories of \(v\) outside of the critical points.

Each morphism carries the structure of a topological space, and their compositions become mappings.

A careful analysis of the structure of the morphisms spaces and their adjacencies, available only under additional assumptions allows one to recover \(M\) up to homeomorphism.

A far more general result of CJS implies that the homotopy type of is that of the classifying space of the (enriched) category \(\cjs\).

The proof of the homotopy equivalence involves an auxiliary enriched category (the subdivision of \(\cjs(M,f,v)\)), whose classifying space is proven to be homotopy equivalent to \(M\).

One can take these underlying idea far beyond the original context of the gradient systems.

One of the research threads here is to port the CJS approach to more general situation, allowing one to make it effective.

The result will be a data-analytic computational pipe, taking the trajectories of an observable of a dynamical system as an input, and resulting in a principled reconstruction of the topology underlying space. Among the intended features:

• the dynamics is not necessarily gradient one;
• the underlying space is not necessarily a manifold (this dictated by the needs of the theory of templates for chaotic dynamical systems);
• allowing for piece-wise smooth vector fields

One can think of this approach as a wide generalization of Willems et al Fundamental Lemma, stating that “the behavior is all there is” in the linear case.

In preliminary experiments (with Mishal Assif) we use a version of Takens’ embedding trick (where one maps a point into space of traces of sensor signal over a prespecified window). A critical difference from the conventional approaches to utilizing Takens’ embedding, our enrichment of the category of trajectories derives from the matching fragments (think DNA sequencing).

Somewhat unexpectedly, the experiment reliably recover the structure of the attractors in chaotic systems, like Lorenz’ one.

In fact, the template theory for chaotic systems provides a highly usable heuristic parallel between hybrid and templated systems.

We intend to exploit this parallelism to full extend in both directions.

Invariants of hybrid (sub)systems

The notion of invariants deals with sketches, morphisms from a category whose objects are hard to analyze into some more amenable structures, allowing one to decompose the objects into simpler components.

Alternative set of ideas uses the notion of invariants as functors on a category, that allows one to disambiguate between different objects, sometimes gaining an insight into their internal structure.

This project will be using both sets of idea, trying to splice them as tightly as possible.

Category Theory Tools

Stability and safety properties of the dynamical systems can be formally rendered in category-theoretical terms.

Invariants (“integrals”) of dynamical systems represent morphisms into the systems with trivial dynamics.

Similarly, Lyapunov functions can be viewed as morphisms to the (asymptotically) stable Filippov dynamics on one-dimensional phase space.

Some obvious obstacles in this direction is the intrinsic weaknesses of almost any proposed notion of the category of dynamical system.

However, Aaron Ames is here to help (talk to follow)…

Topological Invariants of the Spaces of Trajectories

Guards become visible in the space of trajectories in two ways:

• jumps of the observables, and
• divergence of trajectories

First issue is relatively easy to address (in the intensional setting) by adjusting the topology on the space of trajectories (a la Skorokhod).

Second issue is material, and manifests itself in partitioning of the space of trajectories.

The the trajectories diverge sharply upon hitting a singular guard, generating the necessity of rapid switches between different operational modalities.

As more and more guards are encountered, the space of trajectories bifurcates. Quantification of this topological/combinatorial explosion is one of the prevalent themes of this project.

Dynamical Invariants of Hybrid Systems

Singularities generate intrinsic partitions of the trajectory space.

Longer observations lead to finer partitions, reflective of the (dynamic) complexity of the system.

The proliferation of the trajectories is captured by the notion of topological entropy, relevance of which to control emerged recently in the work of Nair, Evans, Liberzon, Mitra.

Intensional approach leads to research questions on topological bounds on the topological entropy, estimates for Pfaffian systems.

Extensional approach connects to rethinking of Lyapunov theory in terms of Novikov-Farber closed 1-forms and fundamental questions on the topology of the space of trajectories.

Rules of and obstacles to composition

Networks of Dynamical Systems thus far remain a subdomian without a clear global theory, despite numerous attempts.

This project will take a phenomenologically driven approach, exploring various models, rather than aiming at all-encompassing formalism.

One of the directions is the understanding the sequential compositionality across time scales (Daniel Liberzon talks about it).

Other directions include

Topological Complexity (Farber'04,...)

Minimal decomposition of the (source,target) space into domains affording an effective motion planning.

Topological Perplexity (B.'23)

Lower bounds on the homologies of the interfaces between domains where feedback stabilization is feasible.

Compositions and Invariants

Two types of invariants, — targets of functors defined on relevant categories (describes the source category), and objects in the target categories, such as reduced dynamics under Hamiltonian symmetries (describes the source objects).

The latter situation is of high practical significance. Examples where invariants are preserved and altered are analyzed by Paulo Tabuada (talk to follow) arguing that that altering them may be a better perspective for controlled (open or closed) systems.

Obstacle Avoidance is an area where compositionality plays central role.

An obstacle in itself, or some partial compositions of them might be avoidable, but their overall composition can lead to a deadlock or to a safety guarantee.

Any two of the trains can be scheduled to reach the target position (without retracing). Together, they are deadlocked.

A general theory of obstacle avoiding open control systems is within reach. It is in essence a topological theory relying ont he basic constructions, like diagrams of spaces and their (homotopy) limits.

Example: Linear Obstacles in Linear Systems (B.'23)

Consider the standard linear control system \(\dot{\xx}=A\xx+B\bu, \xx\in \Real^n, \bu\in U\in\Real^m\).

We are interested in the structure of the space \(\dipp_\obss\) of trajectories avoiding space-like linear obstacles \(\obss_\alpha, \alpha\in A\).

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

(The result reduces the question to solution of finitely many reachibility problems.)

Formal Verification and Analysis

Computing invariants of (hybrid) dynamical systems (in the extensional sense) beyond toy example and theoretical estimates is a superbly challenging problem.

Entropy estimations are more amenable to numerical bounds than topological invariants, such as homologies (or topological complexity/perplexity etc), but either would stress to the limits existing tools and approaches.

New tools will be needed!

Sayan Mitra will talk about some of these new tools, and their relevance to our project.

Looking forward

The program we presented here is intentionally unorthodox, — we believe it represents what Polanyi was calling a growing point in a field, the places where the most rapid progress can be achieved.

The focus on algebraic, topological, categorical, extensional approach will be complemented by the classical tools from analysis and algebraic and analytic geometry.

Not trying to create a unifying foundation of the hybrid dynamical systems theory, but rather trying to experiment with the descriptive tools, which affords radically different view of the research paradigm.

We do expect success, but even a failure should be interesting.

THANK YOU!