Simpler and Faster Algorithm for Checking the Dynamic Consistency of Conditional Simple Temporal Networks
Simpler and Faster Algorithm for Checking the Dynamic Consistency of Conditional Simple Temporal Networks
Luke Hunsberger, Roberto Posenato
Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 1324-1330.
https://doi.org/10.24963/ijcai.2018/184
Recent work on Conditional Simple Temporal Networks (CSTNs) has
focused on checking the dynamic consistency (DC) property assuming
that execution strategies can react instantaneously to observations.
Three alternative semantics---IR-DC, 0-DC, and π-DC---have been presented.
The most practical DC-checking algorithm for CSTNs has only been analyzed
with respect to the IR-DC semantics, while the 0-DC semantics was shown to have a serious flaw
that the π-DC semantics fixed. Whether the IR-DC semantics had
the same flaw and, if so, what the consequences would be for the
DC-checking algorithm remained open questions.
This paper (1) shows that the IR-DC semantics is also flawed;
(2) shows that one of the constraint-propagation rules from
the IR-DC-checking algorithm is not sound with respect to the IR-DC
semantics;
(3) presents a simpler algorithm, called the π-DC-checking algorithm;
(4) proves that it is sound and complete with respect to the π-DC semantics;
and (5) empirically evaluates the new algorithm.
Keywords:
Constraints and SAT: Constraint Satisfaction
Knowledge Representation and Reasoning: Geometric, Spatial, and Temporal Reasoning
Constraints and SAT: Constraints: Evaluation and Analysis