论文标题
具有两级晶格神经网络控制器的LTI系统的多项式达到可达性
Polynomial-Time Reachability for LTI Systems with Two-Level Lattice Neural Network Controllers
论文作者
论文摘要
在本文中，我们考虑了由整流的线性单元（RELU）两级晶格（TLL）神经网络（NN）控制器控制的线性时间流动（LTI）系统的可触时集合的计算复杂性。特别是，我们表明，对于这样的系统和控制器，可以在多项式时间内以TLL NN控制器的大小（神经元数）计算确切的一步可达到的设置。此外，我们表明，可触及集合的紧密边界可以通过两种多项式时间方法进行计算：一个在TLL的大小中具有多项式复杂性，另一个具有多项式复杂性，在控制器和其他问题参数的Lipschitz常数中具有多项式复杂性。最后，我们提出了一种务实的算法，该算法将（半）确切可及性和近似可达性的好处（我们称为L-tllbox）结合在一起。我们通过与最先进的NN控制器可及性工具进行经验比较来评估L-Tllbox。在我们的实验中，L-Tllbox在同一网络/系统上的该工具快5000倍，同时生产到区域的0.08至1.42倍的范围。
In this paper, we consider the computational complexity of bounding the reachable set of a Linear Time-Invariant (LTI) system controlled by a Rectified Linear Unit (ReLU) Two-Level Lattice (TLL) Neural Network (NN) controller. In particular, we show that for such a system and controller, it is possible to compute the exact one-step reachable set in polynomial time in the size of the TLL NN controller (number of neurons). Additionally, we show that a tight bounding box of the reachable set is computable via two polynomial-time methods: one with polynomial complexity in the size of the TLL and the other with polynomial complexity in the Lipschitz constant of the controller and other problem parameters. Finally, we propose a pragmatic algorithm that adaptively combines the benefits of (semi-)exact reachability and approximate reachability, which we call L-TLLBox. We evaluate L-TLLBox with an empirical comparison to a state-of-the-art NN controller reachability tool. In our experiments, L-TLLBox completed reachability analysis as much as 5000x faster than this tool on the same network/system, while producing reach boxes that were from 0.08 to 1.42 times the area.
