We present the first review of methods to overapproximate the set of reachable states of linear time-invariant systems subject to uncertain initial states and input signals for short time horizons. These methods are fundamental to state-of-the-art reachability algorithms for long time horizons, which proceed in two steps: they first use such a method to discretize the system for a short time horizon, and then they efficiently obtain a solution of the new discrete system for the long time horizon. Traditionally, both qualitative and quantitative comparison between different reachability algorithms has only considered the combination of both steps. In this paper we study the first step in isolation. We perform a variety of numerical experiments for six fundamental discretization methods from the literature. As we show, these methods have different trade-offs regarding accuracy and computational cost and, depending on the characteristics of the system, some methods may be preferred over others. We also discuss preprocessing steps to improve the results and efficient implementation strategies.
翻译:我们首次审查了在初始状态和输入信号不确定的情况下,对短期内线性时差系统的一套可达状态进行超近距离的一套可达状态的方法。这些方法对于长期内长期内最先进的可达性算法至关重要,分两个步骤进行:首先采用这种方法使系统在较短的时段内分解,然后有效地获得新离散系统的长期内分系统的解决办法。传统上,不同可达性算法之间的定性和定量比较只考虑两个步骤的结合。在本文件中,我们孤立地研究第一步。我们对文献中的六种基本离散方法进行各种数字实验。正如我们所显示的那样,这些方法在准确性和计算成本方面有不同的权衡,根据系统的特点,有些方法可能优于其他方法。我们还讨论了改进结果和高效执行战略的预处理步骤。