Upper and Lower Bounds for End-to-End Risks in Stochastic Robot Navigation
This provides more efficient safety verification for autonomous navigation systems, though it appears to be an incremental improvement on existing probability bounds.
The paper tackles the problem of estimating collision probability for autonomous robot motion plans with uncertain dynamics, presenting novel upper and lower bounds that are faster than Monte Carlo sampling and less conservative than existing methods.
We present novel upper and lower bounds to estimate the collision probability of motion plans for autonomous agents with discrete-time linear Gaussian dynamics. Motion plans generated by planning algorithms cannot be perfectly executed by autonomous agents in reality due to the inherent uncertainties in the real world. Estimating collision probability is crucial to characterize the safety of trajectories and plan risk optimal trajectories. Our approach is an application of standard results in probability theory including the inequalities of Hunter, Kounias, Frechet, and Dawson. Using a ground robot navigation example, we numerically demonstrate that our method is considerably faster than the naive Monte Carlo sampling method and the proposed bounds are significantly less conservative than Boole's bound commonly used in the literature.