CAREER: Establishing correctness of learning-enabled autonomous systems with conflicting requirements

该奖项全部或部分由《2021年美国救援计划法案》（公法117-2）资助。由于其安全关键性质，自主系统受到多种监管要求的约束。一般来说，保证在所有条件下满足所有要求是不可行的。在这种情况下，系统需要决定如何优先处理它们。有两个主要因素使这一决定复杂化。首先，相互冲突的需求之间的优先次序可能没有完全确定。其次，决策需要在系统中基于学习的组件和环境的非结构化、不可预测和非合作性质所产生的不确定性下做出。因此，建立自治系统的正确性需要规范语言来捕捉需求的不平等重要性，量化每个需求的违反，并包含系统面临的不确定性。拟议的努力针对理论基础和计算工具的主要差距，以实现在自治系统的整个开发过程中正式方法的实际应用，包括基于学习的组件，在不确定的环境中运行，并且受到部分确定优先级的冲突需求的影响。它的关键新颖性在于(1)概率规则手册的发展，这是一种新的规范形式，它捕获了不确定性和违反需求程度之间的权衡，并利用这种违反风险以及需求之间部分建立的优先级来建立系统轨迹之间的一致顺序；(2)基于概率规则手册最小化总违规风险的最小违规控制综合算法，并允许以可证明的正确方式纳入基于学习的功能；(3)定量验证框架，利用基于学习的组件和环境以及概率规则手册的统计分析来提供系统的定量分析。这种发展将成为建立自治制度保障的关键步骤。该项目将在一个小型自治平台上验证在提议的努力下开发的理论结果和算法，该平台也将用于教育目的。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

This award is funded in whole or in part under the American Rescue Plan Act of 2021 (Public Law 117-2). Autonomous systems are subject to multiple regulatory requirements due to their safety-critical nature. In general, it is infeasible to guarantee the satisfaction of all requirements under all conditions. In such situations, the system needs to decide how to prioritize among them. Two main factors complicate this decision. First, the priorities among the conflicting requirements may not be fully established. Second, the decision needs to be made under uncertainties arising from both the learning-based components within the system and the unstructured, unpredictable, and non-cooperating nature of the environments. Therefore, establishing the correctness of autonomous systems requires specification languages that capture the unequal importance of the requirements, quantify the violation of each requirement, and incorporate uncertainties faced by the systems.The proposed effort targets a major gap in theoretical foundations and computational tools to enable practical applications of formal methods throughout the development process of autonomous systems that include learning-based components, operate in uncertain environments, and are subject to conflicting requirements with partially established priorities. Its key novelty lies in the development of (1) probabilistic rulebooks, a new specification formalism that captures the tradeoffs between the uncertainty and the degree of violation of the requirements and utilizes such violation risk together with partially established priorities among the requirements to establish a consistent order among the trajectories of the system, (2) minimum-violation control synthesis algorithms that minimize the total violation risk based on the probabilistic rulebooks and allow learning-based functionality to be incorporated in a provably correct manner, and (3) quantitative verification frameworks that utilize statistical analysis of the learning-based components and the environment as well as the probabilistic rulebooks to provide quantitative analysis of the system. Such development will serve as a critical step towards establishing assurance of autonomous systems. This project will validate the theoretical results and algorithms developed under the proposed effort on a small autonomy platform that will also be utilized for educational purposes.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.