Dynamic controllability of simple temporal networks with uncertainty: Simple rules and fast real-time execution

Simple Temporal Networks (STNs) are a well-studied model for representing temporal constraints. They comprise a set of time-points (real-valued variables representing execution times) and binary difference constraints among them. Simple Temporal Networks with Uncertainty (STNUs) extend STNs in that some time-points (called contingent) are treated as exogenous variables, whose execution times, bound to fall within a given interval from the corresponding activation time-points (as specified by a "contingent link"), get revealed only during real-time execution. An STNU is dynamically controllable (DC) if there exists a strategy to execute its time-points satisfying all the constraints, regardless of the execution times of contingent time-points revealed during execution.In this work we present a new system of constraint propagation rules for STNUs, which is sound-and-complete for DC checking. Our system comprises just three rules which, differently from the ones proposed in all previous works, only generate unconditioned constraints. In particular, after applying any of our rules, the network remains an STNU in all respects. Moreover, our completeness proof is short and non-algorithmic, based on the explicit construction of a valid execution strategy. This is a substantial simplification of the theory which underlies all the previous efficient algorithms for DC-checking.Our analysis also shows: (1) the existence of late execution strategies for STNUs, (2) the equivalence of the notion of DC among several variants of the semantics of STNUs, (3) the existence of a fast algorithm for real-time execution of STNUs, which runs in O(KN) total time in a network with K >= 1 contingent links and N >= K time points, considerably improving the previous O(N-3)-time bound. (C) 2018 Published by Elsevier B.V.