Sampling-based Reachability Analysis: A Random Set Theory Approach with Adversarial Sampling

Understand

Reachability analysis is at the core of many applications, from neural network verification, to safe trajectory planning of uncertain systems.

• However, this problem is notoriously challenging, and current approaches tend to be either too restrictive, too slow, too conservative, or approximate and therefore lack guarantees.
• In this paper, we propose a simple yet effective sampling-based approach to perform reachability analysis for arbitrary dynamical systems.
• Our key novel idea consists of using random set theory to give a rigorous interpretation of our method, and prove that it returns sets which are guaranteed to converge to the convex hull of the true reachable sets.