Reducing Dynamic-Consistency (DC) Checking for Conditional Simple Temporal Networks (CSTNs) with Bounded Reaction Times to Standard DC Checking for CSTNs

Recent work on Conditional Simple Temporal Networks (CSTNs) has introduced the problem of checking the dynamic consistency (DC) property for the case where the reaction of an execution strategy to observations is bounded below by some fixed ε > 0. This paper shows how the ε-DC-checking problem can be easily reduced to the standard DC-checking problem for CSTNs. Given any CSTN S with k observation time-points, the paper defines a new CSTN S0 that is the same as S, except that it includes k new observation time-points. For each observation time-point P? in S that observes some proposition p, the time-point P? in S0 is demoted from an observation time-point to an ordinary time-point; and the job of observing p is taken over by a new observation time-point P0? that is constrained to occur exactly ε after P?. The paper proves that S is ε-DC if and only if S0 is DC; and shows that the application of the ε-DC- checking constraint-propagation rules to S is equivalent to the application of the corresponding DC-checking constraint-propagation rules to S0. Two versions of these results are presented, depending on whether a dynamic strategy for S0 can react instantaneously or only after some arbitrarily small, positive delay. Finally, the paper demonstrates empirically that the performance of building S0 and DC-checking it is even better than ε-DC-checking the original instance S.