Canonical Form of Nested Diamond Structures

A Simple Temporal Network with Uncertainty (STNU) is a data structure for representing and reasoning about time in contexts where some actions may have uncertain, but bounded durations. An STNU is dynamically controllable (DC) if there exists a strategy for executing its controllable timepoints such that no matter how the uncertain durations turn out, within their known bounds, all relevant constraints in the network will necessarily be satisfied. Several polynomial-time DC-checking algorithms have been presented in the literature. A real-time execution strategy, called RTE^*, has been defined that preserves maximum flexibility while requiring minimal real-time computation; however, that strategy only guarantees a successful execution if: (1) the network is extended to accommodate conditional wait constraints; and (2) the network satisfies an additional property called dispatchability, that is stronger than dynamic controllability. This report presents a novel theory of the dispatchability of Extended STNUs (ESTNUs) that is based on the canonical form of nested diamond structures. Each such structure entails an ordinary constraint that must be satisfied by any dispatchable ESTNU. This theory provides an avenue through which to explore more efficient algorithms for finding equivalent dispatchable networks having a minimal number of edges, which is important for limiting the computational requirements during real-time execution.