Voronoi Partition-Based Scenario Reduction for Fast Sampling-Based Stochastic Reachability Computation of LTI Systems

Hossein Sartipizadeh1, Abraham Vinod, Behcet Acikmese2, Meeko Oishi3

  • 1University of Texas at Austin
  • 2University of Washington
  • 3University of New Mexico

Details

10:00 - 10:20 | Wed 10 Jul | Franklin 2 | WeA02.1

Session: Autonomous Systems

Abstract

We address the stochastic reach-avoid problem for linear systems with additive stochastic uncertainty. We seek to compute the maximum probability that the states remain in a safe set over a finite time horizon and reach a target set at the final time. We employ sampling-based methods and provide a lower bound on the number of scenarios required to guarantee that our estimate provides an underapproximation. Due to the probabilistic nature of the sampling-based methods, our underapproximation guarantee is probabilistic, and the proposed lower bound can be used to satisfy a prescribed probabilistic confidence level. To decrease the computational complexity, we propose a Voronoi partition-based to check the reach-avoid constraints at representative scenarios, instead of the original scenarios. The state constraints arising from the safe and target sets are tightened appropriately. We propose a systematic approach for selecting these representative scenarios and provide the flexibility to trade-off the number of cells needed for accuracy with the computational cost.