Sampling-Based Approximation Algorithms for Reachability Analysis with Provable Guarantees
The successful deployment of many autonomous systems in part hinges on providing rigorous guarantees on their performance and safety through a formal verification method, such as reachability analysis. In this work, we present a simple-to-implement, sampling-based algorithm for reachability analysi...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
2018
|
| Online Access: | http://hdl.handle.net/1721.1/116235 https://orcid.org/0000-0002-3229-6665 https://orcid.org/0000-0002-6776-9493 https://orcid.org/0000-0002-2225-7275 https://orcid.org/0000-0001-5473-3566 |
| Summary: | The successful deployment of many autonomous systems in part hinges on providing rigorous guarantees on their performance and safety through a formal verification method, such as reachability analysis. In this work, we present a simple-to-implement, sampling-based algorithm for reachability
analysis that is provably optimal up to any desired approximation accuracy. Our method achieves computational efficiency by judiciously sampling a finite subset of the state space and generating an approximate reachable set by conducting reachability analysis on this finite set of states. We prove that the reachable set generated by our algorithm approximates the ground-truth
reachable set for any user-specified approximation accuracy. As a corollary to our main method, we introduce an asymptoticallyoptimal, anytime algorithm for reachability analysis. We present simulation results that reaffirm the theoretical properties of our algorithm and demonstrate its effectiveness in real-world inspired scenarios |
|---|