Temporal Networks to DC Checking
Luke Hunsberger
Department of Computer Science, Vassar College, NY, USA hunsberger@vassar.edu
Roberto Posenato
Department of Computer Science, University of Verona, Verona, Italy roberto.posenato@univr.it
https://orcid.org/0000-0003-0944-0419
Abstract
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 time of an execution strategy to observations is bounded below by some fixed > 0, the so-called -DC-checking problem. This paper proves that the -DC--DC-checking problem for CSTNs can be reduced to the standard DC-checking problem for CSTNs – without incurring any computational cost. Given any CSTN S with k observation time-points, the paper defines a new CSTN S0 that is
the same as S, except that for each observation time-point P ? in S: (i) P ? is demoted to a non-observation time-point in S0; and (ii) a new observation time-point P0?, constrained to occur
exactly units after P ?, is inserted into S0. The paper proves that S is -DC if and only if S0is
(standard) DC, and that the application of the -DC-checking constraint-propagation rules to S is equivalent to the application of the corresponding (standard) DC-checking constraint-propagation rules to S0. Two versions of these results are presented that differ only in whether a dynamic
strategy for S0 can react instantaneously to observations, or only after some arbitrarily small,
positive delay. Finally, the paper demonstrates empirically that building S0 and DC-checking it
incurs no computational cost as the sizes of the instances increase.
2012 ACM Subject Classification Computing methodologies → Temporal reasoning, Theory of computation → Network optimization, Theory of computation → Dynamic graph algorithms, Mathematics of computing → Graph algorithms
Keywords and phrases Conditional Simple Temporal Networks, Dynamic Consistency, Temporal Constraints
Digital Object Identifier 10.4230/LIPIcs.TIME.2018.15
1
Overview
A Conditional Simple Temporal Network (CSTN) is a data structure for reasoning about time in domains where some constraints may apply only in certain scenarios. For example, a patient who tests positive for a certain disease may need to receive care more urgently than someone who tests negative. In different research fields CSTNs have been used to model temporal reasoning tasks, for example, in planning [18, 21] and automating business processes [8, 15, 17].
Conditions in a CSTN are represented by propositional letters whose truth values are not controlled, but instead are observed in real time. Just as doing a blood test generates a positive or negative result that is only learned in real time, the execution of an observation time-point P ? in a CSTN generates a truth value for its corresponding propositional letter p.
© Luke Hunsberger and Roberto Posenato; licensed under Creative Commons License CC-BY
An execution strategy for a CSTN specifies when the time-points will be executed, but cannot affect which truth values are generated by observations. However, a strategy can be dynamic in that its decisions can react to information from past observations. A CSTN is said to be dynamically consistent (DC) if it admits a dynamic strategy that guarantees the satisfaction of all relevant constraints no matter which outcomes are observed during execution.
Different varieties of the DC property have been defined that differ in how reactive a dynamic strategy can be. Originally, Tsamardinos et al. [20] stipulated that a dynamic strategy could react to an observation only after some positive delay, but that the delay could be arbitrarily small. Comin et al. [9] defined -DC, which assumes that a strategy’s reaction time is bounded below by some fixed > 0. Finally, Cairo et al. [2] defined π-DC, which allows a strategy to react instantaneously (i.e., after zero delay).
Several approaches to DC-checking algorithms have been presented in the literature to address the different flavors of DC [20, 4, 5, 9]. However, the only approach that has been demonstrated to be practical is the one based on the propagation of labeled constraints due to Hunsberger et al. [14, 11]. Different versions of their algorithm have been used to solve the (standard) DC-checking, -DC-checking, and π-DC-checking problems.
This paper makes the following contributions. First, it proves that the -DC-checking problem for CSTNs can be reduced to the standard DC-checking problem. The proof involves transforming the original CSTN instance S into a related CSTN, S0, and then showing that
S is -DC if and only if S0is (standard) DC. Second, the paper proves 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. Third, it empirically
compares the performance of (1) building S0and DC-checking it versus (2) -DC-checking the
original instance S. On a suite of benchmark instances from the business application domain, the results demonstrate that building S0 and DC-checking it incurs no computational cost as
the sizes of the instances increase.
In this way, the global contribution of the paper is to show that the -DC-checking problem is not a new problem (as has been suggested in recent papers), but is in fact reducible to the standard DC-checking problem. The empirical evaluation simply confirms that the -DC-checking algorithm and the algorithm based on transforming to a standard DC problem have comparable performances.
2
Background
Dechter et al. [10] introduced Simple Temporal Networks (STNs) to facilitate reasoning about time. An STN comprises real-valued variables, called time-points, and binary difference constraints on those variables. Typically, an STN includes a special time-point, Z, whose value is fixed at zero. A consistent STN is one that has a solution as a constraint satisfaction problem.
Tsamardinos et al. [20] introduced CSTNs, which augment STNs to include observation time-points (OTPs) and their associated propositional letters. In a CSTN, the execution of an OTP P ? generates a truth value for its associated propositional letter p. In addition, each time-point can be labeled by a conjunction of propositional literals specifying the scenarios in which that time-point must be executed. And since constraints among labeled time-points may similarly be applicable only in certain scenarios, later work generalized CSTNs to also include labels on constraints [13].
P ? 0 = Z Q? Y W V U 0 h−10, p¬qi h−10 , pq i h−10, pi h3 , p i h−7, ¬pi h12 , ¬ pi h− 10 , ¬ pi h5 , ¬pi h−7, pi Figure 1 A sample CSTN.
Building on prior observations by Tsamardinos et al. [20], Hunsberger et al. [13, 6, 7] formalized properties that must be satisfied by the labels in a well-defined CSTN. But then Cairo et al. [3] showed that for any well-defined CSTN, no loss of generality results from subsequently removing the labels from its time-points, the result being a so-called streamlined CSTN. Therefore, to simplify our presentation and results, without any loss of generality, the rest of this paper restricts attention to streamlined CSTNs (i.e., CSTNs whose constraints can have propositional labels, but whose time-points cannot).
Fig. 1 shows a sample CSTN in its graphical form, where the nodes represent time-points, and the directed edges represent binary difference constraints. In the figure, Z is fixed at 0; and P ? and Q? are OTPs whose execution generates truth values for p and q, respectively. The edge from U to Q? being labeled by p¬q indicates that it applies only in scenarios where p is > and q is ⊥. The dashed edges with shaded labels are generated by the DC-checking algorithm by Hunsberger et al. [14], to be discussed later on.
2.1
(Streamlined) CSTNs
The following definitions are from Hunsberger et al. [14], except that propositional labels appear only on constraints. Henceforth, the term CSTN shall refer to streamlined CSTNs.
IDefinition 1 (Labels). Given a set P of propositional letters: a label is a (possibly empty) conjunction of (positive or negative) literals from P. The empty label is notated ; for any label `, and any p ∈ P, if ` |= p or ` |= ¬p, then we say that p appears in `; for any labels `1
and `2, if `1|= `2, then `1is said to entail `2; if `1∧ `2 is satisfiable, then `1and `2 are called consistent; and P∗denotes the set of all consistent labels whose literals are drawn from P.
I Definition 2 (CSTN). A Conditional Simple Temporal Network (CSTN) is a tuple, hT , P, C, OT , Oi, where:
T is a finite set of real-valued time-points (i.e., variables); P is a finite set of propositional letters (or propositions);
C is a set of labeled constraints, each having the form, (Y − X ≤ δ, `), where X, Y ∈ T , δ ∈ R, and ` ∈ P∗;
OT ⊆ T is a set of observation time-points (OTPs); and
O : P → OT is a bijection that associates a unique OTP to each propositional letter. In a CSTN graph, the OTP for p (i.e., O(p)) is typically denoted by P ?; and each labeled constraint, (Y − X ≤ δ, `), is represented by an arrow from X to Y annotated by the labeled value, hδ, `i: Xhδ, `iY . Since any time-points X and Y may participate in multiple constraints of the form, (Y − X ≤ δi, `i), the edge from X to Y may have multiple labeled values of the
form, hδi, `ii.
IDefinition 3 (Scenario). A function, s : P → {>, ⊥}, that assigns a truth value to each
p ∈ P is called a scenario. For any label ` ∈ P∗, the truth value of ` determined by s is denoted by s(`). I denotes the set of all scenarios over P.
IDefinition 4 (Schedule). A schedule for a set of time-points T is a mapping, ψ : T → R. The set of all schedules over T is denoted by Ψ.
The projection of a CSTN onto a scenario, s, is the STN obtained by restricting attention to the constraints whose labels are true under s (i.e., that must be satisfied in that scenario).
IDefinition 5 (Projection). Let S = hT , P, C, OT , Oi be any CSTN, and s any scenario over P. The projection of S onto s – notated S(s) – is the STN, (T , C+
s), where:
C+
s = {(Y − X ≤ δ) | ∃`, (Y − X ≤ δ, `) ∈ C and s(`) = >}
IDefinition 6 (Execution Strategy). An execution strategy for a CSTN S = hT , P, C, OT , Oi is a mapping, σ : I → Ψ, from scenarios to schedules. The execution time for the time-point X in the schedule σ(s) is denoted by [σ(s)]X. An execution strategy σ for a CSTN S is viable if for each scenario s, the schedule σ(s) is a solution to the projection S(s) (i.e., σ is guaranteed to satisfy all of the relevant constraints).
3
CSTN Reduction
This paper presents two related sets of results. Each set of results involves reducing a form of -DC checking to a form of standard DC checking (one of which involves instantaneous reaction). In each case, a given CSTN S is transformed (or reduced) to a related CSTN S0 such that the form of -DC checking for S is equivalent to the corresponding form of
standard DC checking for S0. Although there are two different versions of this result, the
translation from S to S0 is the same.
IDefinition 7 (Reduction CSTN, S0). Let S be any CSTN, and let > 0 be arbitrary. The reduction of S is the CSTN S0that is the same as S except that for each OTP P ? in S, and
its associated propositional letter p:
P ? is demoted from an OTP in S to an ordinary time-point in S0;1
S0 contains a new OTP P0? that is associated with the letter p in S0; and
the constraint, (P0? = P ? + , ), is contained in S0.2
More formally, S0= hT ∪ OT0, P, C ∪ C0, OT0, O0i, where:
OT0 = {P0? | P ? ∈ OT };
O0(p) = P0? ⇔ O(p) = P ?;
C0 = {(P0? = P ? + , ) | P0? ∈ OT0}.
Fig. 2 shows the reduction S0 that corresponds to the CSTN S from Fig. 1. Note that in
any given instance, the value of will be fixed and known (e.g., = 3).
3.1
Computational Complexity
Let > 0 be arbitrary, and let S be any CSTN with k OTPs. The reduction of S to S0
involves O(k) elementary operations for:
1. demoting original OTPs to non-OTPs;
1 Although the demoted time-point is not an OTP in S
0, it shall still be notated as P ? because keeping
its name the same will simplify subsequent definitions and proofs.
2 The constraint, P
P ? P0? 0 = Z Q? Q0? Y W V U − − 0 h−10, p¬qi h−10 , pq i h−10, pi h3 , p i h−7, ¬pi h12 , ¬ pi h− 10 , ¬ pi h5 , ¬pi h−7, pi
Figure 2 The reduction S0corresponding to S from Fig. 1.
2. adding k new OTPs; and
3. inserting a pair of constraints between each demoted time-point P ? and the corresponding new OTP P0?.
Therefore, the overall computational complexity for the reduction is O(k).
4
Dynamic Strategies/Dynamic Consistency
The truth values of propositions in a CSTN are not known in advance, but a dynamic execution strategy can react to observations in real time. This paper addresses the following four flavors of dynamic strategy that differ in how reactive the strategy can be, ordered from most reactive to least reactive.
Type Reaction Time, ρ
π-dynamic ρ ≥ 0
dynamic ρ > 0
-dynamic ρ ≥ > 0
ˆ
-dynamic ρ > > 0
A π-dynamic strategy can react instantaneously to observations, but must specify an order of dependence among simultaneous observations [2]. The reaction times for a (standard) dynamic strategy can be arbitrarily small, but must be positive [20]. The reaction times for an -dynamic strategy must be greater than or equal to some fixed > 0 [9]. The reaction times for an ˆ-dynamic strategy must be greater than some fixed > 0. Since a CSTN is DC if and only if it has a viable and dynamic execution strategy, each distinct version of dynamic strategy gives rise to a distinct version of dynamic consistency: DC, π-DC, -DC, and ˆ-DC, respectively.
The paper will show that the ˆ-DC-checking problem can be reduced to (standard) DC checking; and that the -DC-checking problem can be reduced to π-DC checking. These reductions can be used to simplify the automated management of DC checking for CSTNs.
5
Reducing ˆ
-DC Checking to (Standard) DC Checking
The following sections recall the relevant definitions for DC and ˆ-DC, and show that S is ˆ
5.1
Dynamic Strategies and (Standard) DC
(Standard) dynamic strategies were first defined by Tsamardinos et al. [20]. To facilitate comparisons with later definitions, the following are in the form given by Hunsberger et al. [14].
To begin, a history at time t comprises the truth values of all propositions that were observed before time t.
IDefinition 8 (History). Let S = hT , P, C, OT , Oi be any CSTN, s any scenario, σ any execution strategy for S, and t any real number. The history of t in the scenario s, for the strategy σ – notated Hist(t, s, σ) – is the set of observations made before time t according to the schedule σ(s):
Hist(t, s, σ) = {(p, s(p)) | P ? ∈ OT and [σ(s)]P ?< t}
IDefinition 9 (Dynamic Strategy). An execution strategy σ for a CSTN S is called dynamic if for any scenarios s1and s2, and any time-point X:
let: t = [σ(s1)]X
if: Hist(t, s1, σ) = Hist(t, s2, σ)
then: [σ(s2)]X= t.
In other words, if a dynamic strategy σ executes X at time t in scenario s1, and the schedules σ(s1) and σ(s2) have the same history of past observations, then σ must also execute X
at time t in s2. That is, execution decisions can only depend on past observations, even if
arbitrarily recent.
IDefinition 10 (Dynamic Consistency (DC)). A CSTN is dynamically consistent (DC) if there exists an execution strategy for it that is both viable and dynamic.
5.2
ˆ
-Dynamic Strategies and ˆ
-DC
The ˆ-dynamic consistency property has not been presented before in the literature. However, it differs only slightly from -DC, defined later on. Informally, an ˆ-dynamic strategy must schedule a time-point X at the same time t in two different scenarios s1 and s2 if both
scenarios have the same history of past observations before time t − (i.e., units before the current time t).
IDefinition 11 (ˆ-History). Let S = hT , P, C, OT , Oi be any CSTN, s any scenario, σ any execution strategy for S, t any real number, and > 0. The ˆ-history of t in the scenario s, for the strategy σ, notated ˆHist(t, s, σ), is the set of observations made before time t − according to σ(s):
ˆ
Hist(t, s, σ) = {(p, s(p)) | P ? ∈ OT and [σ(s)]P ?< t−}
I Definition 12 (ˆ-Dynamic Execution Strategy ). Let > 0; and let S be any CSTN. An execution strategy σ for S is called ˆ-dynamic if for any scenarios s1 and s2, and any
time-point X:
let: t = [σ(s1)]X
if: ˆHist(t, s1, σ) = ˆHist(t, s2, σ)
IDefinition 13 (ˆ-DC). For any > 0, a CSTN S is ˆ-dynamically consistent if it has a viable and ˆ-dynamic execution strategy.
The following theorem explicates the relation between ˆ-DC and DC.
I Theorem 14. Let S = hT , P, C, OT , Oi be any CSTN; let > 0 be arbitrary; and let S0= hT ∪ OT0, P, C ∪ C0, OT0, O0i be the reduction of S. Then S is ˆ-DC if and only if S0 is DC.
Proof. (⇒) Suppose that S is ˆ-DC. Then there exists an ˆ-dynamic and viable strategy σ for S. Define a strategy σ0 for the reduction S0, as follows. For any scenario s:
(1) For each X ∈ T : let [σ0(s)]X = [σ(s)]X
(1) For each P0? ∈ OT0: let [σ0(s)]P0?= [σ(s)]P ?+
Since σ is viable for S, σ satisfies all of the constraints in C. And since, by (1) above, σ and σ0 agree on all of the time-points in T , σ0must also satisfy all of the constraints in C.
Finally, by (2) above, σ0 must satisfy all of the constraints in C0. Therefore, σ0 must be
viable for S0.
Next, suppose that σ0is not dynamic. Then for some scenarios s1and s2, and some
time-point X ∈ T ∪ T0, Hist(t, s1, σ0) = Hist(t, s2, σ0), but [σ0(s2)]X 6= t, where t = [σ0(s1)]X.
With no loss of generality, assume that t is minimal for this circumstance. Then: ˆ Hist(t, s2, σ) = {(p, s2(p)) | P ? ∈ OT and [σ(s2)]P ?< t − } = {(p, s2(p)) | P0? ∈ OT0and [σ0(s2)]P0?< t}, by (2) above = Hist(t, s2, σ0) = Hist(t, s1, σ0) = {(p, s1(p)) | P0? ∈ OT0and [σ0(s1)]P0?< t} = {(p, s1(p)) | P ? ∈ OT and [σ(s1)]P ?< t − }, by (2) above = ˆHist(t, s1, σ). (†)
Now, if X ∈ T , then [σ(s1)]X = [σ0(s1)]X = t, but [σ(s2)]X = [σ0(s2)]X 6= t, which,
given that the relevant ˆ-histories are equal, contradicts that σ is ˆ-dynamic. Therefore, X 6∈ T ; thus, X must be some R0? ∈ OT0, where [σ(s1)]R? = [σ0(s1)]R0?− = t − 6=
[σ0(s2)]R0?− = [σ(s2)]R?. Thus, the schedules σ(s1) and σ(s2) are different. Consider those
schedules, each annotated with the relevant observations as they occur. Let t∗≤ t − be the earliest time at which the annotated schedules differ. There are two ways they can differ at t∗.
Case 1. Both schedules execute some OTP Q? at t∗, but with different results (i.e., s1(q) 6= s2(q)). If t∗< t − , it would contradict that ˆHist(t, s1, σ) = ˆHist(t, s2, σ). Therefore, t∗= t − .
Now, the definition of t∗ ensures that ˆHist(t∗, s1, σ) = ˆHist(t∗, s2, σ). But then
[σ(s1)]R?6= [σ(s2)]R?, shown earlier, contradicts that σ is ˆ-dynamic.
Case 2. One of the schedules executes some time-point Y at t∗ while the other schedule executes Y at some later time: [σ(si)]Y = t∗< [σ(sj)]Y, where {si, sj} = {s1, s2}. But
this, together with ˆHist(t∗, s
1, σ) = ˆHist(t∗, s2, σ), contradicts that σ is ˆ-dynamic.
(⇐) Suppose that S0 is DC. Then there exists a viable and dynamic strategy σ0 for S0.
Let σ be the strategy for S such that for each scenario s, and each time-point X ∈ T , [σ(s)]X= [σ0(s)]X. Since σ0is viable for S0, it satisfies all of the constraints in C ∪ C0. And
since σ and σ0 agree on all time-points in T , it follows that σ satisfies all of the constraints
in C. Thus, σ is viable for S.
Next, suppose that σ is not ˆ-dynamic. Then for some scenarios s1and s2, and some
time-point X ∈ T , ˆHist(t, s1, σ) = ˆHist(t, s2, σ), where t = [σ(s1)]X, but [σ(s2)]X 6= t. Arguing
similarly to (†) above, it follows that Hist(t, s1, σ0) = Hist(t, s2, σ0). And since X ∈ T ,
[σ0(s1)]X= [σ(s1)]X= t 6= [σ(s2)]X = [σ0(s2)]X, contradicting that σ0is dynamic. J
6
Reducing -DC Checking to π-DC Checking
This section uses the same reduction of S to S0 to reduce the problem of -DC checking to
that of π-DC checking.
6.1
-Dynamic Execution Strategy and -DC
The semantics for -DC is the same as that for ˆ-DC, except that an -history records the observations at or before time t − , instead of strictly before t − . Nonetheless, for easy reference, the full definitions are given below.
IDefinition 15 (-History). Let S = hT , P, C, OT , Oi be any CSTN, s any scenario, σ any execution strategy for S, t any real number, and > 0. The -history of t in the scenario s, for the strategy σ, notated Hist(t, s, σ), is the set of observations made at or before t − according to σ(s):
Hist(t, s, σ) = {(p, s(p)) | P ? ∈ OT and [σ(s)]P ?≤ t − }
IDefinition 16 (-Dynamic Execution Strategy). Let > 0. An execution strategy σ is
-dynamic if for any scenarios s1 and s2, and any time-point X:
let: t = [σ(s1)]X
if: Hist(t, s1, σ) = Hist(t, s2, σ)
then: [σ(s2)]X= t.
IDefinition 17 (-DC). Given any > 0, a CSTN is -dynamically consistent (-DC) if there exists an execution strategy for it that is both viable and -dynamic.
6.2
π-Dynamic Execution Strategy and π-DC
This section summarizes the π-DC semantics introduced by Cairo et al. [2] that allows a dynamic strategy to react instantaneously to observations, but requires an order of dependence among simultaneous observations.
IDefinition 18 (Order of dependence). For any ordering (P1?, . . . , Pk?) of observation
time-points, where k = |OT |, an order of dependence is a permutation π over (1, 2, . . . , k); and for each P ? ∈ OT , π(P ?) ∈ {1, 2, ..., k} denotes the integer position of P ? in that order. For any non-observation time-point X, we set π(X) = ∞ . Finally, Πk denotes the set of all
permutations over (1, 2, . . . , k).
IDefinition 19 (π-Execution Strategy). For any CSTN S = hT , P, C, OT , Oi, where k = |OT |, a π-execution strategy for S is a mapping, σ : I → (Ψ × Πk), such that for each
scenario s, σ(s) is a pair (ψ, π) where ψ : T →R is a schedule and π ∈ Πk is an order of
any P ? ∈ OT , [σ(s)]πP ? denotes the position of P ? in the order of dependence (i.e., π(P ?)). Finally, a π-dynamic strategy must be coherent: for any scenario s, and any P ?, Q? ∈ OT , [σ(s)]P ?< [σ(s)]Q? implies [σ(s)]πP ?< [σ(s)]
π
Q? (i.e., if σ(s) schedules P ? before Q?, then it orders P ? before Q?).
IDefinition 20 (Viability). The π-execution strategy σ = (ψ, π) is called viable for the CSTN S if for each scenario s, the schedule ψ(s) is a solution to the projection S(s).
I Definition 21 (History). Let S = hT , P, C, OT , Oi be any CSTN. Let σ be any π-execution strategy for S, s any scenario, t any real number, and d ∈ {1, 2, . . . , |OT |} ∪ {∞} any integer position (or infinity). The π-history of (t, d) for the scenario s and strategy σ – denoted by πHist(t, d, s, σ) – is the set
{(p, s(p)) | P ? ∈ OT , [σ(s)]P ?≤ t, and π(P ?) < d}.
Thus, the π-history specifies the truth values of each proposition p that is observed before time t in the schedule ψ, or observed at time t if its corresponding observation time-point P ? is ordered before position d by the permutation π.
The following definition of a π-dynamic strategy is equivalent to that given by Cairo et al. [2]. (The straightforward proof has been omitted to save space.)
IDefinition 22 (π-Dynamic Strategy). A π-execution strategy, σ, for a CSTN is π-dynamic if for every pair of scenarios, s1 and s2, and every time-point X ∈ T :
let: t = [σ(s1)]X, and d = [σ(s1)]πX. if: πHist(t, d, s1, σ) = πHist(t, d, s2, σ) then: [σ(s2)]X= t and [σ(s2)]πX= d.
Thus, if σ executes X at time t and position d in scenario s1, and the histories, πHist(t, d, s1, σ)
and πHist(t, d, s2, σ), are the same, then σ must also execute X at time t and in position d
in scenario s2. (X may be an observation time-point.)
IDefinition 23 (π-Dynamic Consistency). A CSTN, S, is π-dynamically consistent (π-DC) if there exists a π-execution strategy for S that is both viable and π-dynamic.
Theorem 24 explicates the relationship between the -DC and π-DC properties. Its proof, which uses techniques similar to those used to prove Theorem 14, extended to accommodate the order of dependence, is omitted to save space.
I Theorem 24. Let S = hT , P, C, OT , Oi be any CSTN; let > 0 be arbitrary; and let S0= hT0, P, C0, OT0, O0i be the reduction of S. Then S is -DC if and only if S0 is π-DC.
7
The π-DC- and -DC-Checking Algorithms
This section summarizes two versions of the constraint-propagation algorithm due to Huns-berger et al. [14][12]: the π-DC-checking algorithm and the -DC-checking algorithm. Each algorithm uses only three constraint-propagation rules.3 This section proves that applying
the rules for the -DC-checking algorithm to the CSTN S is equivalent to applying the rules for the π-DC-checking algorithm to the corresponding reduced CSTN S0.
3 An earlier version of the π-DC-checking algorithm, called the IR-DC-checking algorithm (IR for
“instantaneous reaction”) used six rules, but recently, Hunsberger and Posenato [12] showed that three rules are sufficient. We applied similar techniques to create a three-rule version of the -DC-checking algorithm.
Table 1 Propagation rules for the π-DC-checking algorithm (above) and instances of their use
(below).
LP: X hu, αi Y hv, βi Z hu + v, αβi if αβ ∈ P∗and u + v < 0 qR0: P ? Z hw, α ˜pi hw, αi if w < 0, ˜p ∈ {p, ¬p, ?p}, and α ∈ Q ∗ qR∗3: P ? Z Y hw, αi hv, β ˜pi hm, α ? βi if w < 0, ˜p ∈ {p, ¬p, ?p}, and α, β ∈ Q ∗ X, Y ∈ T ; P ? ∈ OT ; Z = 0. In qR0/qR∗
3, p does not appear in α or β; and m = max{v, w}.
LP: X h−3, pqri Y h−4, rs¬ti Z
h−7, pqrs¬ti
qR0: P ? h−9, (?p)qrih−9, qri Z
qR∗3: A? h−1, b¬ci Z h−1, b(?c)ih−1, aci B?
7.1
The π-DC-Checking Algorithm
Table 1 lists the three constraint propagation rules used by the π-DC-checking algorithm. Note that the qR∗3rule can generate a new kind of propositional label, called a q-label (defined
below); and the qR0 and qR∗3rules can each be applied to q-labeled edges. Each q-label is a conjunction of q-literals (defined below). Whereas a constraint labeled by p must hold in all scenarios in which p is true, a constraint labeled by the q-literal ?p need only hold as long as the truth value of p is unknown (i.e., as long as P ? has not been executed).
IDefinition 25 (Q-literals, q-labels). A q-literal is a literal of the form ?p, where p ∈ P. A
q-label is a conjunction of literals and/or q-literals. Q∗ denotes the set of all q-labels. For any scenario s, and any q-literal ?p, it is convenient to stipulate that s 6|= ?p.
For example, p(?q)¬r and (?p)(?q)(?r) are both q-labels.
The ? operator extends ordinary conjunction to accommodate q-labels. Intuitively, if the constraint C1is labeled by p, and C2is labeled by ¬p, then both C1 and C2 must hold as
long as the value of p is unknown, represented by p ? ¬p = ?p.
IDefinition 26 (?). The operator, ? : Q∗× Q∗→ Q?, is defined thusly. First, for any p ∈ P, p ? p = p and ¬p ? ¬p = ¬p; and for any p1, p2∈ {p, ¬p, ?p}, such that p16= p2, p1? p2= ?p.
Next, for any `1, `2∈ Q∗, `1? `2∈ Q∗ denotes the conjunction obtained by applying ? in
pairwise fashion to matching literals from `1 and `2, and conjoining any unmatched literals.
For example: (p¬q(?r)t) ? (qr¬s) = p(?q)(?r)¬st.
7.2
The -DC-checking Algorithm
The -DC-checking algorithm uses the same rules as the π-DC-checking algorithm, except that in the qR∗3 rule, it uses m = max{v, w − }. For clarity, we shall refer to this version of the qR∗3rule as qR3; and {LP, qR0, qR3} shall be called the -DC-checking rules.
ITheorem 27. Let > 0; let S be any CSTN; and let S∗ be the CSTN that results from exhaustively applying the -DC-checking constraint-propagation rules to S. Let S0 be the corresponding reduced CSTN for S; and let S0∗ be the CSTN that results from exhaustively applying the π-DC-checking rules to S0. Then S∗ and S0∗ are equivalent in the following sense:
(a) X hu, βi W hv, γi Y LP: hu + v, βγi (b) P ? qRhδ, α ˜pi Z 0: hδ, αi (c) P0? P ? Z − hδ, α ˜pi LP: hδ − , α ˜pi qR0: hδ − , αi (d) P ? P0? Z hδ − , αi LP: hδ, αi (e) P ? hw, βi Z qR hv, γ ˜pi Y 3: hmax{v, w − }, β ? γi (f) P0? P ? Z Y − hw, βi LP: hw − , βi hv, γ ˜pi qR∗3: hmax{v, w − }, β ? γi (g) X Y P0?
hu, βi hv, γi
LP: hu + v, β ? γi
(h) X hu, βi Y hv − , γi P ?
LP: hu + v − , β ? γi (i) P0? Z hδ, α ˜pi qR0: hδ, αi (j) P ? qRhδ + , α ˜pi Z 0: hδ + , αi (k) Q0? Z P0? hu, βi hv, γ ˜qi qR∗3: hδ, αi (l) Q? hu + , βi Z qRhv + , γ ˜ qi P ? 3: hδ + , αi (m) Q0? W P0?
hu, βi hv, γi
LP: hδ, αi
(n) Q? hu + , βi W hv − , γi P ? LP: hu + v, β ? γi
Figure 3 Constraint propagations for the proof of Theorem 27.
(1) Every constraint in S∗ is also in S0∗.
(2) For each P0?, Q0? ∈ OT0, X ∈ T \OT0, δ ∈R, and α ∈ Q∗:
(a) (P0?−X ≤ δ, α) ∈ S0∗ ⇒ (P ? − X ≤ δ − , α) ∈ S∗
(b) (X −P0? ≤ δ, α) ∈ S0∗ ⇒ (X − P ? ≤ δ + , α) ∈ S∗
(c) (P0?−Q0? ≤ δ, α) ∈ S0∗ ⇒ (P ? − Q? ≤ δ, α) ∈ S∗
Proof. (Part 1) Let Σ be some arbitrary sequence of applications of ˆ-DC-checking rules to edges from S∗. Let (Y − X ≤ δ, α) in S∗ be the first edge generated by that sequence that does not belong to S0∗. Call that constraint C. (Note that X and Y must be in T since C is in S∗.)
Case 1.1: The constraint C was generated by applying the LP rule to edges in S∗ (e.g., as shown in Fig. 3a, where δ = u + v and α = βγ). But then, by assumption, the pre-existing edges (from X to W to Y ) must also be in S0∗. Since the LP rule is also one of the DC-checking rules, the generated edge (from X to Y ) must also be in S0∗. But that edge represents the constraint C, a contradiction.
Case 1.2: The constraint C was generated by the qR0 rule (e.g., as shown in Fig. 3b). But
then the pre-existing edge from P ? to Z must be in S0∗; and so is the edge from P0?
to P ?, as shown in Fig. 3c. Applying the LP rule to these edges, followed by the qR0 rule, then yields the shaded labeled values for the edge from P0? to Z in S0∗, as shown
in Fig. 3c. Next, applying the LP rule to the edges from P ? to P0? to Z, as shown in
Fig. 3d, generates the edge from P ? to Z for S0∗. But that edge represents the constraint C, a contradiction.
Case 1.3: The constraint C was generated by the qR3rule (e.g., as shown in Fig. 3e, where m = max{v, w − } and α = β ? γ). But then the pre-existing edges (from P0? to P ? to
Z) must be in S0∗, which allows the LP rule to generate the edge from P0? to Z in S0∗,
shown in Fig. 3f, and then the qR∗3 rule to generate the shaded value for the edge from Y to Z in S0∗, which represents the constraint C, a contradiction.
(Part 2) Let Σ0be some arbitrary sequence of recursive applications of DC-checking rules to
edges from S0∗. Let K in S0∗ be the first edge generated by that sequence that does not have a corresponding edge in S∗ according to (2a), (2b) and (2c) in the statement of the theorem.
Case 2a: K has the form (P0? − X ≤ δ, α). Given that P0? 6≡ Z, K can only have been
generated by an application of the LP rule to edges in S0∗, as shown in Fig. 3g, where δ = u + v and α = β ? γ. By assumption, the pre-existing edge from Y to P0? in S0∗ must
have a corresponding edge from Y to P ? in S∗. For example, if Y ∈ T , then by (2a) there must be an edge from Y to P ? as shown in Fig. 3h. That edge enables the LP rule to then be used to generate the edge from X to P ? in S∗, also shown in Fig. 3h. But that is the edge in S∗ that corresponds to K, a contradiction. The case where Y is some Q0? ∈ OT0 is even easier.
Case 2b.1: K has the form (X − P0? ≤ δ, α) and was generated by applying the LP rule to
edges in S0∗. This case is similar to Case 2a, but focusing on the lefthand side of the LP rule (i.e., the edge from X to Y ) instead of the right.
Case 2b.2: K has the form (Z − P0? ≤ δ, α) and was generated by applying the qR0rule to
edges in S0∗, as shown in Fig. 3i. But then, by (2b), the pre-existing edge from P0? to
Z has a corresponding edge in S∗ from P ? to Z, leading to the propagation in Fig. 3j, which generates the edge in S∗ that corresponds to K, a contradiction.
Case 2b.3: K has the form (Z − P0? ≤ δ, α) and was generated by applying the qR∗3 rule
to edges in S0∗, as shown in Fig. 3k, where δ = max{u, v} and α = β ? γ. By (2b), the pre-existing edges from Q0? to Z, and from P0? to Z in S0 have corresponding edges from Q? to Z, and from P ? to Z in S∗, as shown in Fig. 3l, leading to the generated edge from P ? to Z, where δ + = max{u + , v + }. That edge corresponds to K, a contradiction. Case 3: K has the form (P0?−Q0? ≤ δ, α). Since P0? 6≡ Z, then K must have been generated
by an application of the LP rule. Fig. 3m illustrates the case where the intermediate time-point W is not in OT0, and where δ = u + v and α = βγ. By (2b) and (2a),
respectively, the pre-existing edges from Q0? to W to P0? have corresponding edges from Q? to W to P ? in S∗, leading to the propagation in Fig. 3n, where the edge from Q? to P ? corresponds to K, a contradiction. The case where W ∈ OT0is handled similarly. J
Theorem 27 shows that the -DC-checking and π-DC-checking algorithms perform equiv-alent constraint propagations. However, providing an analogous theorem that relates ˆ -DC-checking and standard DC--DC-checking algorithms must be left to future work, since (1) no algorithm has yet been introduced for solving the ˆ-DC-checking problem; and (2) the sound 6-rule DC-checking algorithm for the standard DC-checking problem has not yet been proven complete [11].
43 59 75 91 107 123 139 155 0.3s 3s 30s1m Benchmark 1 N=10, |P|=3 Benchmark 2 N=20, |P|=5 Benchmark 3 N=30, |P|=7 Benchmark 4 N=40, |P|=9 n execution time -DC-Ch S0π-DC-Ch
Figure 4 Execution time vs. number of time-points n.
8
Empirical Evaluation
Theorem 24 shows that the -DC-checking problem can be reduced to the π-DC-checking problem. In particular, the -DC-checking problem for a CSTN S is equivalent to the π-DC-checking problem for the reduced CSTN S0. This section compares the performance of
implementations of an -DC-checking algorithm [11] and the π-DC-checking algorithm [12]. In what follows, the first algorithm is called -DC-Ch and the second is called S0π-DC-Ch
to reflect that it is applied to the reduced CSTN S0. Both implementations were obtained
from Posenato [19], but we modified the -DC-checking algorithm to use only three rules, as discussed in Footnote 3 and Section 7.2. Algorithms and procedures for this evaluation were implemented in Java and executed on a JVM 8 in a Linux machine with two AMD Opteron 4334 CPUs and 64GB of RAM.
To facilitate comparisons with prior work, we tested both implementations on instances of the four benchmarks proposed by Hunsberger and Posenato [11]. Each benchmark has at least 60 DC and 60 non-DC CSTNs, obtained from random workflow schemata generated by the ATAPIS toolset [16]. The numbers of activities (N ) and observations (|P|) were varied, as shown in Fig. 4. Since non-DC networks were regularly solved one to two orders of magnitude faster than similarly sized DC ones, the rest of this section focuses on DC networks.
Fig. 4 displays the average execution times of the two algorithms over all four benchmarks. For S0π-DC-Ch, the execution times include the time required to build S0. Each data point
represents the average of the execution times for instances of the given size. We extended the benchmarks, adding up to 50 DC instances, to generate tight error bars. In Figure 4, each error bar represents a 95% confidence interval for the average of the execution times.
The results demonstrate that, although -DC-Ch performs better in Benchmark 1, the performance difference becomes statistically insignificant as the sizes of the instances increase. The main reason for this behavior is that in small instances the number of observation time-points is quite small, which results in much less constraint propagation. As a result, the linear time required to build S0 and do the extra propagations can have a significant
impact. In contrast, in larger instances, the number of observation time-points is larger, in which case the time to build S0 is dwarfed by the exponential time required for propagating
constraints. The benchmark does not provide any larger instances because such instances are determined from random workflow instances where the maximum instance size is commonly limited to 30-40 tasks [16].
The experiments summarized in this section show that for all but the smallest CSTNs, there is no computational penalty associated with solving the -DC-checking problem by first computing the reduced CSTN S0 and then applying the π-DC-checking algorithm to it.
9
Conclusions
This paper presented a reduction of the ˆ-DC-checking problem to the (standard) DC-checking problem for CSTNs, and a reduction of the -DC-checking problem to the π-DC-checking problem. It also showed that the constraint-propagation rules for the π-DC-checking algorithm are equivalent to the rules for the -DC-checking algorithm. As a result, the paper showed that the -DC-checking problem for CSTNs can be easily represented within the standard CSTN framework (i.e., the -DC-checking problem is not a “new” problem, as has been suggested in recent related work). Furthermore, solving the -DC-checking problem by applying the π-DC-checking algorithm to the reduced CSTN incurs no computational penalty.
Results of this paper can be applied also in other possible variants of CSTNs. Bhargava et al. [1] defined the delay controllability of a Simple Temporal Network with Uncertainty (STNU). This modification allowed a network designer to insert a delay between the execution of a contingent time-point and the time that the executing agent learns of the duration of the corresponding contingent link. And the delay associated with each contingent link can be different. Similarly, a version of delay consistency for CSTNs could be defined to allow different values of epsilon for each observation time-point. In addition, the techniques used in this paper to reduce epsilon-DC for CSTNs to ordinary DC for CSTNs could be used to reduce delay controllability for STNUs to ordinary DC for STNUs.
References
1 Nikhil Bhargava, Christian Muise, Tiago Vaquero, and Brian Williams. Delay Control-lability: Multi-Agent Coordination under Communication Delay. Technical Report MIT-CSAIL-TR-2018-002, MIT, 2018. URL: http://hdl.handle.net/1721.1/113340.
2 Massimo Cairo, Carlo Comin, and Romeo Rizzi. Instantaneous reaction-time in dynamic-consistency checking of conditional simple temporal networks. In 23rd International Sym-posium on Temporal Representation and Reasoning (TIME 2016), pages 80–89, 2016. doi:10.1109/TIME.2016.16.
3 Massimo Cairo, Luke Hunsberger, Roberto Posenato, and Romeo Rizzi. A Streamlined Model of Conditional Simple Temporal Networks - Semantics and Equivalence Results. In 24th International Symposium on Temporal Representation and Reasoning (TIME 2017), volume 90 of LIPIcs, pages 10:1–10:19, 2017. doi:10.4230/LIPIcs.TIME.2017.10.
4 A. Cimatti, L. Hunsberger, A. Micheli, R. Posenato, and M. Roveri. Sound and complete algorithms for checking the dynamic controllability of temporal networks with uncertainty, disjunction and observation. In 21st International Symposium on Temporal Representation and Reasoning (TIME 2014), pages 27–36. IEEE, 2014. doi:10.1109/TIME.2014.21. 5 A. Cimatti, L. Hunsberger, A. Micheli, R. Posenato, and M. Roveri. Dynamic
con-trollability via Timed Game Automata. Acta Informatica, 53(6-8):681–722, 2016. doi: 10.1007/s00236-016-0257-2.
6 Carlo Combi, Luke Hunsberger, and Roberto Posenato. An algorithm for checking the dynamic controllability of a conditional simple temporal network with uncertainty. In 5th International Conference on Agents and Artificial Intelligent (ICAART 2013), volume 2, pages 144–156, 2013. doi:10.5220/0004256101440156.
7 Carlo Combi, Luke Hunsberger, and Roberto Posenato. An algorithm for checking the dynamic controllability of a conditional simple temporal network with uncertainty-revisited. In Agents and Artificial Intelligence, volume 449 of CCIS, pages 314–331. 2014. doi: 10.1007/978-3-662-44440-5_19.
8 Carlo Combi and Roberto Posenato. Towards temporal controllabilities for workflow schemata. In 17th International Symposium on Temporal Representation and Reasoning (TIME 2010), pages 129–136, 2010. doi:10.1109/TIME.2010.17.
9 Carlo Comin and Romeo Rizzi. Dynamic consistency of conditional simple temporal net-works via mean payoff games: a singly-exponential time dc-checking. In 22st International Symposium on Temporal Representation and Reasoning (TIME 2015), pages 19–28. IEEE, 2015. doi:10.1109/TIME.2015.18.
10 Rina Dechter, Itay Meiri, and Judea Pearl. Temporal constraint networks. Artificial Intel-ligence, 49(1–3):61–95, 1991. doi:10.1016/0004-3702(91)90006-6.
11 Luke Hunsberger and Roberto Posenato. Checking the Dynamic Consistency of Conditional Temporal Networks with Bounded Reaction Times. In 26th International Conference on Automated Planning and Scheduling, ICAPS 2016, pages 175–183, 2016. URL: http:// www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13108.
12 Luke Hunsberger and Roberto Posenato. Simpler and faster algorithm for checking the dy-namic consistency of conditional simple temporal networks. In 26th International Joint Con-ference on Artificial Intelligence, IJCAI-18, pages 1324–1330. International Joint Confer-ences on Artificial Intelligence Organization, July 2018. doi:10.24963/ijcai.2018/184.
13 Luke Hunsberger, Roberto Posenato, and Carlo Combi. The Dynamic Controllability of Conditional STNs with Uncertainty. In PlanEx at ICAPS 2012, pages 1–8, 2012.
14 Luke Hunsberger, Roberto Posenato, and Carlo Combi. A sound-and-complete propagation-based algorithm for checking the dynamic consistency of conditional simple temporal net-works. In 22st International Symposium on Temporal Representation and Reasoning (TIME 2015), pages 4–18, 2015. doi:10.1109/TIME.2015.26.
15 Akhil Kumar and Russell R. Barton. Controlled violation of temporal process constraints – models, algorithms and results. Information Systems, 64:410 – 424, 2017. doi:10.1016/
j.is.2016.06.003.
16 Andreas Lanz and Manfred Reichert. Enabling time-aware process support with the atapis toolset. In Lior Limonad and Barbara Weber, editors, BPM Demo Sessions 2014, volume 1295 of CEUR Workshop Proceedings, pages 41–45, 2014.
17 Andreas Lanz, Barbara Weber, and Manfred Reichert. Time patterns for process-aware information systems. Requirements Engineering, 19(2):113–141, 2014. doi:10.1007/ s00766-012-0162-3.
18 Dian Liu, Hongwei Wang, Chao Qi, Peng Zhao, and Jian Wang. Hierarchical task network-based emergency task planning with incomplete information, concurrency and uncertain duration. Knowledge-Based Systems, 112:67 – 79, 2016. doi:10.1016/j.knosys.2016.08. 029.
19 Roberto Posenato. A CSTN(U) consistency check algorithm implementation in Java. ver-sion 1.22. http://profs.scienze.univr.it/∼posenato/software/cstnu, 2017.
20 Ioannis Tsamardinos, Thierry Vidal, and Martha E. Pollack. CTP: A new constraint-based formalism for conditional, temporal planning. Constraints, 8:365–388, 2003. doi: 10.1023/A:1025894003623.
21 Peng Yu, Jiaying Shen, Peter Z. Yeh, and Brian Williams. Resolving over-constrained conditional temporal problems using semantically similar alternatives. In 25th International Joint Conference on Artificial Intelligence, IJCAI’16, pages 3300–3307, 2016.
