RI: Small: RUI: Automated Reasoning about Time -- Methods and Analysis

RI：小：RUI：关于时间的自动推理——方法与分析

• 批准号: 1909739
• 负责人: Luke Hunsberger
• 金额: $ 40.29万
• 依托单位: Vassar College
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-08-01 至 2023-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1909739&HistoricalAwards=false
• 关键词: RI; Small; RUI; Automated; Reasoning

This project will enhance the ability of computer systems to effectively (and automatically) reason about time in a broad variety of contexts. Such temporal reasoning is relevant to the automation of any business process. As an example, medical organizations must carefully manage the flow of patients through complex treatment pathways whose twists and turns typically include critically important timing constraints, tests and treatments with uncertain durations, and tests whose outcomes can dramatically affect which path to follow. This project will enable computer systems to reliably and efficiently automate the management of such complex pathways by providing algorithms that verify that all timing constraints can be satisfied no matter how the various uncertainties play out. In addition, this study seeks to improve the theoretical foundations for general-purpose workflow management systems used in business process modeling. The project engages a diverse group of undergraduate students in the new Temporal Reasoning Lab at Vassar College to generate and test new algorithms that will be stored in a public repository. The project will benefit society by making workflows more effective and reliable in a wide range of sectors. It will benefit the research community by strengthening the theoretical foundations of workflows, providing a repository for implemented algorithms and benchmark problems, and hosting an instance of the International Symposium on Temporal Representation and Reasoning. Workflows that are currently being used by businesses to automate their manufacturing or other processes currently lack a solid theoretical foundation, especially with regard to their handling of timing information. This project will focus on the use of temporal networks, a formalism for representing and reasoning about time, to solidify the theoretical foundations of workflows, and to generate new algorithms for managing the temporal constraints in workflows. Different variations of temporal networks accommodate features such as actions with uncertain durations, test actions that generate new information, constraints that depend on the results of those tests, disjunctive constraints, probabilistic constraints, and choice points. Undergraduate students working in a new Temporal Reasoning Lab will begin by implementing and empirically evaluating existing algorithms from the literature on temporal networks. Subsequent research aims to generate new algorithms for networks that include novel combinations of features that are especially relevant to workflows in the medical domain, while proving the correctness and analyzing the complexity of each new algorithm. To demonstrate the scalability of the new algorithms, the project will develop a software test-bed with a broad suite of benchmark problems to be made available to the wider research community. The resulting repository of new algorithms, theoretical analyses, benchmark problems, and empirical studies will fill an important gap in the research on temporal networks, while also enhancing the capabilities of workflows in the medical domain.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.

该项目将增强计算机系统在各种情况下有效(和自动)推理时间的能力。这种时态推理与任何业务流程的自动化都是相关的。例如，医疗机构必须谨慎地管理患者在复杂治疗路径中的流动，这些路径的曲折通常包括至关重要的时间限制、不确定持续时间的测试和治疗，以及其结果可能极大地影响选择哪条路径的测试。该项目将使计算机系统能够可靠和高效地自动化管理这种复杂的路径，方法是提供算法，验证无论各种不确定性如何发展，所有的时间约束都可以得到满足。此外，本研究旨在为通用工作流管理系统在业务流程建模中的应用奠定理论基础。该项目邀请了瓦萨学院新的时态推理实验室的一群不同的本科生来生成和测试将存储在公共存储库中的新算法。该项目将使工作流程在广泛的部门更加有效和可靠，从而造福社会。它将通过加强工作流程的理论基础，为已实施的算法和基准问题提供一个储存库，并主办关于时间表示和推理的国际专题讨论会实例，使研究界受益。目前企业用于自动化其制造或其他流程的工作流目前缺乏坚实的理论基础，特别是在处理时间信息方面。该项目将侧重于使用时态网络，这是一种表示和推理时间的形式化方法，以巩固工作流的理论基础，并生成管理工作流中的时态约束的新算法。时态网络的不同变化适应了诸如具有不确定持续时间的动作、生成新信息的测试动作、依赖于这些测试结果的约束、析取约束、概率约束和选择点等特征。在一个新的时态推理实验室工作的本科生将从实施和经验性地评估关于时态网络的文献中的现有算法开始。后续研究的目标是为网络生成新的算法，其中包括与医疗领域的工作流特别相关的特征的新组合，同时证明每个新算法的正确性并分析其复杂性。为了证明新算法的可扩展性，该项目将开发一个软件测试台，其中包含一系列基准问题，供更广泛的研究社区使用。由此产生的新算法、理论分析、基准问题和实证研究的存储库将填补时态网络研究中的一个重要空白，同时也增强了医疗领域的工作流程的能力。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Simple Temporal Networks: A Practical Foundation for Temporal Representation and Reasoning (Invited Talk)

简单时态网络：时态表示和推理的实用基础（特邀演讲）

• 发表时间: 2021
• 期刊: Leibniz international proceedings in informatics
• 作者: Hunsberger, Luke;Posenato, Roberto
• 通讯作者: Posenato, Roberto

Speeding Up the RUL¯ Dynamic-Controllability-Checking Algorithm for Simple Temporal Networks with Uncertainty

加速具有不确定性的简单时态网络的 RUL 动态可控性检查算法

• DOI: 10.1609/aaai.v36i9.21213
• 发表时间: 2022
• 期刊: Proceedings of the AAAI Conference on Artificial Intelligence
• 作者: Hunsberger, Luke;Posenato, Roberto
• 通讯作者: Posenato, Roberto

Faster Dynamic-Consistency Checking for Conditional Simple Temporal Networks

条件简单时态网络的更快动态一致性检查

• 发表时间: 2020
• 期刊: 30th International Joint Conference on Applied Planning and Scheduling (ICAPS-2020
• 作者: Hunsberger, Luke;Posenato, Roberto
• 通讯作者: Posenato, Roberto

A faster algorithm for converting simple temporal networks with uncertainty into dispatchable form

一种更快的算法，用于将具有不确定性的简单时间网络转换为可调度形式

• 发表时间: 2023
• 期刊: Information and Computation
• 影响因子: 1
• 作者: Hunsberger, Luke;Posenato, Roberto
• 通讯作者: Posenato, Roberto