CAREER: Reachability Analysis and Optimization of Stochastic Hybrid Systems

在广泛的实际应用中（例如，运输系统、嵌入式软件设计、便携式电子设备的节能、生物系统等），在系统的演变中存在两种固有的不确定性：由环境扰动引起的小的增量噪声，以及由随机离散事件和系统重新配置引起的突然和大的变化。这种系统的模型和分析可以方便地捕获最近发展的随机混合系统的框架。NSF CAREER研究旨在为随机混合系统中出现的两类重要问题的有效解决方案开发理论基础和计算平台：可达性问题和可达性优化问题。可达性问题是特别相关的安全关键的应用程序（如空中交通管理）：他们的解决方案将给出定量的概率特征的系统安全下存在的不确定性。这样的信息不仅可以用于监视系统的安全操作，而且还可以用作优化系统性能的总体努力中的中间结果，从而导致可达性优化问题。这两个问题的有效解决的一个关键障碍是爆炸性增加的计算复杂性与问题的维数。为了克服这一障碍，该项目正在开发分层多级计算算法。这些算法的基础上开发的软件工具，预计将使这两个问题的实时解决方案的许多实际应用具有重要的社会意义。此外，所开发的理论，算法和软件正在多机器人实验测试平台上进行验证。

In a wide range of practical applications (e.g., transportation systems, embedded software design, energy saving of portable electronics, biological systems, etc.), there are two types of uncertainty inherent in the evolution of the systems: small incremental noises caused by environmental perturbations, and abrupt and large changes caused by random discrete events and system reconfigurations. The model and analysis of such systems can be conveniently captured by the recently developed framework of stochastic hybrid systems. This NSF CAREER research aims to develop the theoretical foundation and the computational platform for the efficient solution of two important classes of problems arising in stochastic hybrid systems: their reachability problems and reachability optimization problems. The reachability problems are particularly relevant in safety-critical applications (e.g. air traffic management): their solutions will give quantitative probabilistic characterizations of the system safety under the presence of uncertainty. Such information can not only be used in monitoring the safe operation of the system, but can also serve as the intermediate results in an overall effort to optimize the system performance, resulting in reachability optimization problems. A key obstacle to the efficient solution of these two problems is the explosive increase of computational complexity with the problem dimension. Hierarchical multi-level computational algorithms are being developed in this project to overcome this obstacle. Software tools developed based on these algorithms are expected to enable the real-time solution of the two problems for many practical applications of great societal importance. In addition, the developed theory, algorithms, and software are being validated on a multi-robot experimental testbed.