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

Hossein Sartipizadeh1, Abraham Vinod2, Behcet Acikmese3, Meeko Oishi2

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



Regular Session


10:00 - 12:00 | Wed 10 Jul | Franklin 2 | WeA02

Autonomous Systems

Full Text


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.

Additional Information

No information added


No videos found