Computing reachable sets of hybrid systems using a combination of zonotopes and polytopes

Matthias Althoff, Olaf Stursberg, Martin BussNonlinear 2009 · DOI

TL;DR

This paper tackles the challenge of computing reachable sets for complex hybrid systems by proposing a novel approach that combines zonotopes and polytopes. This hybrid representation allows for efficient computation of continuous dynamics while accurately handling discrete transitions, a crucial step for verifying safety in real-world systems.

What Problem Does This Paper Address?

Hybrid systems, which combine continuous dynamics (like physical processes) with discrete logic (like control decisions), are becoming increasingly complex. Ensuring the safety of these systems is paramount, but computing their "reachable sets" – all possible states a system can reach over time – is computationally challenging, especially for systems with many continuous variables. Traditional methods often struggle with either the continuous dynamics or the discrete transitions. Zonotopes offer efficiency for continuous dynamics but are problematic when intersecting with discrete transition guards. Polytopes can handle these intersections but are computationally expensive in high dimensions. This paper aims to bridge this gap by leveraging the strengths of both representations.

Methods

The core of this work lies in a hybrid approach to computing reachable sets. Here's a breakdown of the key techniques:

  • Zonotopes for Continuous Dynamics: Zonotopes are used to represent reachable sets during continuous evolution within a location. Their generator-based representation makes them computationally efficient, especially in higher dimensions.
  • Polytopes for Guard Intersections: When a hybrid system transitions between discrete states, it must pass through "guard sets." The paper uses polytopes to represent these guard sets and to conservatively over-approximate the intersection of the zonotopic reachable set with these guard sets.
  • Conversion Between Representations: A crucial aspect is the ability to convert between zonotope (generator) representation and polytope (halfspace) representation. This allows for exact intersection computations with guard sets.
  • Over-Approximation: Since exact intersections can be computationally prohibitive, the paper focuses on over-approximating the resulting sets. This means the computed reachable set might be larger than the true reachable set, but it still guarantees safety if the over-approximated set does not intersect unsafe regions.
  • Order Reduction of Zonotopes: To further improve computational efficiency, techniques for reducing the "order" of zonotopes (i.e., reducing the number of generators) are explored. This is particularly useful when dealing with complex intersections.

Datasets

Not discussed in the paper. The paper focuses on algorithmic development and evaluation using randomly generated zonotopes and a benchmark example of a room heating scenario.

Key Insights and Ideas

  • Hybrid Representation is Key: The paper demonstrates that a combination of zonotopes and polytopes is more effective than using either alone for hybrid system reachability analysis. Zonotopes handle the continuous flow efficiently, while polytopes are essential for accurate guard set intersections.
  • Conversion is the Bottleneck (and Solution): The computational cost often lies in converting between zonotope and polytope representations. The paper develops methods for these conversions and explores techniques to mitigate this cost.
  • Over-Approximation Trade-offs: The paper highlights the inherent trade-off between the accuracy of the over-approximation and the computational effort. Order reduction techniques for zonotopes are presented as a way to manage this trade-off.
  • Generator Selection Matters: The choice of generators for zonotopes significantly impacts the quality of over-approximations. The paper investigates heuristics for selecting these generators.

Key Results

The paper presents several methods for converting zonotopes to halfspace representations and for enclosing polytopes with zonotopes. Numerical results are provided in tables, comparing different methods based on their over-approximation index (a measure of accuracy) and computational time.

  • Method C (for parallelotopes) and Method D₂ (for reduced zonotopes) are highlighted as efficient and accurate for over-approximative halfspace conversion.
  • For the room heating example, the proposed method achieved a computational time of 16.3 seconds on a single-core desktop computer.
  • The paper demonstrates that the proposed techniques scale well with the dimension of the system, allowing for analysis of systems with order greater than 10 when high accuracy is not strictly required.

Limitations and Future Work

  • Order Reduction Stability: The authors note that the proposed order reduction techniques are not stable if the zonotope representation is changed. This is identified as a problem for future research.
  • Computational Cost for High Accuracy: While the methods scale well, achieving very high accuracy can still be computationally expensive, especially for high-dimensional systems.
  • Nonlinear Dynamics: The paper primarily focuses on linear continuous dynamics. Extending the methods to handle nonlinear dynamics would be a valuable future direction.
  • Uncertainty in Time: The paper acknowledges that the uncertainty in transition times can lead to an extended time horizon for reachable set computation, which could be further investigated.

Summary updated

BibTeX
@inproceedings{althoff2009computing,
  author = {Matthias Althoff and Olaf Stursberg and Martin Buss},
  title = {{Computing reachable sets of hybrid systems using a combination of zonotopes and polytopes}},
  booktitle = {Nonlinear},
  year = {2009},
  doi = {10.1016/j.nahs.2009.03.009},
}
Figure