汎用到達可能性解析のための簡便で効率的なサンプリングベースアルゴリズム
A Simple and Efficient Sampling-based Algorithm for General Reachability Analysis
入力をサンプリングして真の到達可能集合内の像を評価し、εパディング付き凸包を集合推定器とする汎用的な到達可能性解析アルゴリズムを提案し、ランダム集合論による精度保証とニューラルネット検証・ロバストMPCへの応用を示した。
著者: Thomas Lew, Lucas Janson, Riccardo Bonalli, Marco Pavone
分類: eess.SY, cs.AI, cs.LG, cs.RO, cs.SY
原文アブストラクト
In this work, we analyze an efficient sampling-based algorithm for general-purpose reachability analysis, which remains a notoriously challenging problem with applications ranging from neural network verification to safety analysis of dynamical systems. By sampling inputs, evaluating their images in the true reachable set, and taking their $\epsilon$-padded convex hull as a set estimator, this algorithm applies to general problem settings and is simple to implement. Our main contribution is the derivation of asymptotic and finite-sample accuracy guarantees using random set theory. This analysis informs algorithmic design to obtain an $\epsilon$-close reachable set approximation with high probability, provides insights into which reachability problems are most challenging, and motivates safety-critical applications of the technique. On a neural network verification task, we show that this approach is more accurate and significantly faster than prior work. Informed by our analysis, we also design a robust model predictive controller that we demonstrate in hardware experiments.
