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

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

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.