Dynamic-Consistency Checking for Conditional Simple Temporal Networks: Strengthening the Theoretical Foundations and Presenting a Faster Algorithm

Recent work on Conditional Simple Temporal Networks (CSTNs) has focused on checking the dynamic consistency (DC) property for the case where an execution strategy can react instantaneously to observations. Three alternative semantics for such strategies—IR-dynamic, 0-dynamic, and π-dynamic—have been presented. However, the most practical DC-checking algorithm has only been analyzed with respect to the IR semantics. Meanwhile, 0-dynamic strategies were shown to permit a kind of circular dependence among simultaneous observations, making them impossible to implement, whereas π-dynamic strategies prohibit this kind of circularity. Whether IR-dynamic strategies allow this kind of circularity and, if so, what the consequences would be for the above-mentioned DC-checking algorithm remained open questions. This paper makes the following contributions: (1) it shows that IR-dynamic strategies do allow circular dependence and, thus, that the IR semantics does not properly capture instantaneous reactivity; (2) it shows that one of the constraint-propagation rules from the IR-DC-checking algorithm is unsound with respect to the IR semantics; (3) it presents a simpler DC-checking algorithm, called the π-DC-checking algorithm, that uses half of the rules from the earlier algorithm, and that it proves is sound and complete with respect to the π-DC semantics; (4) it empirically evaluates the new algorithm. Thus, the paper places practical DC checking for CSTNs in the case of instantaneous reaction on a solid theoretical foundation.