Variable-Delay Controllability

1 Introduction

In temporal planning problems, agents are required to find schedules for events that satisfy a set of predetermined constraints. This scheduling problem becomes more difficult when the duration of certain actions are outside of an agent's control (e.g. when driving to work, it is impossible to give a precise schedule because of the unpredictability of traffic).

When temporal planning problems include uncertainty, delay controllability checking provides a generalized way of determining the feasibility of the temporal plan, unifying the previous notions of strong and dynamic controllability [Bhargava et al., 2018]. Informally, under delay controllability, the main actor learns about the true duration of uncertain events after some amount of time has elapsed, and delay controllability assesses the feasibility of the temporal plan under different observation patterns.

While delay controllability gives us a rich language with which to model temporal planning in the face of uncertainty, it still has some fundamental limitations. In particular, it requires that an agent either learns the exact time that an event happens or learns nothing about the event. In contrast, there are many instances where some of the temporal ambiguity around an event is resolved after time passes even if it is impossible to learn its exact occurrence. For example, a human actor is unlikely to remember that they finished lunch at precisely 1:08pm several hours later, but they may be able to say that they finished lunch between 1:00pm and 1:15pm. Often, this partial reduction in uncertainty is both necessary and sufficient to ensure that the remaining constraints can be satisfied, but this uncertainty reduction might only happen well after the initial action occurred. Others have created models where the observation of events allows us to branch and consider distinct possible states [Moffitt and Pollack, 2007; Combi et al., 2013], but these models do not consider how to incorporate partial resolution of uncertainty in events that have already happened. In this paper, we focus on addressing this modeling gap and provide three main contributions.

First, we provide a formalism for modeling uncertain observations of events. We build our model and controllability checking algorithms on top of Simple Temporal Networks with Uncertainty [Vidal and Fargier, 1999] and for each action with uncertain duration, we provide a bounded interval representing the amount of time that may pass after an event occurs before an agent learns that it occurs.

Second, we provide an efficient algorithm for verifying that these networks are controllable under uncertain observation. We approach the problem by creating a parallel temporal network that is controllable with respect to some fixed observations if and only if our original network is controllable. If we let n be the number of events in our schedule and m be the number of constraints, we can apply this transformation in O(m+n) time, and since controllability checking under fixed observation can be performed in O(n3 ) time [Bhargava et al., 2018], we can similarly check variable-delay controllability in O(n3 ) time. Along with a controllability check, we also show how to derive an execution strategy for controllable networks with uncertain observations. The same approach used to assess the controllability of the network yields a new, less expressive network that is controllable with respect to some fixed-delay observations. We show how only a few modifications are needed to reduce our original execution problem to that of finding an execution strategy on the less expressive network.

Third and finally, we provide an empirical characterization of the quality of variable-delay controllability as contrasted against controllability checks that approximate the model using fixed delays. We show that the false positive rate is low but not zero, indicating that it is most appropriate to check variable-delay controllability directly.

Beyond temporal and observational uncertainty, many others have extended temporal networks and temporal network controllability checking to suit particular needs. Probabilistic Simple Temporal Networks ascribe probability distributions to the uncontrollable constraints of a network [Fang et al., 2014], and Conditional Simple Temporal Networks with Uncertainty allow for conditional execution and enforcement of constraints based on the observation of prespecified events [Combi et al., 2013]. When new temporal constraints are added one at a time to a network, iterative controllability checks show improvements over non-iterative solutions [Stedl and Williams, 2005; Shah et al., 2007; Nilsson et al., 2013; 2014], and when constraints are instead iteratively relaxed, RelaxIDC [Bhargava et al., 2017] gives us an algorithm that speeds up controllability checking over time.

Despite the many existing extensions to temporal networks and controllability checking, we argue that the ability to model, validate, and execute temporal networks under observational uncertainty represents a unique and significant improvement over state of the art. With previous temporal controllability formalisms, inference only flowed forward with time. Observations that happened in the future had no impact on our beliefs about past events. In contrast, our approach provides a rigorous means of incorporating future observations in our updated beliefs about past events. While others have worked on extending existing models to account for these relationships [Moffitt and Pollack, 2007; Moffitt, 2007; Bit-Monnot et al., 2016; Casanova et al., 2016], none have provided a sound and complete algorithm for verifying controllability in arbitrary networks.

2 Background &Definitions

In temporal planning, Simple Temporal Networks (STN) are composed of a set of events and simple binary constraints relating those events (e.g. event A must happen at least 20 minutes before event B) [Dechter et al., 1991]. STNs are useful for modeling problems where the agent can precisely schedule the timings of events, but they do not let us model actions whose durations are uncertain.

Simple Temporal Networks with Uncertainty (STNU) augment the STN allowing us to model these types of uncertain actions [Vidal and Fargier, 1999]. Events are subdivided into activated and received timepoints while constraints are subdivided into free and contingent constraints.

Definition 1. STNU [Vidal and Fargier, 1999]

An STNU is a 4-tuple 〈Xb, Xe, Rc, Rg〉 where:

• Xb is the set of activated timepoints
• Xe is the set of received timepoints
• Rc is the set of free constraints of the form lc ≤ xi - xj ≤ uc, where xi, xj ∈ Xb ∪ Xe
• Rg is the set of contingent constraints of the form lg ≤ ei - bj ≤ ug, where ei ∈ Xe, bj ∈ Xb

Activated timepoints represent events whose values are explicitly scheduled by the main agent while received timepoints are assigned values by some external actor. Free constraints behave like ordinary STNU constraints while contingent constraints represent actions with values of uncertain duration. Contingent constraints always begin with an activated timepoint, representing an initiated action, and end with a received timepoint.

Since an STNU has events whose occurrences are outside of an agent's control, to assess the feasibility of an STNU, we examine its delay controllability to determine whether a valid schedule can be constructed given a guarantee that future uncertainty will eventually be fully resolved [Bhargava et al., 2018]. In the rest of this paper, we will refer to the original notion of delay controllability as fixed-delay controllability for clarity.

Fixed-delay controllability uses a fixed-delay function to parameterize controllability. The fixed-delay function encodes the amount of time that must pass before we observe a received timepoint when constructing our schedule.

Definition 2. Fixed-Delay Function [Bhargava et al., 2018] A fixed delay function, γ : Xe → R+ ∪ {∞} maps from received timepoints to the amount of time that must pass before that timepoint is observed.

Definition 3. Fixed-Delay Controllability [Bhargava et al., 2018]

An STNU is fixed-delay controllable with respect to some delay function γ if it is possible for an agent to reactively execute a plan if they learn the true value of received timepoint e only after an additional γ(e) time has passed.

Importantly, fixed-delay controllability generalizes other notions of controllability. For example, by using a fixed-delay function where we observe all timepoints, checking fixeddelay controllability reduces to checking dynamic controllability. Similarly, a fixed-delay function specifying that we never observe any received timepoints corresponds to checking strong controllability [Vidal and Fargier, 1999].

As a matter of convention, we will use A -→ B to represent requirement links between timepoints A and B and will use A =⇒ E to represent contingent links between A and E. When we talk about the delay function associated with the received timepoint E of some contingent link A =⇒ E, we will use the notation γ(e).

2.1 Variable-Delay Controllability

While fixed-delay controllability is quite expressive, its fundamental limitation is that events must be observed only after a fixed offset. If there were some uncertainty in our observation event, the controllability problem becomes much harder, as we now only have rough bounds around when an event in the past happened rather than ground truth. We now rigorously introduce the notions of a variable-delay function and variable-delay controllability.

Definition 4. Variable-Delay Function

A variable-delay function, ¯ γ : Xe → (R+ ∪ {∞}) × (R+ ∪

{∞}), takes a received timepoint and outputs an interval [a, b]. The range bounds the least amount of time and most amount of time that may pass after the assignment of a value to the received timepoint before a value is known to be assigned. By convention, we use ¯ γ-(e) to represent the lowerbound in observation and ¯ γ+(e) to represent the upper-bound.

Definition 5. Fixed Delay Set

We say F(¯ γ) represents the set of all possible fixed-delay functions that are valid groundings of the variable-delay function ¯ γ. In other words, ∀γ ∈ F(¯ γ), ∀e ∈ Xe : γ(e) ∈ [¯ γ-(e), ¯ γ+(e)].

Definition 6. Possible Observed Situations

Let Ω be the set of all possible sets of assignments of durations to contingent links, let δ : Xb → R be a partially committed schedule for activated timepoints, let ω ∈ Ω be the actual assignment of durations to contingent links, let ¯ γ be the variable-delay function, and let γ ∈ F(¯ γ) be the actual observational delay. The set of all possibly observed situations before t with respect to some δ, ω, ¯ γ, γ is Ω<t,δ,ω,¯ γ,γ = {ω′ ∈ Ω : p(ω, ω′ , δ, t, ¯ γ, γ) ∧ q(ω, ω′ , δ, t, ¯ γ, γ)}, where:

• p(ω, ω′ , δ, t, ¯ γ, γ) = ∧ωij∈ω (δ(bi) + ωij + γ(ej ) > t) → (δ(bi) + ω′ij + ¯ γ+(ej) > t); or for any event that has not yet been seen, it is possible to have not yet seen that event in ω′ .
• q(ω, ω′ , δ, t, ¯ γ, γ) = ∧ωij∈ω (δ(bi) + ωij + γ(ej ) ≤ t) → (γ(ej) +ωij -ω′ij ∈ ¯ γ(ej)); or for any event that has been seen, it must be possible to see that event at the same moment in ω′ .

Definition 7. Variable-Delay Controllability

For any δ, let δ<t,δ represent a restriction on the set of assignments δ, where δ<t,δ only contains assignments for events that happen before time t. An STNU S is variable-delay controllable with respect to some variable-delay function ¯ γ if and only if: ∀ω ∈ Ω, ∀γ ∈ F(¯ γ), there exists an assignment δ, such that ∀(x, t) ∈ δ, ∀ω′ ∈ Ω<t,δ,ω,¯ γ,γ, there exists δ′ , such that δ<t,δ ⊆ δ′ and δ′ is an assignment that satisfies Sω′ .

In other words, an STNU is variable-delay controllable with respect to some variable-delay function ¯ γ if it is always possible to construct a satisfying plan for the future given the inferences that have been made about events that have already been observed.

It is clear that variable-delay controllability is a generalization of fixed-delay controllability. For any fixed-delay function γ, we can produce a corresponding variable-delay function ¯ γ where ¯ γ+(e) = ¯ γ-(e) = γ(e).

3 Determining Controllability

Our strategy for determining whether a given STNU S is variable-delay controllable with respect to ¯ γ is to instead construct a related STNU S′ that is fixed-delay controllable with respect to some derived delay function γ ′ .

It is important to note that we do not expect S′ and γ ′ to be expressive enough to model our original problem. Because our focus is on checking the controllability of our problem, it suffices for us to focus on the worst-case areas of our problem, or the situations that are hardest to schedule, and we construct S′ and γ ′ with that end in mind.

To construct S′ and γ ′ , we start by copying the original graph S. We then make a series of iterative modifications to our new outputs so that they capture the controllability of our original input. We start by updating our definition of γ ′ based on observed values of ¯ γ.

Lemma 1. For any received timepoint e ∈ Xe in S, if ¯ γ-(e) = ¯ γ+(e), we can express the same behavior in S′ using γ ′ (e) = ¯ γ+(e).

Proof. If ¯ γ-(e) = ¯ γ+(e), then ¯ γ already emulates a fixeddelay for timepoint e. Assigning γ ′ (e) = ¯ γ+(e) makes no change to the proposed controllability since the modified S′ and γ ′ cover the same scenarios as S and ¯ γ.

Lemma 2. If for some e ∈ Xe, ¯ γ+(e) = ∞, we can express the same behavior in S′ using γ ′ (e) = ∞

Proof. If ¯ γ+(e) = ∞, then in some scenarios, e is unobservable in S. It does not matter that in some instances we may learn about e after some delay; controllability checking is about verifying that a valid execution strategy exists in all scenarios. Thus, if we can verify that S′ is controllable when e is unobservable (when γ ′ (e) = ∞), then we know that S is controllable whenever e is observed after t ∈ ¯ γ(e) since a valid execution strategy could always choose to ignore the observation. If S′ is uncontrollable when γ ′ (e) = ∞, then we also similarly know that we would not be able to find a valid execution strategy if e ended up unobservable in S.

After repeated applications of Lemmas 1 and 2, we are left with a series of received timepoints whose variable-delay function values represent finite ranges. Since the delay in observation is an uncertain and uncontrollable duration, a naive attempt at transforming the model would be to model observation itself as a contingent link (Figures 1a, 1b). This structure better equips us to reason about the controllability and execution of our original problem, but it is important to realize that this structure is not a valid STNU. In an STNU, all contingent links are required to start at an activated timepoint, whereas this transformation lets a contingent link start at a received timepoint. Nonetheless, while normal STNU algorithms may fail on this structure, we can still leverage it to better understand how to reason about variable-delay execution.

Under this new transformation, the next question we consider is how much information the observation of ¯ γ gives us in the worst case. Let [a, b] be the bounds of the contingent link X =⇒ E. There are two ways to handle these contingent links based on how the uncertainty of the observation compares to the uncertainty of the original link.

Lemma 3. If b - a ≤ ¯ γ+(e) - ¯ γ-(e), we can express the same behavior in S′ using γ ′ (e) = ∞.

Proof. In this situation, there is at least as much uncertainty in the observation of the event as there is in the occurrence of the event, meaning we have no guarantee of receiving any meaningful information after observing that the event happened. Consider the worst-case scenario where we learn that e happened a + ¯ γ+(e) after the starting activated timepoint. It is clear that the original contingent link could have taken on a value of a given this information, but because a + ¯ γ+(e) - b ≥ ¯ γ-(e), we also know that the original link could have had a value of b and thus been anywhere in [a, b]. Since ¯ γ is not guaranteed to give us any information in this instance, in our derived STNU S′ , we can let γ ′ (e) = ∞.

We do not make controllability checking or network execution any harder by going from a highly uncertain observation to no observation at all. We always know the starting time of the original contingent link, as we choose it ourself, meaning we still have our original coarse bounds [a, b] on when the event occurs.

Lemma 4. If b - a > ¯ γ+(e) - ¯ γ-(e), we can replace the bounds of the original link ending at e with [a + ¯ γ+(e), b + ¯ γ-(e)].

Proof. If b - a > ¯ γ+(e) - ¯ γ-(e), we can take our original contingent link with range [a, b] and variable-delay ¯ γ(e), and in S′ we can transform it into a contingent link [a+¯ γ+(e), b+ ¯ γ-(e)] with γ ′ (e) = 0 (see contingent link across Figures 1a, 1b, 1d), folding some of the uncertainty in observing e directly into the contingent link.

It is important to notice that the range of the modified contingent link is shorter than the range of possible times at which we would actually notice the occurrence of e, [a + ¯ γ-(e), b + ¯ γ+(e)]. Here again, we rely on the notion that we are only interested in capturing the worst-case scenario. Imagine that we observed e at some time a+¯ γ+(e)-ϵ where 0 < ϵ ≤ ¯ γ+(e). We know that the original link occurred at a lower-bound of a and that it has an upper-bound of a+(¯ γ+(e)-¯ γ-(e))-ϵ. In contrast, with an observation at a + ¯ γ+(e), we have a strictly larger range of possible options for the original contingent link, meaning our restriction does not make the scheduling problem less constrained.

We can make the same argument for the upper-bound. If we observe e at some b + ¯ γ-(e) + ϵ, then we have an upperbound of b and a lower-bound of b - (¯ γ+(e) - ¯ γ-(e)) + ϵ. When we instead observe e at b + ¯ γ-(e), we have the same upper-bound but a smaller lower-bound at b - (¯ γ+(e) - ¯ γ-(e)), meaning the range of possible options is strictly larger. This means that our modified contingent link with γ ′ (e) = 0 fully captures the worst-case scenarios for e with our original S and ¯ γ.

What remains is to demonstrate how to transform the requirement links attached to e such that they represent the original execution semantics of S. To validate that this is the case, we first examine what local execution semantics look like in a variable-delay temporal network (Figures 1b, 1c).

Lemma 5. If we have contingent link X =⇒E with duration [a, b], outgoing requirement link E -→ Z with duration [u, v] with an unobservable E, and contingent link E =⇒ Y with range [¯ γ-, ¯ γ+], we can replace the original requirement link during execution with a new link Y -→ Z with bounds [u - max(¯ γ-, XY - b), v - min(¯ γ+,XY - a)], where XY is the true duration of X =⇒ Y . See Figure 1c for reference.

Proof. From an execution perspective, X and Y are the only events that can give us any information that we can use to reason about when to execute Z (since E is wholly unobservable).

If we execute Z based on what we learn from Y , then we use our information from Y to make inferences about the true durations of X =⇒ E and E =⇒ Y based on X =⇒ Y . We know that the lower-bound of E =⇒ Y is at least XY - b and that its upper-bound is at most XY - a. But we also have the a priori bounds on the contingent link that limit its range to [¯ γ-, ¯ γ+]. Taken together, during execution we can infer that the true bounds of E =⇒ Y are [max(¯ γ-,XY - b),min(¯ γ+,XY - a)]. Since we have bounds only on Z's execution in relation to E, we can then infer a requirement link Y -→ Z with bounds [u - max(¯ γ-, XY - b), v - min(¯ γ-, XY - a)].

If we try to execute Z based on information we have from X, we must be robust to any possible value assigned to X =⇒ E. This means that we would be forced to draw a requirement link X -→ Z with bounds [u + b, v + a]. But we know that u-max(¯ γ-, XY -b) ≤ u+b-XY and v-min(¯ γ-, XY - a) ≥ v + a - XY , which means that the bounds we derived from Y are at least as expressive as the bounds that we would derive fromX.

Since we have a local execution strategy that depends on the real value of XY , we can try to apply that strategy to the contingent link we restricted in Lemma 4 to repair the remaining requirement links.

Lemma 6. If we have an outgoing requirement link E -→ Z with duration [u, v] where E is a received timepoint, we can replace the bounds of the original requirement link with [u - ¯ γ-, v - ¯ γ+]. See Figure 1d for reference.

Proof. If we directly apply the transformation from Figure 1c to our original STNU, we introduce a new complexity in the form of reasoning over min and max operations in our link bounds. However, from Lemma 4, we know that in a controllability evaluation context, it is acceptable for us to have the X =⇒ Y link take on stricter range [a + ¯ γ+, b + ¯ γ-] instead of [a+ ¯ γ-, b + ¯ γ+], meaning for the purposes of evaluating controllability, we can assume a + ¯ γ+ ≤ XY ≤ b + ¯ γ-. When we evaluate the requirement link Y -→ Z, max(¯ γ-,XY - b) = ¯ γ- and min(¯ γ+,XY - a) = ¯ γ+. This gives us the bounds for the requirement link that we see in Figure 1d.

Lemma 6 handles outgoing requirement edges connected to received timepoints, but we also must handle incoming edges.

Corollary 6.1. If we have an incoming requirement link Z -→ E with duration [u, v] where E is a received timepoint, we can replace the bounds of the original requirement link with [u + ¯ γ+, v + ¯ γ-].

Proof. A requirement link Z -→ E with bounds [u, v] can be immediately rewritten as its reverse E -→ Z with bounds [-v, -u]. After reversing the edge, we can apply Lemma 6 to Input: STNU S; variable-delay function ¯ γ Output: An STNU S′ and fixed-delay function γ ′

Initialization: 1 S′ ←S.copy(); 2 γ ′ ← {}; CONVERTTOFIXEDDELAY: 3 for l ∈ S′ .contingentLinks() do 4 e ← l.endpoint(); 5 a, b ← l.bounds(); 6 if ¯ γ+(e) == ∞ or ¯ γ+(e) == ¯ γ-(e) then 7 γ ′ (e) ← ¯ γ+(e); 8 else if b - a ≤ ¯ γ+(e) - ¯ γ-(e) then 9 γ ′ (e) ← ∞; 10 else 11 e ← l.endpoint(); 12 a, b ← l.bounds(); 13 l.setBounds(a + ¯ γ+(e), b + ¯ γ-(e)); 14 γ ′ (e) ← 0; 15 for l′ ∈ e.outgoingReqLinks() do 16 u, v ← l′ .bounds(); 17 l′ .setBounds(u - ¯ γ-(e), v - ¯ γ+(e)); 18 for l′ ∈ e.incomingReqLinks() do 19 u, v ← l′ .bounds(); 20 l′ .setBounds(u + ¯ γ+(e), v + ¯ γ-(e)); 21 return S′ , γ ′

Now we put it all together and introduce Algorithm 1 as a complete algorithm for transforming an STNU S and variable-delay function ¯ γ into a corresponding STNU S′ and fixed-delay function γ ′ , where S is variable-delay controllable if and only if S′ is fixed-delay controllable.

Theorem 7. We can convert a variable-delay controllability problem into a corresponding fixed-delay controllability problem in O(m + n).

Proof. Initially in Algorithm 1 (lines 6-7), we handle Lemmas 1 and 2. Next, we check the condition set forth by Lemma 3 (lines 8-9) to see if in the worst-case the observation would fail to give us new information.

Finally, in the remaining part of the algorithm (lines 1020), we transform all other contingent links and the requirement links that are associated with them. At line 13, we apply the transformation as specified by Lemma 4. At lines 15-20, we ensure that all outgoing and incoming requirement links are updated as specified in Lemma 6 and Corollary 6.1.

Overall, the transformation is efficient, running in linear time. Let n be the total number of timepoints and let m be the total number of constraints in an STNU. There are at most O(n) contingent links, meaning the operations spanning lines 4-14 are applied at most O(n) times. For each requirement link in S′ , we modify its bounds at most once as an outgoing link (lines 15-17) and once as an incoming link (lines 18-20).

This means that lines 15-20 are executed at most O(m) times, meaning the total runtime is O(m+n).

Since we can convert any variable-delay controllability problem into an equivalent-valued fixed-delay controllability problem, we can use fixed-delay controllability checkers to assess the variable-delay controllability of an STNU after transformation.

Theorem 8. Variable-delay controllability can be evaluated in O(n3 ) time.

Proof. Since the transformation takes O(m+n) time without changing the size of the output STNU and fixed-delay controllability checking takes O(n3 ) [Bhargava et al., 2018], the result is an O(n3 ) way to check variable-delay controllability for any STNU since m ≤ n2 .

4 Variable-Delay Execution

Our algorithmic transformation gives us an efficient way to determine whether an STNU is variable-delay controllable but the resulting transformation does not give us an execution strategy for our STNU.

Intuitively, we want to use the resulting STNU from our fixed-delay transformation to guide execution but we face some limitations. To simplify our controllability checking, we restricted the ranges of many of our contingent links. If we tried to execute the resulting STNU, we would likely encounter a violation since it is possible for the world to violate the invariants of our STNU - namely that nature will respect the bounds of all contingent links. However, this problem is not insurmountable. We can use our transformed STNU as a guide for execution but amend our execution semantics slightly to account for these slight discrepancies.

Theorem 9. Deriving an execution strategy for a variabledelay controllability problem reduces to finding an execution strategy for a fixed-delay controllability problem.

Proof. The problem lies in a few contingent links that in the transformed STNU have bounds [a + ¯ γ+, b + ¯ γ-] but in the original STNU have implicit bounds of [a+¯ γ-, b+¯ γ+]. The reason we were allowed to restrict these bounds is that the execution of other actions in the STNU were not dependent on the endpoint of this longer contingent link but rather on some other contingent link that had bounds [a, b]. In the restricted case, we always had less information about the true duration of the original contingent link, despite the fact that the range itself was smaller.

Armed with this knowledge, the remedy for our execution strategy is relatively straightforward. We follow the normal fixed-delay execution strategy for our derived STNU but with two exceptions. First, if the true duration of a contingent link is less than a + ¯ γ+, we buffer the response and act as if the duration was actually a + ¯ γ+. It is clear that waiting gives us no extra information.

Second, if more than b+¯ γ- time has passed and the contingent link has not reached completion, we act as if it actually reached completion at b + ¯ γ-. We can safely assume the earlier completion time because of the information it gives us. When b+¯ γ- time passes, the value of the original contingent link is somewhere in [b - (¯ γ+ - ¯ γ-), b]. If we were to learn about the value at a later moment, b+¯ γ- +ϵ, then the value of the original contingent link would be in [b+ϵ-(¯ γ+ - ¯ γ-), b], which is strictly tighter. Thus, if we assume an earlier completion time, we give ourselves a strictly harder problem, but we know it is still controllable because this still maps to our corresponding fixed-delay controllability problem.

These changes restrict the information we can learn about the original [a, b] link, but since the system is still controllable with this restriction, our execution strategy remains valid. Thus, finding an execution strategy for an STNU with variable-delay function reduces to finding an execution strategy for an STNU with a fixed-delay function.

5 Empirical Evaluation

The introduction of variable-delay controllability gives us a level of expressiveness that we previously lacked. In this section, we attempt to characterize the gap in expressivity by showing how attempts to evaluate variable-delay problems using fixed-delay approximations lead to incorrect results.

To evaluate the comparative quality of the different approaches, we constructed a set of randomly generated STNUs. Each STNU had 10 contingent links with lowerbound 0 and an integer upper-bound uniformly chosen between 1 and 4. Each contingent link had a variable-delay function with a lower-bound of 0 and upper-bound chosen from the exponential distribution f (t) = λe-λt with λ = 0.5. For each pair of contingent link endpoints, we established a requirement link between themwith probability 1 40 . Each requirement link had a lower-bound of 0 and an integer upperbound uniformly chosen between 1 and 4. We chose these parameters because they represent a reasonable trade-off between simplicity in degenerate cases and sufficient complexity to exhibit interesting behaviors. Moving forward, we hope to validate our approach against real-world examples that demonstrate both temporal and observational uncertainty.

We employed three different strategies for our fixed-delay approximations: γ(xe) = ¯ γ-(xe), γ(xe) = ¯ γ-+¯ γ+ 2 , and γ(xe) = ¯ γ+(xe). For each strategy, we know that whenever the original STNU is variable-delay controllable with respect to ¯ γ, it is also fixed-delay controllable with respect to γ. Each choice of γ represents a potential realization of the delays offered by ¯ γ, and the fixed-delay approximation has the added benefit of eliminating uncertainty in observation.

We generated 1000 different STNUs and compared the variable-delay controllability results to the different fixeddelay controllability approaches (Table 1). The instances that are of greatest interest are those where the STNU is not variable-delay controllable but the fixed-delay approximations determines it to be controllable.

The false positive rate of the minimum fixed-delay controllability approximation is quite high at 39%, but the mean and maximum fixed-delay approximations have more reasonable false positive rates at 4.5% and 3.0% respectively. Since all approximations yield the correct answer when the original STNU is variable-delay controllable, it makes sense that the maximum fixed-delay approximation has the lowest false positive rate, as it is the most demanding of the three.

We note that these results are also dependent on the width of the variable-delay ranges found in the network. We can simulate increasing the likelihood that a delay takes on a larger value by decreasing the choice of λ in our exponential delay function. When we vary our delay function using λ = 0.5, 0.1, 0.05, 0.01, the false positives of the max-delay approximation are 3.0%, 3.4%, 3.9%, 5.2%. As expected, this indicates that as the uncertainty of our bounds grows, there is an increasing advantage, from a correctness perspective, to using variable-delay controllability.

6 Conclusion

In this paper, we introduce variable-delay controllability as an extension to fixed-delay controllability over STNUs. We provide a formal definition showing how it generalizes fixeddelay controllability while also providing an efficient sound and complete algorithm for determining the variable-delay controllability of an STNU. Because variable-delay controllability execution reduces to fixed-delay controllability execution, we are able to demonstrate that variable-delay controllability is a formalism that can be used in practice to construct and evaluate schedules in the face of both temporal and observational uncertainty.

Acknowledgments

This research was funded in part by the Toyota Research Institute under grant number LP-C000765-SR.