A Better Algorithm for Converting an STNU into Minimal Dispatchable Form

A Simple Temporal Network with Uncertainty (STNU) is a data structure for representing and reasoning about temporal constraints on activities, including those with uncertain durations. An STNU is dispatchable if it can be flexibly and efficiently executed in real time while guaranteeing that all relevant constraints are satisfied. Typically, dispatchability requires inserting conditional wait constraints, thereby forming an Extended STNU (ESTNU). The number of edges in an ESTNU affects the computational work that must be done during real-time execution. The MinDispESTNU problem is that of finding an equivalent dispatchable ESTNU having a minimal number of edges. Recent work presented an O(k n³)-time algorithm for solving the MinDispESTNU problem, where n is the number of timepoints and k is the number of actions with uncertain durations. A subsequent paper presented a faster O(n³)-time algorithm, but it has been shown to be incomplete. This paper presents a new O(mn+ n² k+ n² log n)-time algorithm for solving the MinDispESTNU problem, where m is the number of constraints in the network. The correctness of the algorithm is based on a novel theory of the canonical form of nested diamond structures. An empirical evaluation demonstrates the order-of-magnitude improvement in performance.