Introduction
Ensuring the safety of autonomous systems—such as unmanned aerial vehicles (UAVs) or self-driving cars—is a fundamental challenge in control theory. A common approach involves the use of Stochastic Barrier Functions (SBFs), which provide a mathematical framework to certify that the probability of a system entering an unsafe state remains below a specified threshold over a given time horizon.
However, traditional SBF synthesis typically assumes complete knowledge of the underlying noise distributions (e.g., Gaussian noise). In practice, these distributions are often unknown, and only finite data samples are available. Existing data-driven techniques, such as Sample Average Approximation (SAA), suffer from poor scalability; they require an impractical number of samples to provide high-confidence safety guarantees, especially for stringent safety requirements. This paper addresses these limitations by proposing a novel, data-efficient framework for SBF design.
Methodology
The authors focus on discrete-time piece-wise affine (PWA) systems, which are versatile enough to approximate complex non-linear dynamics by partitioning the state space into regions with distinct linear behaviors.
Inner Approximation of Stochastic Programs
The core theoretical contribution is an "inner approximation" strategy. The authors demonstrate that the non-convex stochastic optimization problem inherent in SBF synthesis can be conservatively approximated by a chance-constrained program. By introducing a tightening parameter $\nu$, they ensure that any solution to the approximated problem is a valid safety certificate for the original system.
The Scenario Approach
To handle unknown noise distributions, the framework employs the scenario approach. Instead of estimating a probability density function, this method utilizes $N$ independent and identically distributed (i.i.d.) noise samples to construct a set of deterministic constraints. If the system satisfies these constraints for all $N$ scenarios, it is guaranteed to meet the safety requirements with a high degree of confidence.
Linear Programming Reduction
For PWA systems, the authors show that the synthesis of SBFs can be reformulated as a Linear Programming (LP) problem. This is a significant departure from traditional methods that rely on computationally expensive Sum-of-Squares (SoS) optimization, allowing for much faster and more scalable safety verification.
Theoretical Advantages: Logarithmic Data Efficiency
A key insight of this work is the dramatic improvement in data efficiency. In traditional SAA methods, the number of samples required to achieve a confidence level $1-\beta$ grows linearly with $1/\beta$. In contrast, the proposed scenario-based approach exhibits logarithmic growth with respect to $1/\beta$.
As illustrated in the figure above, to achieve a high-confidence safety bound (e.g., $\beta = 10^{-9}$), SAA would require billions of samples, rendering it computationally infeasible. The proposed method achieves the same level of confidence with a fraction of the data, making it suitable for high-stakes safety applications.
Experimental Results
The framework was validated on three benchmarks: a 1D Martingale system, a 2D Drone model, and a 2D PWA Vehicle model subjected to unknown wind disturbances.
The experimental results, summarized in the table above, highlight several advantages:
- Superior Confidence: On the Drone benchmark, the proposed method achieved a confidence level of $1-10^{-9}$, whereas SAA was limited to $1-10^{-6}$ due to computational constraints.
- Computational Speed: The reduction to LP allowed the Vehicle model (with 126 PWA regions) to be solved in seconds. SAA/SoS approaches failed to handle this level of complexity.
- Certified Safety Probability: In the Vehicle example, the method certified a safety probability ($\zeta$) of 99.4%, outperforming existing state-of-the-art bounds.
Discussion and Future Work
While the proposed method offers significant improvements in efficiency and speed, it faces some limitations. The number of constraints in the LP grows with both the number of PWA regions and the number of data samples, which may pose challenges for extremely high-dimensional systems. Furthermore, the current theory assumes i.i.d. noise; future work could extend this to systems with temporally correlated noise.
The authors also suggest that the "inner approximation" theory is generalizable beyond PWA systems. Future research could explore its application to more complex function classes, such as neural network-based barrier functions, to further enhance the flexibility of data-driven safety certification.
Summary updated