Estimating Uncertainty of Autonomous Vehicle Systems with Generalized Polynomial Chaos

Keyur Joshi, Chiao Hsieh, Sayan Mitra, Sasa Misailovic

Abstract

Modern autonomous vehicle systems use complex perception and control components. These components can rapidly change during development of such systems, requiring constant re-testing. Unfortunately, high-fidelity simulations of these complex systems for evaluating vehicle safety are costly. The complexity also hinders the creation of less computationally intensive surrogate models. We present GAS, the first approach for creating surrogate models of complete (perception, control, and dynamics) autonomous vehicle systems containing complex perception and/or control components. GAS's two-stage approach first replaces complex perception components with a perception model. Then, GAS constructs a polynomial surrogate model of the complete vehicle system using Generalized Polynomial Chaos (GPC). We demonstrate the use of these surrogate models in two applications: estimating the probability of unsafe states and performing global sensitivity analysis. GAS provides an average speedup of 3.7x for safety estimation while maintaining high accuracy.

Introduction

The development of autonomous vehicles (AVs) is a highly iterative process. Changes to control algorithms or vehicle physical parameters necessitate comprehensive re-testing to ensure safety. Traditionally, this is achieved through Monte Carlo Simulation (MCS), which involves running thousands of high-fidelity simulations in environments like Gazebo or CARLA. However, these simulations are computationally prohibitive, primarily because processing high-dimensional camera data through deep neural networks (DNNs) is extremely slow.

While surrogate models—mathematical approximations of complex systems—are often used to speed up physics simulations, they typically struggle with the non-deterministic and high-dimensional nature of perception systems. There is a critical need for a method that can create a surrogate for the entire closed-loop system, encompassing perception, control, and vehicle dynamics.

The GAS Framework

The authors propose GAS (Generalized Polynomial Chaos for Autonomous Systems), a framework designed to bypass the simulation bottleneck through a two-stage process.

The GAS framework replaces the standard high-fidelity simulation pipeline (top) with a more efficient surrogate model (bottom).

1. Perception Modeling

Instead of executing a full DNN for every frame, GAS characterizes the DNN’s behavior. It samples the network’s output across a grid of ground-truth states to determine the resulting error distribution (mean and variance). By fitting a polynomial to this distribution, GAS "abstracts away" the expensive image generation and inference steps.

2. GPC Surrogate Construction

GAS utilizes Generalized Polynomial Chaos (GPC) to build a single, high-degree polynomial representing the entire system. GPC represents stochastic processes as a series of orthogonal polynomials. For systems with discrete logic (e.g., categorical aircraft maneuvers), GAS employs Multi-Element GPC and decision-tree classifiers to predict mode switches.

This compositional approach allows for rapid iteration; if the vehicle's physics change, the perception model can be reused, significantly reducing data collection time.

Key Insights and Empirical Evidence

A primary finding of this research is that image processing accounts for over 99% of simulation time in standard benchmarks. Consequently, approximating only vehicle dynamics yields negligible speedups. The real gain comes from approximating the perception system.

Distance perception error distribution for a crop-monitoring vehicle, demonstrating the Gaussian nature of DNN errors.

The authors observed that perception error in many DNNs follows a Gaussian distribution. This observation is crucial because it allows the use of Hermite polynomials within the GPC framework, ensuring high accuracy in the surrogate model.

Evaluation and Results

GAS was evaluated across five scenarios, including crop-management vehicles, lane-keeping cars, and unmanned aircraft collision avoidance systems.

  • Speedup: GAS achieved an average speedup of 3.7x for safety probability estimation (up to 8.9x) and 1.4x for global sensitivity analysis.
  • Accuracy: The probability of reaching an unsafe state calculated by GAS matched Monte Carlo ground truth for over 97% of simulated time steps.
  • Sensitivity Analysis: GAS calculated Sobol indices—identifying which input variables most affect output—with a minimal average error of 0.0004.

Conclusion and Future Work

While GAS offers significant performance improvements, it faces challenges with the "curse of dimensionality" as state variables increase. Furthermore, the perception model is tied to its training environment; shifts in lighting or terrain require re-training. Future work will focus on handling highly discontinuous control systems and improving scalability for higher-dimensional systems.

Summary updated

Abstract

Modern autonomous vehicle systems use complex perception and control components. These components can rapidly change during development of such systems, requiring constant re-testing. Unfortunately, high-fidelity simulations of these complex systems for evaluating vehicle safety are costly. The complexity also hinders the creation of less computationally intensive surrogate models. We present GAS, the first approach for creating surrogate models of complete (perception, control, and dynamics) autonomous vehicle systems containing complex perception and/or control components. GAS's two-stage approach first replaces complex perception components with a perception model. Then, GAS constructs a polynomial surrogate model of the complete vehicle system using Generalized Polynomial Chaos (GPC). We demonstrate the use of these surrogate models in two applications. First, we estimate the probability that the vehicle will enter an unsafe state over time. Second, we perform global sensitivity analysis of the vehicle system with respect to its state in a previous time step. GAS's approach also allows for reuse of the perception model when vehicle control and dynamics characteristics are altered during vehicle development, saving significant time. We consider five scenarios concerning crop management vehicles that must not crash into adjacent crops, self driving cars that must stay within their lane, and unmanned aircraft that must avoid collision. Each of the systems in these scenarios contain a complex perception or control component. Using GAS, we generate surrogate models for these systems, and evaluate the generated models in the applications described above. GAS's surrogate models provide an average speedup of $3.7\times$ for safe state probability estimation (minimum $2.1\times$) and $1.4\times$ for sensitivity analysis (minimum $1.3\times$), while still maintaining high accuracy.
BibTeX
@misc{joshi2022estimating,
  author = {Keyur Joshi and Chiao Hsieh and Sayan Mitra and Sasa Misailovic},
  title = {{Estimating Uncertainty of Autonomous Vehicle Systems with Generalized Polynomial Chaos}},
  year = {2022},
  eprint = {2208.02232},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2208.02232},
}
Figure