Symmetry Abstractions for Hybrid Systems and their Applications

Hussein Sibai, Sayan Mitra

Abstract

A symmetry of a dynamical system is a map that transforms one trajectory to another trajectory. We introduce a new type of abstraction for hybrid automata based on symmetries. The abstraction combines different modes in a concrete automaton A, whose trajectories are related by symmetries, into a single mode in the abstract automaton B. The abstraction sets the guard and reset of an abstract edge to be the union of the symmetry-transformed guards and resets of the concrete edges. We establish the soundness of the abstraction using a forward simulation relation (FSR) and present several examples. Our abstraction results in simpler automata, that are more amenable for formal analysis and design. We illustrate an application of this abstraction in making reachability analysis faster and enabling unbounded time safety verification. We show how a fixed point of the reachable set computation of B can be used to answer reachability queries for A, even if the latter visits an infinite and unbounded sequences of modes. We present our implementation of the abstraction construction, the fixed point check, and the map that transforms abstract reachable sets to concrete ones in a software tool. Finally, we show the advantage of our method over existing ones, and the different aspects of our abstraction, in a sequence of experiments including scenarios with linear and nonlinear agents following waypoints.

Introduction

Hybrid systems, which integrate continuous physical dynamics with discrete logic, are foundational to modern technology, from autonomous drones to medical devices. Ensuring their safety requires reachability analysis—calculating all possible states the system can enter to ensure it never enters an "unsafe" zone. However, this process faces two major challenges: state explosion, where the number of discrete modes makes computation intractable, and the difficulty of verifying safety over unbounded time horizons. This paper introduces a novel abstraction technique that exploits inherent symmetries in hybrid systems to address these hurdles.

Methodology

The core contribution is a formal framework for Symmetry Abstractions. The authors define a "virtual" hybrid automaton ($\mathcal{A}_v$) that simplifies the "concrete" system ($\mathcal{A}$).

Concrete hybrid system with waypoints and its discrete automaton representation.

As shown in Figure 1, a concrete system might involve multiple waypoints ($w_0, \dots, w_3$) and corresponding discrete modes. If these modes are related by symmetry—for instance, moving between waypoints 1 and 2 is functionally identical to moving between 2 and 3 after a translation or rotation—they are collapsed into a single virtual mode in the abstract model.

The abstraction process involves several key steps:

  • Virtual Automaton Construction: Merging symmetric operational modes into a unified virtual mode.
  • Guard and Reset Transformation: Calculating virtual "guards" (mode-switch conditions) and "resets" (state changes) by taking the union of symmetry-transformed concrete parameters.
  • Symmetry Mapping: Applying transformation maps (e.g., translation or rotation) to relate concrete trajectories to the virtual space.
Illustration of a symmetry transformation mapping a concrete trajectory to a virtual space.

Figure 3 illustrates this transformation, where a point $p^*$ is used to shift a trajectory into a common coordinate system. The authors prove that this virtual system is a "sound" over-approximation via a Forward Simulation Relation (FSR): if the virtual system is safe, the concrete system is guaranteed safe. Furthermore, because the virtual system has fewer modes, it often reaches a "fixed point," enabling safety verification for infinite time horizons.

Experimental Evaluation

The approach was evaluated using simulated agents following various paths (rectangles, S-shapes, and Koch snowflakes) with both linear and nonlinear (unicycle) dynamics. Two types of symmetry maps were tested: Translation (T) and a combination of Translation and Rotation (TR).

Key results include:

  • Significant Speedups: In S-shaped path experiments, symmetry-based abstraction was approximately 89% faster than standard methods.
  • Model Reduction: For a 16-road Koch snowflake path, TR symmetry reduced the model from 16 concrete modes to just 2 virtual modes, drastically lowering the computational burden.
  • Unbounded Verification: The method successfully verified safety for infinite paths where traditional reachability tools would fail to terminate.

Discussion and Limitations

The primary advantage of this method is its ability to turn logical redundancy into a computational asset. By treating symmetric behaviors as identical, the "discrete" complexity of the problem is reduced. However, there is a trade-off between speed and precision: more aggressive symmetries (like TR) lead to larger over-approximation errors, which might be too conservative to prove safety if the unsafe set is nearby.

Current limitations include the need for manual symmetry identification and potential non-convergence in highly unstable continuous dynamics. Future work will focus on automatic symmetry discovery and refinement techniques to improve precision when abstractions are too coarse.

Summary updated

Abstract

A symmetry of a dynamical system is a map that transforms one trajectory to another trajectory. We introduce a new type of abstraction for hybrid automata based on symmetries. The abstraction combines different modes in a concrete automaton A, whose trajectories are related by symmetries, into a single mode in the abstract automaton B. The abstraction sets the guard and reset of an abstract edge to be the union of the symmetry-transformed guards and resets of the concrete edges. We establish the soundness of the abstraction using a forward simulation relation (FSR) and present several examples. Our abstraction results in simpler automata, that are more amenable for formal analysis and design. We illustrate an application of this abstraction in making reachability analysis faster and enabling unbounded time safety verification. We show how a fixed point of the reachable set computation of B can be used to answer reachability queries for A, even if the latter visits an infinite and unbounded sequences of modes. We present our implementation of the abstraction construction, the fixed point check, and the map that transforms abstract reachable sets to concrete ones in a software tool. Finally, we show the advantage of our method over existing ones, and the different aspects of our abstraction, in a sequence of experiments including scenarios with linear and nonlinear agents following waypoints.
BibTeX
@misc{sibai2020symmetry,
  author = {Hussein Sibai and Sayan Mitra},
  title = {{Symmetry Abstractions for Hybrid Systems and their Applications}},
  year = {2020},
  eprint = {2006.09485},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2006.09485},
}
Figure