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

Vassar College, Poughkeepsie NY

Investigators

Abstract

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.