We propose a novel Branch-and-Bound method for reachability analysis of neural networks in both open-loop and closed-loop settings. Our idea is to first compute accurate bounds on the Lipschitz constant of the neural network in certain directions of interest offline using a convex program. We then use these bounds to obtain an instantaneous but conservative polyhedral approximation of the reachable set using Lipschitz continuity arguments. To reduce conservatism, we incorporate our bounding algorithm within a branching strategy to decrease the over-approximation error within an arbitrary accuracy. We then extend our method to reachability analysis of control systems with neural network controllers. Finally, to capture the shape of the reachable sets as accurately as possible, we use sample trajectories to inform the directions of the reachable set over-approximations using Principal Component Analysis (PCA). We evaluate the performance of the proposed method in several open-loop and closed-loop settings.
翻译:Translated abstract:
本文提出了一种新颖的分支定界方法,用于神经网络在开环和闭环设置下的可达性分析。我们的想法是首先使用凸程序在某些感兴趣的方向上离线计算神经网络的Lipschitz常数的精确界限。然后,我们使用这些界限来使用Lipschitz连续性论据获得可达集的瞬时但保守的多面体逼近。为了减少保守性,我们将我们的边界算法纳入一个分支策略中,以在任意精度下减少超逼近误差。然后,我们将我们的方法扩展到具有神经网络控制器的控制系统的可达性分析中。最后,为了尽可能准确地捕捉可达集的形状,我们使用样本轨迹使用主成分分析(PCA)来通知可达集超逼近的方向。我们在多个开环和闭环设置中评估所提出方法的性能。