Sampling-Based Robust Control of Autonomous Systems with Non-Gaussian Noise

Thom S. Badings, Alessandro Abate, Nils Jansen, David Parker, Hasan A. Poonawala, Mariëlle Stoelinga

Abstract

Controllers for autonomous systems that operate in safety-critical settings must account for stochastic disturbances. Such disturbances are often modelled as process noise, and common assumptions are that the underlying distributions are known and/or Gaussian. In practice, however, these assumptions may be unrealistic and can lead to poor approximations of the true noise distribution. We present a novel planning method that does not rely on any explicit representation of the noise distributions. In particular, we address the problem of computing a controller that provides probabilistic guarantees on safely reaching a target. First, we abstract the continuous system into a discrete-state model that captures noise by probabilistic transitions between states. As a key contribution, we adapt tools from the scenario approach to compute probably approximately correct (PAC) bounds on these transition probabilities, based on a finite number of samples of the noise. We capture these bounds in the transition probability intervals of a so-called interval Markov decision process (iMDP). This iMDP is robust against uncertainty in the transition probabilities, and the tightness of the probability intervals can be controlled through the number of samples. We use state-of-the-art verification techniques to provide guarantees on the iMDP, and compute a controller for which these guarantees carry over to the autonomous system. Realistic benchmarks show the practical applicability of our method, even when the iMDP has millions of states or transitions.

Introduction

In the operation of autonomous systems—such as drones navigating wind gusts or spacecraft performing docking maneuvers—uncertainty is a constant challenge. Traditionally, control engineering has relied heavily on the "Gaussian assumption," treating environmental noise as a predictable bell curve. However, real-world disturbances are often messy, non-Gaussian, or entirely unknown. If a system assumes wind gusts follow a Gaussian distribution when they actually exhibit "fat-tailed" behavior (like the Dryden gust model), safety guarantees can become dangerously unreliable.

This research addresses the reach-avoid problem: how to guarantee that a system reaches a target region within a specific timeframe while strictly avoiding unsafe zones, without requiring prior knowledge of the noise distribution.

Methodology: From Samples to Formal Guarantees

The proposed framework bridges the gap between data-driven sampling and formal verification through a three-step pipeline.

The proposed framework iteratively refines an abstract iMDP using noise samples to compute a robust optimal policy.
  1. Finite-State Abstraction: The continuous state space is partitioned into discrete, convex regions (polytopes). Transitions between these regions are modeled as actions in a discrete abstraction.
  2. Scenario Approach & PAC Bounds: Instead of estimating a single probability for transitions, the method utilizes $N$ independent noise samples. Using scenario optimization, the authors calculate Probability Intervals (lower and upper bounds). These are "Probably Approximately Correct" (PAC), ensuring with a user-defined confidence level (e.g., 99%) that the true transition probability lies within the interval.
  3. Interval Markov Decision Processes (iMDPs): These intervals are used to construct an iMDP. Unlike standard MDPs with fixed transition probabilities, iMDPs are inherently robust, seeking a policy that satisfies safety requirements for any probability within the specified intervals.

This process is iterative: if the initial safety guarantee is insufficient, the system collects more samples to shrink the intervals and re-computes the policy.

Experimental Evaluation

The method was validated on three realistic benchmarks: UAV motion planning under non-Gaussian turbulence, building temperature regulation, and spacecraft rendezvous.

A key finding is the relationship between sample size and the reliability of safety guarantees. As shown in Figure 5, while standard MDPs (using point estimates) may appear to perform well empirically, they often fail to provide valid lower-bound guarantees. In contrast, the iMDP approach provides a conservative but rigorous lower bound that converges toward the true empirical performance as the number of samples ($N$) increases.

Reachability probability vs. sample size: iMDP guarantees provide a rigorous lower bound that converges as data increases, unlike standard MDP point estimates.

In the building regulation task, the proposed method demonstrated significant computational efficiency, completing in 3–9 seconds—an order of magnitude faster than state-of-the-art formal verification tools like StocHy, which required 45 minutes. Furthermore, in high-noise scenarios like spacecraft docking, the method maintained safety guarantees where competing tools failed to find viable solutions.

Conclusion and Future Work

This approach provides a distribution-free method for robust control, remaining valid regardless of the noise's "shape" (Gaussian, uniform, etc.) as long as samples are i.i.d. By using intervals instead of point estimates, the controller accounts for the worst-case probabilities allowed by the data.

Future research will focus on adaptive discretization to refine the state-space partition where it is most critical for safety, and extending the framework to handle measurement noise alongside process noise. While currently optimized for linear systems, the theoretical foundations offer a path toward robust control for non-linear autonomous systems.

Summary updated

Abstract

Controllers for autonomous systems that operate in safety-critical settings must account for stochastic disturbances. Such disturbances are often modelled as process noise, and common assumptions are that the underlying distributions are known and/or Gaussian. In practice, however, these assumptions may be unrealistic and can lead to poor approximations of the true noise distribution. We present a novel planning method that does not rely on any explicit representation of the noise distributions. In particular, we address the problem of computing a controller that provides probabilistic guarantees on safely reaching a target. First, we abstract the continuous system into a discrete-state model that captures noise by probabilistic transitions between states. As a key contribution, we adapt tools from the scenario approach to compute probably approximately correct (PAC) bounds on these transition probabilities, based on a finite number of samples of the noise. We capture these bounds in the transition probability intervals of a so-called interval Markov decision process (iMDP). This iMDP is robust against uncertainty in the transition probabilities, and the tightness of the probability intervals can be controlled through the number of samples. We use state-of-the-art verification techniques to provide guarantees on the iMDP, and compute a controller for which these guarantees carry over to the autonomous system. Realistic benchmarks show the practical applicability of our method, even when the iMDP has millions of states or transitions.
BibTeX
@inproceedings{badings2022sampling,
  author = {Thom S. Badings and Alessandro Abate and Nils Jansen and David Parker and Hasan A. Poonawala and Mariëlle Stoelinga},
  title = {{Sampling-Based Robust Control of Autonomous Systems with Non-Gaussian Noise}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i9.21201},
}
Figure