# Case Studies for Computing Density of Reachable States for Safe Autonomous Motion Planning

arXiv: https://arxiv.org/abs/2209.08073 · HTML: https://mlsanity.com/paper/2209.08073/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 60 references that are in the map.
- First posted on arXiv 16 Sep 2022.

## Builds on (most cited first, 25 of 25)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks](https://mlsanity.com/paper/1702.01135/) (2017)
- [A Survey of Motion Planning and Control Techniques for Self-driving Urban Vehicles](https://mlsanity.com/paper/1604.07446/) (2016)
- [End-to-end Interpretable Neural Motion Planner](https://mlsanity.com/paper/2101.06679/) (2021)
- [Algorithms for Verifying Deep Neural Networks](https://mlsanity.com/paper/1903.06758/) (2019)
- [NNV: The Neural Network Verification Tool for Deep Neural Networks and Learning-Enabled Cyber-Physical Systems](https://mlsanity.com/paper/2004.05519/) (2020)
- [DeepReach: A Deep Learning Approach to High-Dimensional Reachability](https://mlsanity.com/paper/2011.02082/) (2020)
- [Verisig: verifying safety properties of hybrid systems with neural network controllers](https://mlsanity.com/paper/1811.01828/) (2018)
- [Output Reachable Set Estimation and Verification for Multi-Layer Neural Networks](https://mlsanity.com/paper/1708.03322/) (2017)
- [How Should a Robot Assess Risk? Towards an Axiomatic Theory of Risk in Robotics](https://mlsanity.com/paper/1710.11040/) (2017)
- [Reach-SDP: Reachability Analysis of Closed-Loop Systems with Neural Network Controllers via Semidefinite Programming](https://mlsanity.com/paper/2004.07876/) (2020)
- [Reachable Polyhedral Marching (RPM): A Safety Verification Algorithm for Robotic Systems with Deep Neural Network Components](https://mlsanity.com/paper/2011.11609/) (2020)
- [Efficient Bayesian Inference of Sigmoidal Gaussian Cox Processes](https://mlsanity.com/paper/1808.00831/) (2018)
- [Data-Driven Reachable Set Computation using Adaptive Gaussian Process Classification and Monte Carlo Methods](https://mlsanity.com/paper/1910.02500/) (2019)
- [Bridging the Gap Between Safety and Real-Time Performance in Receding-Horizon Trajectory Design for Mobile Robots](https://mlsanity.com/paper/1809.06746/) (2018)
- [Reachability Analysis for Feed-Forward Neural Networks using Face Lattices](https://mlsanity.com/paper/2003.01226/) (2020)
- [Sampling-based Reachability Analysis: A Random Set Theory Approach with Adversarial Sampling](https://mlsanity.com/paper/2008.10180/) (2020)
- [Learning Density Distribution of Reachable States for Autonomous Systems](https://mlsanity.com/paper/2109.06728/) (2021)
- [Efficient Reachability Analysis of Closed-Loop Systems with Neural Network Controllers](https://mlsanity.com/paper/2101.01815/) (2021)
- [Technical Report: Convex Optimization of Nonlinear Feedback Controllers via Occupation Measures](https://mlsanity.com/paper/1305.7484/) (2013)
- [PAC Model Checking of Black-Box Continuous-Time Dynamical Systems](https://mlsanity.com/paper/2007.10141/) (2020)
- [Data-Driven Set-Based Estimation using Matrix Zonotopes with Set Containment Guarantees](https://mlsanity.com/paper/2101.10784/) (2021)
- [State-Based Confidence Bounds for Data-Driven Stochastic Reachability Using Hilbert Space Embeddings](https://mlsanity.com/paper/2010.08036/) (2020)
- [Approximation of reachable sets using optimal control and support vector machines](https://mlsanity.com/paper/1412.3302/) (2014)
- [Optimal Safe Controller Synthesis: A Density Function Approach](https://mlsanity.com/paper/1909.11798/) (2019)

## Built on by (most cited first, 1 of 1)

- [The Third International Verification of Neural Networks Competition (VNN-COMP 2022): Summary and Results](https://mlsanity.com/paper/2212.10376/) (2022)

## Abstract (arXiv)

Density of the reachable states can help understand the risk of safety-critical systems, especially in situations when worst-case reachability is too conservative. Recent work provides a data-driven approach to compute the density distribution of autonomous systems' forward reachable states online. In this paper, we study the use of such approach in combination with model predictive control for verifiable safe path planning under uncertainties. We first use the learned density distribution to compute the risk of collision online. If such risk exceeds the acceptable threshold, our method will plan for a new path around the previous trajectory, with the risk of collision below the threshold. Our method is well-suited to handle systems with uncertainties and complicated dynamics as our data-driven approach does not need an analytical form of the systems' dynamics and can estimate forward state density with an arbitrary initial distribution of uncertainties. We design two challenging scenarios (autonomous driving and hovercraft control) for safe motion planning in environments with obstacles under system uncertainties. We first show that our density estimation approach can reach a similar accuracy as the Monte-Carlo-based method while using only 0.01X training samples. By leveraging the estimated risk, our algorithm achieves the highest success rate in goal reaching when enforcing the safety rate above 0.99.