Abstract
Sampled-data (SD) systems, which are composed of both discrete- and continuous-time components, are arguably one of the most common classes of cyberphysical systems in practice; most modern controllers are implemented on digital platforms while the plant dynamics that are being controlled evolve continuously in time. As with all cyberphysical systems, ensuring hard constraint satisfaction is key in the safe operation of SD systems. A powerful analytical tool for guaranteeing such constraint satisfaction is the viability kernel: the set of all initial conditions for which a safety-preserving control law (that is, a control law that satisfies all input and state constraints) exists. In this paper we present a novel sampling-based algorithm that tightly approximates the viability kernel for high-dimensional sampled-data linear time-invariant (LTI) systems. Unlike prior work in this area, our algorithm formally handles both the discrete and continuous characteristics of SD systems. We prove the correctness and convergence of our approximation technique, provide discussions on heuristic methods to optimally bias the sampling process, and demonstrate the results on a twelve-dimensional flight envelope protection problem.
Introduction
In safety-critical systems like autonomous drones or medical devices, mathematical guarantees are required to ensure the system never violates its constraints. The set of all initial states from which such safety can be maintained is known as the viability kernel. The primary challenge in computing this set for modern systems lies in their Sampled-Data (SD) nature: digital controllers act at discrete intervals while the physical plant evolves continuously. Traditional grid-based methods for finding these kernels often fail due to the "curse of dimensionality" (scaling poorly beyond 5-6 dimensions) and the "inter-sample gap," where a system might briefly enter an unsafe state between control updates.
The Sampling-Based Algorithm
To overcome these limitations, the authors propose a sampling-based polytopic approximation algorithm. Instead of gridding the entire state space, the method explores the kernel along randomly sampled rays from a known safe interior point.
The algorithm follows a structured process:
- Ray Sampling: A random direction is chosen from a starting safe point.
- Bisection Search: A bisection method is used along that ray to find the boundary of the viability kernel.
- Feasibility Check: To verify if a point is "safe," the algorithm solves a Linear Program (LP) over a finite time horizon.
- Formal Error Handling: Two critical lemmas ensure the approximation is "under-conservative" (guaranteed safe). The algorithm "erodes" the constraint set based on maximum velocity to account for inter-sample behavior and calculates formal bounds on Taylor series truncation errors to ensure simulations match physical reality.
Scalability and Performance
By utilizing randomness as a feature, the algorithm achieves a better convergence rate for the volume of convex bodies in high dimensions compared to deterministic gridding. The runtime is linear with respect to the number of samples and sub-cubic with respect to the state dimension.
The effectiveness of this approach was demonstrated on a 12-dimensional quadrotor flight envelope problem. While traditional level-set methods find such high-dimensional problems computationally intractable, this algorithm generated new boundary vertices in roughly 3 seconds and over-approximation facets in 5 seconds on standard hardware. The resulting polytopic approximation provides a much tighter fit than previous ellipsoidal techniques.
Key Insights and Future Work
The "sandwich" bound approach—computing both an under-approximation (guaranteed safe) and an over-approximation (guaranteed unsafe outside)—allows for a quantitative bound on estimation error. Furthermore, guided sampling using the von-Mises Fisher distribution can focus computational effort on high-curvature areas of the boundary to speed up convergence.
While this work focuses on Linear Time-Invariant (LTI) systems with convex constraint sets, it establishes a scalable foundation for safety verification. Future research will address non-convex constraints, truly nonlinear behavior, and the synthesis of the actual safety-preserving controllers.
Summary updated