Search for: All records

A Simple Temporal Network with Uncertainty (STNU) is a data structure for reasoning about time constraints on actions that may have uncertain durations. An STNU is dispatchable if it can be executed in real-time with minimal computation 1) satisfying all constraints no matter how the uncertain durations play out and 2) retaining maximum flexibility. The fastest known algorithm for converting STNUs into dispatchable form runs in O(n3) time, where n is the number of timepoints. This paper presents a faster algorithm that runs in O(mn + kn2 + n2 logn) time, where m is the number of edges and k is the number of uncertain durations. This performance is particularly meaningful in fields like Business Process Management, where sparse STNUs can represent temporal processes or plans. For sparse STNUs, our algorithm generates dispatchable forms in time O(n2 logn), a significant improvement over the O(n3)-time previous fastest algorithm. 

A Simple Temporal Network with Uncertainty (STNU) includes real-valued variables, called time-points; binary difference constraints on those time-points; and contingent links that represent actions with uncertain durations. STNUs have been used for robot control, web-service composition, and business processes. The most important property of an STNU is called dynamic controllability (DC); and algorithms for checking this property are called DC-checking algorithms. The DC-checking algorithm for STNUs with the best worst-case time-complexity is the RUL¯ algorithm due to Cairo, Hunsberger and Rizzi. Its complexity is O(mn + k²n + kn log n), where n is the number of time-points, m is the number of constraints, and k is the number of contingent links. It is expected that this worst-case complexity cannot be improved upon. However, this paper provides a new algorithm, called RUL2021, that improves its performance in practice by an order of magnitude, as demonstrated by a thorough empirical evaluation. 

Since Simple Temporal Networks (STNs) were first introduced in 1991, there have been numerous theoretic and algorithmic advances that have made them practical for a wide variety of applications. However, the presentation of most of the important advances have been scattered across numerous conference papers and journal articles. As a result, it is too easy for even experienced researchers to be unaware of results that could positively impact their work. In this talk we review the most important results about STNs for researchers in Artificial Intelligence who are interested in incorporating the management of time and temporal constraints into their projects. 

A Conditional Simple Temporal Network (CSTN) is a structure for representing and reasoning about time in domains where temporal constraints may be conditioned on outcomes of observations made in real time. A CSTN is dynamically consistent (DC) if there is a strategy for executing its timepoints such that all relevant constraints will necessarily be satisfied no matter which outcomes happen to be observed. The literature on CSTNs contains only one sound-and-complete DC-checking algorithm that has been implemented and empirically evaluated. It is a graph-based algorithm that propagates labeled constraints/edges. A second algorithm has been proposed, but not evaluated. It aims to speed up DC checking by more efficiently dealing with so-called negative q-loops. This paper presents a new two-phase approach to DC-checking for CSTNs. The first phase focuses on identifying negative q-loops and labeling key time-points within them. The second phase focuses on computing (labeled) distances from each time-point to a single sink node. The new algorithm, which is also sound and complete for DC-checking, is then empirically evaluated against both pre-existing algorithms and shown to be much faster across not only previously published benchmark problems, but also a new set of benchmark problems. The results show that, on DC instances, the new algorithm tends to be an order of magnitude faster than both existing algorithms. On all other benchmark cases, the new algorithm performs better than or equivalently to the existing algorithms.