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: First they 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.
翻译:我们首先审查一些方法,以超近可达的线性时差系统的一组可达状态,这些方法在初始状态和输入信号的短时间范围内都不确定。这些方法对于长期范围内最先进的可达性算法至关重要,分两个步骤进行:首先,它们使用这种方法将系统分解到一个很短的时间范围内,然后有效地获得新离散系统的长期解决办法。传统上,不同可达性算法之间的定性和定量比较只考虑两个步骤的结合。在本文件中,我们孤立地研究第一步。我们对文献中的六种基本离散方法进行各种数字实验。正如我们所显示的那样,这些方法在准确性和计算成本方面有不同的权衡,根据系统的特点,有些方法可能优于其他方法。我们还讨论了改进结果和高效执行战略的预处理步骤。