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

Introduction

In safety-critical robotics, autonomous systems must reliably solve the reach-avoid problem: reaching a target destination while strictly avoiding unsafe regions. Achieving this requires controllers to account for "process noise"—stochastic disturbances such as wind gusts, sensor inaccuracies, or environmental fluctuations.

The prevailing industry standard often assumes this noise follows a Gaussian distribution. However, real-world disturbances are frequently non-Gaussian and their exact mathematical form may be unknown. Relying on incorrect noise models can lead to fragile safety "guarantees" that fail in practice. This paper addresses a fundamental challenge: providing rigorous, distribution-free safety guarantees for systems subject to unknown environmental noise.

Methodology: From Physics to Discrete Logic

The authors propose a robust control pipeline that abstracts continuous physical dynamics into a discrete logical framework. This process ensures that safety properties can be formally verified.

The proposed control synthesis pipeline, moving from continuous dynamics to a discrete iMDP abstraction with PAC guarantees.

The pipeline consists of several key stages:

  1. State Space Partitioning: The continuous environment is divided into disjoint convex regions (polytopes).
  2. Sampling (The Scenario Approach): Instead of assuming a specific distribution, the method utilizes $N$ noise samples obtained from simulators or historical data.
  3. iMDP Construction: For each action within a region, these samples are used to calculate upper and lower bounds on transition probabilities, forming an Interval Markov Decision Process (iMDP). Unlike standard MDPs, iMDPs explicitly model uncertainty through probability ranges.
  4. PAC Guarantees: By applying a variant of the scenario approach, the authors prove that these intervals are "Probably Approximately Correct" (PAC). This ensures that with a user-defined high confidence level (e.g., 99%), the true transition probability resides within the calculated bounds.
  5. Iterative Refinement: If the initial sample size $N$ results in intervals too wide to guarantee a safe path, the algorithm automatically increases $N$ and re-abstracts the system.
  6. Verification and Synthesis: The PRISM model checker is employed to solve the iMDP, extracting a robust controller that satisfies the desired safety properties.

Evaluation and Benchmarks

The methodology was validated across three diverse control benchmarks:

  • UAV Motion Planning: A 6D state-space model of a drone navigating obstacles under Dryden gust model turbulence.
  • Building Temperature Control: A 4D model managing two rooms with radiators to maintain specific temperature ranges.
  • Spacecraft Rendezvous: A classic benchmark for satellite docking, used for comparison against existing tools like SReachTools.

Key Results and Insights

The sampling-based approach demonstrates significant advantages in safety, efficiency, and robustness.

UAV trajectory planning in a 3D environment with obstacles. The controller maintains safety under varying turbulence levels.
  • Guaranteed Safety: In the UAV benchmark, standard MDP controllers using point estimates frequently failed. In contrast, the iMDP-based controller consistently maintained safety within the theoretically guaranteed bounds.
  • Computational Efficiency: The approach proved to be orders of magnitude faster than state-of-the-art abstraction tools like StocHy (seconds vs. 45 minutes) while providing comparable or tighter safety bounds.
  • Distribution-Free Robustness: The method's power lies in its independence from noise distribution types (Gaussian, uniform, or asymmetrical). As long as the noise can be sampled, it can be bounded.
  • Scalability: The framework successfully handled iMDPs with millions of states, demonstrating its applicability to complex, high-dimensional problems.

Conclusion and Future Directions

While highly effective for linear dynamical systems, extending this framework to nonlinear systems remains a challenge due to the computational cost of reachability analysis for non-convex shapes. Future work aims to explore adaptive partitioning to focus computational resources on regions with high uncertainty and to integrate Safe Learning techniques for scenarios where both system dynamics and noise distributions are unknown.

Summary updated

Abstract

Controllers for autonomous systems that operate in safety-critical settings must account for stochastic disturbances. Such disturbances are often modeled 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