Abstract
We define a special class of hybrid automata, called Deterministic and Transversal Linear Hybrid Automata (DTLHA), whose continuous dynamics in each location are linear time-invariant (LTI) with a constant input, and for which every discrete transition up to a given bounded time is deterministic and, importantly, transversal. For such a DTLHA starting from an initial state, we show that it is possible to compute an approximation of the reach set of a DTLHA over a finite time interval that is arbitrarily close to the exact reach set, called a bounded epsilon-reach set, through sampling and polyhedral over-approximation of sampled states. We propose an algorithm and an attendant architecture for the overall bounded epsilon-reach set computation process.
Introduction
Hybrid systems, which integrate continuous physical dynamics with discrete logic, are fundamental to modeling complex autonomous systems like self-driving cars or industrial robots. A primary challenge in ensuring the safety of these systems is reachability analysis: determining the set of all states a system can reach from a given initial condition. For most general hybrid systems, computing the exact reach set is mathematically undecidable. While existing tools provide over-approximations, they often lack guarantees regarding termination or the precision of the approximation, particularly when discrete transitions (jumps) occur.
Methodology
This work introduces Deterministic and Transversal Linear Hybrid Automata (DTLHA) to address these challenges. The core innovation lies in the requirement of transversality during discrete transitions.
Transversality and Determinism
In a DTLHA, when a continuous trajectory encounters a guard (a boundary triggering a discrete jump), it must do so transversally. This means the trajectory crosses the boundary at a non-zero angle rather than skimming along it. This property is crucial because it ensures that the "exit time" from a continuous state is numerically detectable and prevents Zeno behavior—a phenomenon where a system undergoes infinite jumps in finite time.
Sampling and Polyhedral Wrapping
The proposed algorithm computes the reach set by sampling the state at discrete time intervals $h$ and wrapping these points in polyhedral neighborhoods.
- Error-Driven Sampling: The sampling period $h$ is derived based on a user-defined maximum error $\epsilon$. This ensures that the Hausdorff distance between the computed approximation and the true reach set is bounded by $\epsilon$.
- Numerical Robustness: The method explicitly accounts for finite-precision floating-point arithmetic errors, ensuring that the theoretical guarantees hold in practical computer implementations.
Experimental Evaluation
The algorithm was evaluated using a synthetic 2D Linear Hybrid Automaton benchmark consisting of four locations (UP, DOWN, LEFT, RIGHT) with distinct linear dynamics. The system was designed to loop through these states, testing the algorithm's ability to handle multiple discrete transitions.
In simulations, the algorithm successfully computed a bounded $\epsilon$-reach set with $\epsilon = 0.5$ over a 20-second window. Despite the system undergoing 10 discrete transitions, the accumulated numerical calculation error remained exceptionally low ($2.56 \times 10^{-11}$), demonstrating the robustness of the approach.
Conclusion
By assuming transversality, this research transforms a potentially undecidable reachability problem into a decidable one with provable error bounds. While currently restricted to DTLHAs, the framework provides a rigorous foundation for reachability analysis. Future work will focus on extending these guarantees to non-deterministic systems and optimizing polyhedral operations to mitigate the computational costs associated with higher-dimensional state spaces.
Summary updated