Dynamic Controllability Checking for Conditional Simple Temporal Networks with Uncertainty: New Sound-and-Complete Algorithms based on Constraint Propagation

A Conditional Simple Temporal Network with Uncertainty (CSTNU) is a data structure for representing and reasoning about time. CSTNUs incorporate "observation time-points" from Conditional Simple Temporal Networks (CSTNs) and "contingent links" from Simple Temporal Networks with Uncertainty (STNUs). A CSTNU is "dynamically controllable" (DC) if there exists a strategy for executing its time-points that guarantees the satisfaction of all relevant constraints no matter how the uncertainty associated with its observation time-points and contingent links is resolved in real time. This paper presents the first sound-and-complete DC-checking algorithms for CSTNUs based on the propagation of labeled constraints and demonstrates their practicality.