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.