Algorithms for Temporal Networks
Merrick Chang ’21, Furrukh Asif ’22, Sudais Moorad ’21, and Professor Luke Hunsberger (Computer Science)
The purpose of this URSI project was to help establish a (virtual) Temporal Reasoning Laboratory at Vassar College. The principal goal was to create a public repository that will include implementations of recently developed algorithms for manipulating Simple Temporal Networks (STNs) and Simple Temporal Networks with Uncertainty (STNUs). The algorithms were drawn from the recent literature on Temporal Networks. The public repository will enable researchers in the field to use the implemented algorithms to carry out reproducible empirical evaluations of the algorithms.
Temporal Networks are data structures for reasoning about temporal constraints on events in a variety of circumstances. For example, a computer agent responsible for planning a set of activities might use a Simple Temporal Network to represent the starting and ending times of those activities, as well as constraints on their durations, deadlines, and inter-activity constraints. A consistent STN is one that has a solution (i.e., a fixed schedule for doing those activities that is guaranteed to satisfy all of the constraints). Efficient algorithms are available for the computer agent to check the consistency of the STN, and for generating a variety of solutions. More complex problems involve scheduling activities in real-time (i.e., as opposed to fixing a complete schedule in advance). Algorithms for converting a consistent STN into dispatchable form ensure that real-time execution can be guaranteed to succeed with minimal computational overhead.
An STNU augments an STN to include contingent links that can be used to represent actions with uncertain duration. For example, our computer agent might control when it gets into a taxi, but not the duration of the taxi ride to the train station. Determining whether the activities in an STNU can be successfully executed in real-time is a more complex problem. However, assuming that the uncertainty is bounded by known values (e.g., the taxi ride might take between 10 and 25 minutes), efficient algorithms can check whether an STNU is dynamically controllable. Such algorithms allow an agent to use a dynamic strategy for deciding when to start actions, meaning that the agent’s decisions can react to observations of the durations of contingent links.