Converting Simple Temporal Networks with Uncertainty into Minimal Equivalent Dispatchable Form

Venue: icaps-conference_org_ICAPS_2024_Conference
Published: 2023-12-05 09:35:37

Abstract: A Simple Temporal Network with Uncertainty (STNU) is a structure
for representing and reasoning about time constraints on actions that
may have uncertain durations.  
An STNU is dynamically controllable (DC) if there exists a dynamic strategy 
for executing the network that guarantees that all of its constraints will be satisfied 
no matter how the uncertain durations turn out---within their specified bounds.  
However, such strategies typically require exponential space.  
Therefore, converting a DC STNU into a so-called dispatchable form 
for practical applications is essential.  
The relevant portions of a real-time execution strategy for a dispatchable
STNU can be incrementally constructed during execution, requiring only $O(n^2)$ space,
while also providing maximum flexibility and minimal computation during the execution
of the network.  
Although existing algorithms can generate equivalent-dispatchable STNUs,
they do not guarantee a minimal number of edges in the STNU graph.  
Since the number of edges directly impacts the computations during execution, this paper
presents a novel algorithm for converting any dispatchable STNU into 
an equivalent dispatchable network having a minimal number of edges.  
The complexity of the algorithm is $O(kn^3)$, where $k$ is the number of actions with uncertain durations, 
and $n$ is the number of timepoints in the network.  
The paper also provides an empirical evaluation of the reduction of edges obtained by the impact of the new algorithm.

Main paper: 
 background: 
 This section summarizes definitions and results for the dispatchability of Simple Temporal Networks (STNs) and STNs with Uncertainty (STNUs). Our focus is on the dispatchability of STNUs, but the work on STNs is also important.Definition 1 ( (Dechter, Meiri, and Pearl 1991) ). A Simple Temporal Network (STN) is a pair S = (T , C), where T is a set of real-valued variables called timepoints (TPs) and C is a set of constraints of the form (Y -X ≤ δ), for some X, Y ∈ T and some δ ∈ R. Each STN S = (T , C) has a corresponding graph G = (T , E), where the TPs in T serve as the graph's nodes, and the constraints in C correspond to labeled, directed edges in E. In partic-ular: E = {X δ Y | (Y -X ≤ δ) ∈ C}. For convenience, X δ Y may be notated as (X, δ, Y ).An STN is consistent if it has a solution as a constraint satisfaction problem. Although solutions for consistent STNs can be computed in advance of execution (e.g., by the Bellman-Ford algorithm (Cormen et al. 2022 )), it is often desirable to preserve as much flexibility as possible during execution (e.g., to enable reacting to unanticipated events). Toward that end, Tsamardinos, Muscettola, and Morris (1998) first specified a real-time execution algorithm for STNs, called the Time Dispatching (TD) algorithm, and then defined an STN to be dispatchable if every run of the TD algorithm was guaranteed to generate a solution. The TD algorithm provides maximum flexibility during execution by maintaining time windows for each timepoint. It requires minimal computation during execution by propagating the effects of each real-time execution, X = v, only locally (i.e., to X's neighbors; that is, timepoints connected to X by a single edge). Morris (2016) subsequently provided a graphical characterization of STN dispatchability in terms of vee-paths.Definition 2 (Vee-path (Morris 2016) ). A vee-path is a path consisting of zero or more negative edges followed by zero or more non-negative edges. If P is a vee-path from X to Y that is also a shortest path from X to Y , then P is called a shortest vee-path (SVP). If, in addition, P contains no proper cycles, then P is called a simple shortest vee-path (SSVP). Theorem 1. (Morris 2016) An STN is dispatchable if and only if whenever there is a path from any X to any Y , then there is a shortest vee-path from X to Y (i.e., an SVP). Definition 3 ( (Morris, Muscettola, and Vidal 2001) ). A Sim-120 ple Temporal Network with Uncertainty (STNU) augments an STN to accommodate actions with uncertain durations. Formally, an STNU is a triple, S = (T , C, L), where (T , C) is an STN, and L is a set of contingent links (CLs), each of the form (A, x, y, C), where A, C ∈ T and 0 < x < y < ∞.Intuitively, once the activation timepoint A is executed (i.e., assigned a value during execution), the contingent timepoint C is guaranteed to be executed such that the duration C -A ∈ [x, y], but the particular execution time for C is not controlled by the agent in charge of executing the network; instead, it is only observed in real time. ⇒ For convenience, and without loss of generality, we assume that no contingent timepoint C can serve as the activation timepoint for another contingent link.Each STNU S = (T , C, L) has a corresponding graph,G = (T , E o ∪ E lc ∪ E uc ), where (T , E o ) is the graph for the STN (T , C), and E lc and E uc contain labeled, directed edges derived from the contingent links in L. In particular:E lc = {A c:x C | (A, x, y, C) ∈ L}, and E uc = {C C:-y A | (A, x, y, C) ∈ L}.The so-called lower-case (LC) edge 140 A c:x C represents the uncontrollable possibility that the duration C -A might take on its minimum value x, while the so-called upper-case (UC) edge C C:-y A represents the uncontrollable possibility that C -A might take on its maximum value y. Such edges may be respectively notated as (A, c:x, C) and (C, C:-y, A), while constraints in C and edges in E o may be called ordinary constraints and edges, respectively, to distinguish them from the LC and UC edges.Definition 4. An STNU S = (T , C, L) is dynamically controllable (DC) if there exists a dynamic strategy for executing its timepoints such that all constraints in C are guaranteed to be satisfied no matter how the durations of the CLs in L turn out (Morris, Muscettola, and Vidal 2001) . The strategy is dynamic in that its execution decisions cannot depend on advance knowledge of future contingent executions.Several polynomial-time DC-checking algorithms have been presented in the literature (Morris 2006 (Morris , 2014;; Cairo, Hunsberger, and Rizzi 2018; Hunsberger and Posenato 2022) . However, in positive instances, such algorithms only confirm the existence of a dynamic execution strategy; they do not output one. Since such strategies typically require exponential space, Morris (2016) extended the concept of dispatchability from STNs to extended STNUs (ESTNUs), as follows.First, we must backtrack. Some of the DC-checking algorithms for STNUs generate a new kind of conditional constraint called a wait (Morris 2006) . A typical wait can be glossed as: "If the contingent timepoint C has not yet executed, then W must wait until at least w after the activation timepoint A." Its graphical representation is the generated UC edge, W C:-w A, where A and C are the activation and contingent timepoints for some CL (A, x, y, C). Intuitively, since the execution of C cannot be directly controlled and might occur as late as y after A, W must wait until w after A; but if C executes earlier than w after A, then the wait is automatically satisfied and W may be executed immediately.Generating wait edges is not required to determine the DC property (e.g., as seen in the algorithms of Morris (2014) and Cairo, Hunsberger, and Rizzi (2018) ), but wait edges turn out to be necessary for enforcing the dispatchability of STNUs. Anticipating this, Morris (2016) defined an extended STNU (ESTNU) to be an STNU augmented to include zero or more waits (equivalently, an STNU graph together with a set E ucg of generated UC edges). He then defined the dispatchability of ESTNUs in terms of their STN projections, as follows.Definition 5 (Situation). Let S be an STNU with k contingent links whose duration ranges are[x 1 , y 1 ], . . . , [x k , y k ]. A situation (for S) is a k-tuple ω = (ω 1 , ω 2 , . . . , ω k ) where ω i ∈ [x i , y i ] for each i ∈ {1, 2, . . . , k}. The space of all situations is notated as Ω = [x 1 , y 1 ] × . . . × [x k , y k ].In other words, a situation ω ∈ Ω specifies a fixed duration for each contingent link. For convenience, if C is the contingent timepoint for a link (A, x, y, C), then the duration C -A in the situation ω may be notated as ω c .G = (T , E o ∪ E lc ∪ E uc ∪ E ucg ), and any situation ω, the projection of G onto ω is the STN G ω = (T , E o ∪ E ω lc ∪ E ω uc ∪ E ω ucg ), where:• E ω lc = {(A i , ω i , C i ) | ∃(A i , c i :x i , C i ) ∈ E lc } • E ω uc = {(C i , -ω i , A i ) | ∃(C i , C i :-y i , A i ) ∈ E uc } • E ω ucg = {(W, δ, A i ) | ∃(W, C i :-v, A i ) ∈ E ucg and δ = max{-ω i , -v}} Definition 7 (Dispatchable ESTNU). An ESTNU is dispatchable iff all of its STN projections are dispatchable (as STNs).Morris suggested that a dispatchable ESTNU could be executed using the TD algorithm for STNs, while pretending that the execution times for the contingent TPs were chosen by external reality. Others (citation omitted for blind review) recently confirmed this by formally defining a real-time execution algorithm for ESTNUs and proving that it is guaranteed to successfully execute any dispatchable ESTNU, preserving maximum flexibility while requiring minimal computation.Most DC-checking algorithms do not output a dispatchable ESTNU. However, as Morris (2014) noted, his O(n 3 )-time DC-checking algorithm can easily be modified to generate waits and, insodoing, guarantee that it will output an equivalent dispatchable ESTNU. More recently, Hunsberger and Posenato (2023) presented a faster algorithm for generating equivalent dispatchable ESTNUs. However, neither algorithm makes any claim about the number of edges in the dispatchable output. Since that number impacts the performance of the real-time execution algorithm, producing an equivalent dispatchable ESTNU with a minimal number of edges is of practical importance. This paper presents the first algorithm for solving this problem. It runs in O(kn 3 ) worst-case time. 
the mindisp estnu algorithm: 
 This section introduces our new minDisp ESTNU algorithm.When given a dispatchable ESTNU as input, it outputs an equivalent dispatchable ESTNU with a minimal number of edges. 1 Since the input is dispatchable, the algorithm need only determine which edges can be removed while preserving dispatchability (i.e., while ensuring that every pair of timepoints connected by a path are connected by an SVP in every projection). However, a key observation is that for any timepoints V and Y , the length of the shortest vee-path from V to Y may be different across different STN projections.Definition 8 (Path-length notation). The length of a path P in a projection G ω is notated as |P| ω . For timepoints X and Y , d ω (X, Y ) denotes the length of the shortest path from X to Y in G ω ; and maxd(X, Y ) = max ω {d ω (X, Y )} denotes the maximum such length across all projections. Finally, d o (X, Y ) denotes the length of the shortest path from X to Y that has only ordinary edges from the ESTNU graph.For example, suppose e = (V, σ, Y ) is an ordinary edge in a dispatchable ESTNU G. Suppose further that in every STN projection G ω , there is an SVP P from V to Y that does not use e, and such that |P| ω ≤ σ. Then in every projection, e is not needed to ensure dispatchability. Therefore, the ESTNU obtained by removing e must still be dispatchable.If maxd(V, Y ) is determined solely by ordinary edges, then the dispatchability algorithm for STNs (i.e., for ordinary edges) can be used to remove all ordinary edges dominated by ordinary vee-paths (Tsamardinos, Muscettola, and Morris 1 We intentionally blur the distinction between an ESTNU and its graph, and between edges and constraints.V C A Y β = -2 C :α - y = C :- 6 α = 4 c:x = c:1 C:-y = C:-10 γ = 6 δ = 1 3 (1) VAY β (2 ) V A Y w t (3 ) V A C Y β (4) VACY wt (5) VCY (6 ) V C A Y Minimum of Above Plots maxd(V, Y ) = 71 2 6 7 10 The lengths of the relevant paths in Figure 1 are speci-285 fied algebraically in Table 1 . Since each plot is continuous, piecewise-linear and monotonic (whether non-increasing or non-decreasing), the minimum plot, represented by the thick blue dashed line in Figure 1 , can be determined by finding each value ω † c ∈ [x, y] = [1, 10] at which any of the above 290 plots might intersect, and then taking the minimum value of the plots at each such ω † c . The maximum of those minimum values, across all of the intersection points, will be the maximum SVP length across all projections (i.e., maxd(V, Y )).The Problem Turns Out to be Simpler!Although six different paths from V to Y in the ESTNU graph from Figure 1 were explored above, it turns out that in(1) |VAY β | ωc = β + δ = 11 (2) |VAY wt | ωc = max{-ω c , α -y} + δ = max{δ-ω c , α+δ-y} = max{13-ω c , 7} ∈ [7, 12] (3) |VACY β | ωc = β + ω c + γ = 4 + ω c ∈ [5, 14] (4) |VACY wt | ωc = max{-ω c , α -y} + ω c + γ = max{γ, α + γ -y + ω c } = max{6, ω c } ∈ [6, 10] (5) |VCY | ωc = α + γ = 10 (6) |VCAY | ωc = α -ω c + δ = 17 -ω c ∈ [7, 16]Table 1 : The lengths of the paths in Figure 1 V general it suffices to consider only two of the paths: namely, (2) VAY wt and (4) VACY wt , as shown in Figure 2 . As will be seen, the desired max-of-the-mins value must occur at the 300 intersection of these two paths. But if the intersection point is outside of the interval (x, y), then one of the paths, ( 2) and (4), will dominate the other throughout the entire interval [x, y] which, as will be shown, implies that a pre-existing ordinary path is shortest from V to Y . On the other hand, if the intersection lies within the interval (x, y), the desired maxd(V, Y ) value will necessarily occur at that intersection point-because path (2) is non-increasing, while path (4) is non-decreasing. Hence, it suffices to find where the paths (2) and (4) intersect, which a simple computation reveals is where ω = δ -γ. For the numbers in Figure 2 , the two paths intersect where ω = δ -γ = 13 -6 = 7 ∈ (1, 10).EQUATIONTheir lengths in the projection, ω = 7, gives the value of maxd(V, Y ), which also happens to be 7, as seen earlier.Although the path, (3) VACY β , in Figure 1 has the minimum length for ω ∈ [1, 2], that has no effect on the value of maxd(V, Y ). Our new algorithm explores simpler structures like those in Figure 2 to find the strongest constraints entailed by various combinations of labeled and ordinary edges.The ESTNU in Figure 3 Since special structures can be nested, exploring each one only once will typically not be sufficient. However, as will be shown later on, it suffices to consider nestings that use the labeled edges from each contingent link at most once. Therefore, k rounds of processing, where each round involves processing every special structure, will suffice.Algorithm 1 shows pseudocode for our new algorithm. It takes a dispatchable ESTNU as its only input and generates as its output an equivalent dispatchable ESTNU having a minimal number of edges. The algorithm begins (at Lines 3-8) by inserting any missing weak-ord edges needed to make the input ESTNU weak-ord complete (defined below).Definition 9 (Weak-ord Edges). Let (A, c:x, C), (C, C:-y, A) and (V, C:-v, A) be the LC, UC and any wait edges associated with a contingent link (A, x, y, C). The corresponding weak-ord edges are (A, y, C), (C, -x, A) and (V, -x, A). For any labeled edge e, the corresponding weak-ord edge is denoted by e o . An ESTNU G is called weak-ord complete if for each labeled edge e in G, G contains an ordinary edge ê such that |ê| ≤ |e o |.Note that for any edge e and situation ω, |e| ω ≤ |e o |. For the LC and original UC edge, the result is trivial. For waits:|(V, C:-v, A)| ω = max{-v, -ω c } ≤ max{-x, -x} = -x = |(W, -x, A)|.(We assume -v < -x, since otherwise the wait is equivalent to the ordinary edge (V, -x, A).)Since every inserted weak-ord edge is dominated by the projection of its labeled counterpart in G, such edges are not needed for dispatchability. However, as will be seen, making them explicit in G enables the algorithm to compute maxd(V, Y ) values derived from the kinds of special structures seen in Figure 2 . To ensure that they are removed before the end of the algorithm, each inserted weak-ord edge is "marked" for later removal.The next part of the algorithm comprises the multiply nested loops at Lines 9-23. Their purpose is to discover and insert ordinary edges that are entailed by the kinds of special structures seen in Figure 2 . Since these structures can be nested to a maximum depth of k, the outermost loop does k iterations. Each iteration begins (at Line 10) by using Johnson's algorithm to compute the distance matrix d for the STN consisting of the ordinary edges from the input ESTNUwhich includes the weak-ord edges inserted at Lines 3-8, as Eo • • = Eo ∪ {(V, -x, A)} // x is lower bound for C -A marked • • = marked ∪ {(V, -x, A)} for i • • = 1 to k do // k = maxedgeAdded • • = ⊥ foreach (A, x, y, C) ∈ L do foreach V, Y ∈ T \{A, C} | V ̸ ≡ Y and ∃(V, C:-q, A) ∈ Eucg do 14 γ • • = d(C, Y ), δ • • = d(A, Y ) 15 if γ < ∞ and δ < ∞ then 16 ω • • = δ -γ 17 if x < ω < y then 18 θ • • = max{-ω, -q} + δ 19 if θ ≤ d(V, Y ) then // max min ord edge 20 Eo • • = Eo ∪ {(V, θ, Y )} 21 marked • • = marked ∪ {(V, θ, Y )} 22 edgeAdded • • = ⊤ if edgeAdded == ⊥ thenmarked uc • • = marked uc ∪{(C, Ĉ:v, Â)} foreach (V, C:-v, A) ∈ Eucg do // Mark dominated waits from Eucg if d(V, A) ≤ -v or d(V, C) ≤ 0 then marked uc • • = marked uc ∪ {(V, C:-v, A)} else foreach U ∈ T | ∃(U, C:-u, A) ∈ Eucg do 40 if d(V, U ) ≤ 0 and d(V, U ) -u ≤ max{-y, -v} then 41 marked uc • • = marked uc ∪ {(V, C:-v, A)} Eucg • • = Eucg\marked uc return G = (T , Eo ∪ E lc ∪ Euc ∪ Eucg)well as any ordinary edges inserted during previous iterations. The inner loops (Lines 12-22) then explore all possible simpler structures involving timepoints V, A, C and Y , as 380 illustrated in Figure 2 . If the values of γ and δ are finite, then ω = δ -γ is the value of ω c at which the paths labeled ( 2) and (4) in Figure 2 intersect. If ω ∈ (x, y), then the desired max-of-the-mins value (i.e., a possible update for maxd(V, Y )) (called θ in the pseudocode) is computed 385 (Line 18). If θ ≤ d(V, Y ), then the ordinary edge (V, θ, Y ) is inserted-and marked-to make explicit the constraint entailed by the special structure. It is marked because it is entailed by other edges and, hence, must be removed before the algorithm completes. In the meantime, it contributes to the 390 distance matrix computation at the start of the next iteration. After all of the ordinary edges entailed by combinations of labeled and ordinary edges have been inserted into the graph, the final part of the algorithm (Lines 24-42) determines which edges to remove from the ESTNU to achieve 395 the minimal equivalent dispatchable ESTNU. At Line 24, the STN dispatchability algorithm is run on the subgraph of ordinary edges (i.e., the edges in E o ). This replaces that ordinary STN subgraph with a minimal equivalent dispatchable STN. Next, any marked ordinary edges that were not removed by 400 the STN dispatchability algorithm are removed at Line 26.Lines 28-34 remove negative (ordinary or wait) edges emanating from any contingent TP, and non-negative ordinary edges terminating at any contingent TP. That's because in a dispatchable network, the presence of such edges necessarily 405 imposes constraints on the corresponding activation TP that make the above-mentioned edges redundant.Lines 35-42 remove wait edges that are dominated by alternative paths that are either ordinary or involving a different wait edge associated with the same contingent link.Complexity. The worst-case time complexity of the minDisp ESTNU algorithm is dominated by the k+1 calls to Johnson's algorithm which has complexity O(mn log n), where m ≤ n 2 is the maximum number of edges in the created STN. Therefore, the overall complexity is O(kn 3 ). 
formal analysis: 
 This section presents a proof of correctness for the minDisp ESTNU algorithm. Throughout this section, we assume G is a dispatchable and weak-ord complete ESTNU.Definition 10. We say that an edge e in a projection G ω derives from a contingent link (A, x, y, C) if e is the projection of an LC, UC or wait edge associated with that link. Definition 11 (Needed). A contingent link (A, x, y, C) is needed for maxd(X, Y ) in G if removing all of the labeled edges associated with that contingent link from G would change the value of maxd(X, Y ).If no contingent link is needed for maxd(X, Y ), then its value is determined solely by ordinary edges in G. Otherwise, there must be some contingent link (A, x, y, C) that is needed to determine maxd(X, Y ). Lemma 1. If a contingent link (A, x, y, C) is needed for maxd(X, Y ), then at least two labeled edges associated with (A, x, y, C) are needed for maxd(X, Y ).Proof. Suppose only one labeled edge is needed.Case 1: The LC edge e = (A, c:x, C) is the only labeled edge associated with (A, x, y, C) that is needed for maxd(X, Y ). Let ω be any situation in which e is needed. Then for any situation ω ′ that is the same as ω except possibly for the value of C -A, e must also be needed, since otherwise there would have to be a path P in G that does not include e and such that Theorem 2. Suppose (A, x, y, C) is a contingent link needed for maxd(X, Y ) such that no other needed contingent link is constrained to have its activation TP occur after A. Then|P | ω ′ ≤ maxd(X, Y ). But then |P | ω = |P | ω ′ = maxd(X, Y ), contradicting that e is needed in G ω . But since e is needed in G ω ′′ ,maxd(X, Y ) = min{d o (X, V ) + maxd(V, Y ) such that ∃(V, C: -v, A) ∈ E ucg }Proof. Let ω ′ be any situation in which some paths, P 1 , P 2 , . . ., each involving one or more edges derived from (A, x, y, C), are needed to determine maxd(X, Y ); and let ω ′ c denote the value of C -A specified by ω ′ . By construction, the lengths of the P i paths in G ω ′ must be strictly less than the lengths of any other paths from X to Y in G ω ′ .Next, let Ω ′ c denote the family of situations, where each situation in Ω ′ c specifies the same duration as ω ′ for every contingent link except possibly (A, x, y, C). If we let µ ∈ [x, y] be any possible value for C -A, then the family of situationsΩ ′c is effectively parameterized by µ; so we can let Ω ′ c (µ) denote the situation in Ω ′ c for which C -A = µ. Since the lengths of the P i paths are less than the lengths of any other paths from X to Y in G ω ′ ; and their lengths vary piecewise-linearly with µ or -µ, there must be some c ; and we refer to the duration of C -A by ω c rather than µ (i.e., we effectively stipulate that Ω * c is parameterized by ω c , rather than µ).f 1 (ω c ) = |XVAY | ω = σ + max{-v, -ω c } + δ f 2 (ω c ) = |XACY | ω = β + ω c + γ f 3 (ω c ) = |XVACY | ω = σ + max{-v, -ω c } + ω c + γ f 4 (ω c ) = |XCAY | ω = α -ω c + δTable 2 : The lengths of the paths in Figure 7 Let ω be any projection in Ω * c . As illustrated in Figure 7 , each simple shortest vee-path from X to Y in G ω , which by construction must include edges derived from (A, x, y, C), must have one of the following forms:2 XVAY , XACY , XVACY or XCAY , where the subpaths 565 XC , XV , XA, CY and AY contain only ordinary edges or edges derived from other contingent links. Therefore, the lengths of those subpaths are constant across all situations in Ω * c . In contrast, the lengths of the paths, XVAY , XACY , XVACY and XCAY , are functions of ω c , 570 as listed in Table 2 using names such as f 1 (ω c ), f 2 (ω c ), etc.Note that, by construction, XCY and XAY don't have any edges derived from (A, x, y, C). Thus, using an argument similar to that in the proof of Lemma 1, they cannot be needed for maxd(X, Y ) across the familyΩ * c . Therefore, 575 maxd(X, Y ) < |XCY | ω and maxd(X, Y ) < |XAY | ω .From Table 2 it is apparent that the four length functions are each continuous, piecewise-linear and monotone (either non-decreasing or non-increasing). Therefore, if we define f (ω c ) = min 1≤i≤4 {f i (ω c )} to be the minimum of the four 580 length functions over [a, b] , then it too is continuous and piecewise-linear, although not necessarily monotone. Furthermore, the endpoints of each segment of the f (ω c ) function are necessarily at values of ω c where at least two of the four length functions intersect. In what follows, we first com-585 pute the values of f (ω c ) at each possible intersection point, which completely determines the value of maxd(X, Y ) = max{f (ω c ) | ω c ∈ [a, b]}. We then show that for each such ω c , f (ω c ) = min{f 1 (ω c ), f 3 (ω c )} ≤ maxd(X, Y ). This will prove that it suffices, in general, to restrict attention to f 1 590 and f 3 (i.e., to the paths XVAY and XVACY ) to determine maxd(X, Y ), which shall require only computing the single value of ω c where those two paths intersect.Computing the intersection points. To keep track of all possible points of intersection among the paths 595 XVAY , XACY , XVACY and XCAY , we use expressions such as τ ij to denote the value of ω c where f i (ω c ) = f j (ω c ). For example, τ 13 denotes the value of ω c at which f 1 (ω c ) = f 3 (ω c ) (i.e., where |XVAY | = |XVACY |). Intersection points that depend on the projected length of the wait edge 600 (i.e., max{-v, -ω c }) are given the superscript v (for the case where -v ≥ -ω c ) or w (for the case where -ω c ≥ -v).It is easy, but tedious to compute the seven distinct points of intersection. For example, f 1 (ω c ) = f 2 (ω c ) if and only if σ + max{-v, -ω c } + δ = β + ω c + γ. For -v ≥ -ω c , links can be needed to determine any given maxd(X, Y ) value. Since the order of nesting is typically not known in advance, the algorithm performs k outer iterations to ensure that every possible nesting order can be accommodated.Second, for any contingent links needed for maxd(C, Y ) or maxd(A, Y ), there must be durations that ensure that Since the values of maxd(C, Y ) and maxd(A, Y ) cannot need as many contingent links as the value of maxd(V, Y ), because they cannot use (A, x, y, C), the inductive hypothesis ensures that the algorithm correctly computes maxd(C, Y ) and maxd(A, Y ) and, therefore, it correctly computes maxd(V, Y ).Lemma 4. For a dispatchable ESTNU G, and contingent timepoint C, removing negative (ordinary or wait) edges emanating from C, and non-negative ordinary edges pointing at C cannot threaten the dispatchability of G.Proof. Omitted due to space limitations.Theorem 4. Algorithm 1 computes an equivalent dispatchable ESTNU having a minimal number of edges.Proof. Suppose the output G of Algorithm 1 contains an ordinary edge e = (X, δ, Y ) that is not needed for dispatchability. Then in every projection G ω , there must be some shortest veepath P from X to Y that does not use e such that |P| ω ≤ δ. But then maxd(X, Y ) ≤ δ and the algorithm marks e for removal, contradicting that e in the output G.Next, suppose E = (V, C:-v, A) is a wait edge in the output G that is not needed for dispatchability but not marked for removal. This happens when all of the following hold: (1) maxd(V, A) > -v; (2) maxd(V, C) > 0; and (3) for each wait (U, C:-u, A) ∈ E ucg , maxd(V, U ) > 0 or maxd(V, U ) -u > max{-y, -v}. We will show that there must be a value ω c < v such that in that projection, every alternative path from V to A has length greater than -ω c = |(V, C:-v, A)|. First, note that for any (U, C:-u, A), if maxd(V, U ) > 0, then |VUA| > max{-u, -ω c } > -ω c . Next, let -u * be the minimum value of maxd(V, U ) -u for all waits (U, C:-u, A) where maxd(V, U ) -u > max{-y, -v}. Then -u * > -v. Let -u † = min{-u * , maxd(V, A)} > -v. And then let ω c be any point in (u † , v). It is not hard to check that the length of every alternative path from V to A (i.e., VA o , VCA or any VUA) is greater than -ω c = |E|. Hence, E is needed. 
conclusions: 
 This paper presented a new algorithm for generating equivalent dispatchable ESTNUs having a minimal number of edges. The empirical evaluation demonstrated its effectiveness in reducing the number of edges. The formal analysis proved the algorithm's correctness. 
4 empirical evaluation: 
 We evaluated the performance of the minDisp ESTNU algorithm, comparing it against Morris14 and FD STNU . Our aim was to demonstrate: (1) the increase in computational cost required to minimize a dispatchable ESTNU, and (2) the reduction in 420 the number of edges in the minimized network.Morris14 is the DC-checking algorithm proposed by Morris (2014), modified according to his high-level description to enable it to generate equivalent dispatchable networks for DC instances. We implemented the modified version for this 425 evaluation. FD STNU is the fast dispatchable STNU algorithm presented by Hunsberger and Posenato (2022) .We implemented all algorithms in Java and ran them on a JVM 21 with 8GB of heap memory on a Linux computer with two AMD Opteron ™ 4334@3.1 GHz (6200 BogoMIPS). Our 430 implementations are available at (omitted for blind review).For our evaluation, we used one of the benchmarks published by Posenato (2020) . For each n ∈ contingent links, and about 6 incident edges for each node (for a total of m ≈ 3n edges).Each DC STNU was separately fed to the Morris14 and FD STNU algorithms to generate a pair of equivalent dispatchable ESTNUs. Both ESTNUs were then fed to the minDisp ESTNU algorithm to check that the two minimized networks were the same. For the large majority of instances, they were, but for a few instances, the two minimized ESTNUs had some different edges. We discovered that simultaneity constraints among pairs of timepoints can result in trivially confidence intervals (difficult to see because the standard deviations are small). The average number of edges in the minimized networks is an order of magnitude smaller than in the ESTNUs generated by Morris14 and about 34% smaller than in the ESTNUs generated by FD STNU , confirming the importance of minDisp ESTNU for providing dispatchable networks that can be more efficiently executed.Fig. 5 demonstrates the computational cost of generating minimal dispatchable ESTNUs. The results highlight the influence of the number of edges on the computing time, 460 a factor that is absorbed by the O(kn 3 ) theoretical worstcase complexity. Indeed, the minDisp ESTNU average execution time when Morris14 gives the input instances (violet line) is an order of magnitude higher than the average execution time of minDisp ESTNU when FD STNU gives the input instances 465 (green line). For n = 2000, the average execution time of minDisp ESTNU (Morris14) is not reported because it was above the 30m timeout. Such a difference is equal to the difference in the average number of edges between the instances  
: 
 will be satisfied no matter how the uncertain durations turn out-within their specified bounds. However, such strategies typically require exponential space. Therefore, it is essential to convert a DC STNU into a so-called dispatchable form for practical applications. For a dispatchable STNU, the relevant portions of a real-time execution strategy can be incrementally constructed during execution, requiring only O(n 2 ) space, while also providing maximum flexibility but requiring only minimal computation during execution. Existing algorithms can generate equivalent dispatchable STNUs, but with no guarantee about the number of edges in the output STNU. Since that number directly impacts the computations during execution, this paper presents a novel algorithm for converting any dispatchable STNU into an equivalent dispatchable network having a minimal number of edges. The complexity of the algorithm is O(kn 3 ), where k is the number of actions with uncertain durations, and n is the number of timepoints. The paper also provides an empirical evaluation of the order-ofmagnitude reduction of edges obtained by the new algorithm.Temporal constraint networks facilitate representating and reasoning about temporal constraints on activities. Among the many kinds of temporal constraint networks in the literature, Simple Temporal Networks with Uncertainty (STNUs) are one of the most important because they allow the explicit representation of actions with uncertain durations (Morris, Muscettola, and Vidal 2001) . In an STNU, an action with uncertain duration is represented by a contingent link that specifies bounds on the duration's uncertainty. A contingent link also represents that a scheduler cannot decide the action's duration, but instead can only observe it at runtime. Therefore, for STNUs, it is important to know whether a strategy exists for executing the network that guarantees that all of its constraints will be satisfied no matter how the uncertain durations play out. If such a strategy exists, the STNU is said to be dynamically controllable (DC). The literature includes several polynomial-time algorithms for checking the DC property that differ in their approaches to finding possible inconsistencies, characterized by different kinds of negative cycles (Stedl and Williams 2005; Morris 2006 Morris , 2014;; Nilsson, Kvarnstrom, and Doherty 2014; Cairo, Hunsberger, and Rizzi 2018) . But the algorithms are not constructive (i.e., they do not output actual execution strategies in positive instances).For DC STNUs, an execution strategy can be specified by pre-computing every possible incremental schedule for every possible combination of uncertain action durations. However, such a strategy requires exponential space and, therefore, is exceedingly impractical. So, for practical applications, Morris (2014 Morris ( , 2016) ) proposed converting DC STNUs into an equivalent dispatchable form. For a dispatchable STNU, a dynamic execution strategy can be generated incrementally, during execution, using only O(n 2 ) space, where n is the number of timepoints (citation omitted/blind review). Moreover, such a strategy provides maximum flexibility for the action scheduler, but requires minimal real-time computation.Most DC-checking algorithms do not guarantee a dispatchable output, but Morris (2014) indicated that his DC-checking algorithm could be modified to do so. We call that version of his algorithm Morris14. More recently, Hunsberger and Posenato (2023) presented an algorithm for creating an equivalent dispatchable STNU, called FD STNU . Although these are the only known algorithms that guarantee an equivalent dispatchable output, they do not provide any guarantees about the number of edges in it. Since the number of edges directly impacts computations during execution, this paper presents a novel algorithm for converting any dispatchable STNU into an equivalent dispatchable network with a minimal number of edges. The complexity of the algorithm is O(kn 3 ), where k is the number of actions with uncertain durations, and n is the number of nodes in the network. The paper provides an empirical evaluation of the order-of-magnitude reduction in the number of edges obtained by the new algorithm. 
 
 Appendix: Lemma 2 does not rule out that multiple wait edges might be needed across different situations. However, in the projection G ω ′ , some wait edge (V, C:-v, A) must minimize the length of the path from X to V to A over some open interval, as described earlier. (If more than one wait yields the same minimum value, then disregard all but one.) Therefore, we may safely assume henceforth that only one wait edge is needed over the restricted family of situations Ω * c . 


Decision: The paper elaborates presents an algorithm that transforms an (E)STNU into an equivalent one with a minimal number of edges. This is important for the execution of dynamic strategies, because the execution algorithm time is directly influenced by the size of the network.

There was considerable discussion on this paper.

Specifically, three points were raised:

1. Limited contribution: one of the reviewers thinks that finding the minimal dispatchable network is a very incremental contribution. The other reviewers argued that this is non-trivial and significant enough for a conference paper.
2. Experimental analysis: all experiments are on random networks, but the authors stress in the paper the importance for practical applications, and no experiments on real data are reported. In the rebuttal, the authors promised to provide a plot showing the benefits in term of execution time. We recommend to provide this data, but the majority of reviewers agreed that the paper is acceptable even without this promised contribution.
3. Organization and clarity: the organization of the paper with teh formal analysis at the end was criticized, but the reviewers do not see this as a fatal flaw. 

In sumamry, we could not reach a consensus among the reviewers, but it seems to me that there are no knocking-down arguments for the paper, so I am recommending acceptance.

Reviews: review: strength_weakness: strength_weakness: Significance: It is stated in the abstract and introduction that minimizing the number of edges reduces computation time during execution. This is the main motivation provided by the authors to claim the significance of their contribution. However, for the reader, it is unclear what the relation is between the number of edges and the computation time during execution. The statement is neither theoretically justified nor empirically evaluated.  Therefore, it cannot be judged whether the obtained results (reduction in number of edges) significantly improve the computation time for execution. This is an important concern that needs to be addressed for acceptance. 

Clarity: In Section 3, multiple comments are included such as “as will be seen” (line 299), and “as will be shown” (e.g. line 304). I assume that the authors mean that they will further in the paper (Section 5 I believe) will formally explain why these statements are true. It might be helpful to already refer to the corresponding theorems/lemmas, to help the reader navigate through the different components of the algorithm and corresponding proofs. I find it rather hard to now navigate through Section 5 because I miss the connection with Section 3. 
Also within Section 3 the subsection “Nesting of Special Structures” misses a bit of introduction and connection to the rest of the paper.  
I think there is potential to improve the clarity of the paper by connecting the illustrative examples, subparts of the algorithm, and the corresponding theorems and proofs in a proper way. 

Technical soundness: The authors claim that the complexity of the algorithm runs in O(kn^3) worst-case time, where k is the number of actions with uncertain durations, and n is the number of timepoints because it is dominated by the k+1 calls to Johnson's algorithm (line 9 /10 of pseudocode). For a non-expert reader, it is a bit hard to follow why this is correct, mainly why it is true that the complexity is dominated by the k+1 calls to Johnson’s algorithm and why it is true that m <= n^2.
questions: questions: 1. Could you provide the theoretical justification for the claim that reducing the number of edges reduces the computation time during execution?  
2. By how much does the number of edges reduce the computation time during execution in your experiments? 
3. Could you explain how you came to O(kn^3)? So, could you explain why the k+1 calls of Johnson dominate the complexity, and not the subsequent nested for loops? 
4. Could you provide the proof of Lemma 4 in supplementary material? 
5. Could you provide the needed connections between Section 3 and Section 5 to improve the clarity of the paper? So instead of, “will be shown” in Section 3, please refer to exact Lemmas/Theorems on which these claims are based.

POST-REBUTTAL:
Thank you for your answers. We've updated our scores, assuming you'll indeed follow-up as described in your rebuttal, including the promised plot.
strength_weakness: strength_weakness: There are several issues in the paper most of which can be easily fixed.  

- Definition of dispatchability.  

Dispatchability is first defined as the property of an STN, which states that a specific
algorithm always succeeds when applied to the STN, and then Th1 shows
that dispatchability is equivalent to the existence of shortest
vee-paths in the graph.  I think the authors should explicitly state
that they will use this characterisation of dispatchability as its
formal definition (it was unclear to me as I read the paper, and I was
constantly expecting a formal definition of dispatchability).
(This is especially true given that the definition of dispatchability of
an ESTNU (Def. 7) is based on properties of the graph and not on the
property of an algorithm.)

The solution to this issue might be as simple as first explaining the TD algorithm (lines 105 and next), and only after explaining that dispatchability is the property that the TD algorithm always succeeds.

- Did I understand correctly that the example of Fig. 1 is a structure that appears all the time in an STNU?  I assumed that it was an example used to introduce some notions; I now believe that it is essentially the only structure that will be encountered in the network (together with that of Figure 3) and that the only aspects of the figure that will differ in a real instance are the specific numbers that will be attached to each edge.

If I am correct, then I would like this to be made explicit.

Misc.

Line 26
"representating" -> representing

Line 52, I do not understand the sentence ``such a strategy requires
exponential space''.  Exponential in what?  Also, what would the
execution strategy look like?  I expect for instance that the execution
strategy might specify things like: ``x units of time after observing o,
execute action a'', but the `language' used to represent the execution
strategy might become more elaborate: ``You may execute action a in the
time interval [max(something,something),min(something,something)]''.
Do you have a good reference that explains what you have in mind?
What do you mean by "*exceedingly* impractical"?

The (citation omitted/blind review) references are very unfortunate.  I
understand (and appreciate) that the authors are worried that their
submission might not be accepted.  However, how am I supposed to do my
job as a reviewer if the references are not available?  If the work is
currently under review (which I assume is the case, because already
published stuff wouldn't be a problem here), it seems that the work is
done incrementally (publish a paper on the strategy, then publish a
paper on improving the representation).  Why not publish everything in a
single paper?

Line 65: ``presented an algorithm for creating an equivalent
dispatchable STNU, called FDSTNU .''  This sentence is weird.
``Equivalent'' to what?  Do you mean ``an algorithm that takes an STNU
and creates an equivalent dispatchable STNU?''

Definition 6, technically, $\omega_i$ is not defined.  What has been defined was $\omega_c$.  Maybe the notation before the definition should be amended.

Line 228, there is an implicit assumption that there cannot be
subset-minimal dispatchable ESTNU that are not cardinality-minimal ones
(for instance, there might be an input ESTNU with three edges {a,b,c}
such that the sub-ESTNUs {a,b} and {c} are dispatchable, and  none of
their proper sub-ESTNUs are).  I am willing to believe that this is
true, but it would be nice to see a discussion about that.
* From memory of the work on STNs, there can be multiple
cardinality-minimal dispatchable STNs.  For instance, one might have the
choice between keeping edge (a->c) and (a->b) if the label on these
edges is the same.

After Def. 8, it is worth explaining that maxd(V,Y) will be used to
prune the edge between V and Y.  I believe that this is the purpose of
the paragraph Line 242-247, but maxd(V,Y) is not mentionned in this
paragraph.

I believe it's worth explaining why the structures are nested.  Do I
understand correctly that the nested comes from the fact that the edge
A2 to A has a negative upper-case edge, and that there cannot be a
negative upper-case edge from A to A2 because there would then be a
negative cycle, hence inconsistency?

Definition 9, unless I missed it, I am not sure that $\le$ has been defined for edges.  I presume this means two edges over the same vertices but the distance of $e$ is smaller than that of $e'$.

Line 415, why isn't the complexity O(kn3 log n)?
questions: questions: - Definition 7 (Dispatchable ESTNU) defines dispatchability of a ESTNU as a property that is difficult to assess (it requires, at first glance, to verify the property of an infinite number of projections).  Is there a simpler (to verify) property similar to Theorem 1?

- Is my understanding correct that the structure of Figure 1 appears everywhere in the network?
strength_weakness: strength_weakness: - Limited contribution
- Experiments
- Organization and clarity
questions: questions: See review in the contribution of the paper section.