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

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

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.