--- title: "Robustness Computation of Dynamic Controllability in Probabilistic Temporal Networks with Ordinary Distributions" authors: - "Michael Saint-Guillain" - "Tiago Stegun Vaquero" - "Jagriti Agrawal" - "Steve Chien" doi: "10.24963/ijcai.2020/576" url: "https://ijcai.org/proceedings/2020/576" pdf: "https://ijcai.org/proceedings/2020/0576.pdf" venue: "Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence" year: 2020 pages: "4168-4175" track: "Main track" keywords: - "Planning and Scheduling: Robot Planning" - "Planning and Scheduling: Temporal and Hybrid planning" - "Planning and Scheduling: Planning under Uncertainty" --- # Robustness Computation of Dynamic Controllability in Probabilistic Temporal Networks with Ordinary Distributions Michael Saint-Guillain, Tiago Stegun Vaquero, Jagriti Agrawal, Steve Chien *Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence*, pages 4168-4175. DOI: [10.24963/ijcai.2020/576](https://doi.org/10.24963/ijcai.2020/576) ## Abstract Most existing works in Probabilistic Simple Temporal Networks (PSTNs) base their frameworks on well-defined probability distributions. This paper addresses on PSTN Dynamic Controllability (DC) robustness measure, i.e. the execution success probability of a network under dynamic control. We consider PSTNs where the probability distributions of the contingent edges are ordinary distributed (e.g. non-parametric, non-symmetric). We introduce the concepts of dispatching protocol (DP) as well as DP-robustness, the probability of success under a predefined dynamic policy. We propose a fixed-parameter pseudo-polynomial time algorithm to compute the exact DP-robustness of any PSTN under NextFirst protocol, and apply to various PSTN datasets, including the real case of planetary exploration in the context of the Mars 2020 rover, and propose an original structural analysis. ## Full text ## 1 Introduction Temporal networks formalize the arrangement and interdependencies of tasks, or activities, that compose an operational project. In a simple temporal network (STN), activities are modeled as a finite set of time events. In practice, some activity durations, considered as contingent, remains unknown beforehand. In the case some stochastic knowledge on the uncertain durations exists, then one can model it as (estimated) probability distributions, leading to the extending concept of probabilistic STN, or PSTN. Solving a STN then amounts at finding an assignment of time values to events that fulfils all the constraints between events. Whenever such schedule exists, a network is said to be controllable. When the operational assumptions enable it, the schedule may be dynamically constructed, the time values being assigned as durations are observed. Yet, even under dynamic decision, due to unfortunate durations a network may reveal uncontrollable. How likely is a PSTN to lead to a successful execution? Provided some stochastic knowledge on contingent activity durations, the degree of dynamic controllability (DDC) of a PSTN can be quantified, as the success probability of a given task network. The current literature proposes DDC computation methods for PSTNs that involve unimodal distributions only (uniform or normal), or exploit Monte Carlo simulation, which admits ordinary distributions. On both cases, the computed DDC values are approximations only, without guarantee on the true robustness of the network. ∗Contact Author Figure 1: A simplified hypothetical sol on Mars for two planetary rovers, encoded as a PSTN. Bold: controllable. Dashed: contingent. ![Image](https://ijcai.org/proceedings/2020/fulltext/576/image_000000_814d219d34d87d5f217d4fbad5638cd4a013e7214df1384cdf9cce4fb5c87152.png) Contributions. We propose the first efficient DDC (aka. robustness) computation method capable of dealing with PSTNs with any possible ordinary probability distributions (i.e. non-parametric, non-symmetric, multi-modal, or even hand-made). Our method computes a valid lower bound on the exact DDC of a PSTN. Under a specific dispatching protocol, it computes the exact execution success probability. Furthermore, it enables to compute a lower bound on each task's own success probability within that network, which can be mapped to activity temporal brittleness. On the application side, we propose a new method for identifying structural bottlenecks in temporal brittleness analysis, applied to the real case study of the Mars 2020 rover's task networks. ## 2 Temporal Networks STN. Simple Temporal Network is a popular formalism for temporal constraint reasoning [Dechter et al., 1991], framed as a constraint satisfaction problem over time point variables: a STN is a tuple 〈T,C〉, where T is a set of time points (ti ∈ T ⊆ IR) and C is a set of constraints c(ti, tj) that encode bounds on the differences between pairs of time points: lij ≤ (tj - ti) ≤ uij, i.e. (tj - ti) ∈ [lij, uij]. A solution is called a schedule, a specific assignment to all ti ∈ T. Constraint c(ti, tj) represents the valid bounds for the duration of an activity defined by time points (ti, tj), whereas tj - ti gives the activity duration set up by a specific schedule. Probabilistic STN. Most realistic operational contexts account for temporal uncertainty. PSTN is a natural extension of STN in which probability density functions are associated to activity durations [Tsamardinos, 2002]. The PSTN formalism partitions both sets T and C as T = TE ∪ TC, where executable time points TE are determined by the agent, and contingent time points TC are assigned by nature. The constraints set is C = CR ∪ CC where: requirement edges, CR, are controlled by the agent; and contingent edges, CC, are determined by nature, each element being described as a probability distribution (tj -ti) = Xi,j . A schedule assigns values to executable time points only. The duration (tj - ti) associated to any contingent time point tj remains unknown prior to execution. In absence of stochastic knowledge for a contingent duration (tj - ti), a common usage is to consider it uniform: Xij ∼ U(lij, uij). A temporal network in which that assumption applies to all its contingent edges is called a STN with Uncertainty: STNU [Vidal and Ghallab, 1996]. Illustrative example: rover operations. An hypothetical example of Mars rovers PSTN is depicted in Fig. 1. Each rover has three activities in sequence: drive towards a science site, experiment, and relay results to an orbiter. A special time point t0 = 0 represents the beginning of the operations. Time events are linked by temporal constraints, either controllable or contingent. In our example, the rovers work independently during their driving and science activities. They do not coordinate until the communication time window, which strictly happens between time 600 to 700. Communication tasks cannot overlap, and Rover1 is chosen to relay first. However, duration of driving and experimental activities are highly uncertain. In practice, distributions can be estimated from historical observations. Even an inaccurate stochastic knowledge, e.g. obtained accurate observations, leads to valuable results in practice (as illustrated in [Saint-Guillain, 2019] for Marsinspired operations). In Fig. 1, distribution X1,2 describes the stochastic duration of driving activity (t1, t2), encoded in the PSTN as a contingent constraint c(t1, t2) ∈ CC, t2 ∈ TC. ## 3 Robustness Ideally, a perfect assignment of all time points in TE would work for any situation imposed by nature. In practice that is very restrictive, if not impossible. Instead, we refer to a strategy mapping observations to schedules during execution. In fact, if the PSTN of Fig. 1 involves some probability distribution with unbounded tail, then such perfect schedule does not exist. Under uncertain activity durations, how likely is the execution of a PSTN to succeed? What is the probability that our rovers get their relay activities (≥20 long for Rover1, ≥30 long for Rover2) during the communication window? ## 3.1 Controllability In STNU and PSTN realm, consistency is not directly applied due to the unpredictable assignment of contingent time points and edges. A PSTN relies instead on checking controllability, which verifies whether an agent can generate a consistent schedule to any situation that may arise in the external world. Controllability theory is usually applied to STNUs, but can also be applied to more general PSTNs (distributions being not restricted to uniform ones), at specific different levels. An PSTN is said to be strongly controllable (SC) [Vidal and Ghallab, 1996] iff there exists at least one strong schedule (a.k.a. static schedule), i.e. a "universal" schedule that fits any situation, guaranteed to satisfy all temporal constraints regardless of the nature's assignments. That is motivated by cases where agents have to compute a schedule offline before making any observations, with no opportunity to adapt online. Nevertheless, in practice a valid static schedule is rarely available in dynamic and unpredictable environments. A more practical level would be dynamically controllable (DC) [Morris et al., 2001; Morris, 2014], in which we check whether there exists an execution strategy such that, at any time during execution, the partial sequence executed so far extends to a complete solution, whatever durations remain to be observed. It requires the agent to be able to determine, in a dynamic fashion, a valid assignment of executable time points based on observed past contingent ones, without violating any future temporal constraints. ## 3.2 Degrees of Dynamic Controllability Whereas controllability checking has been proven polynomial in many cases [Bhargava and Williams, 2019], evaluating the degree of controllability of uncontrollable networks is still an open problem. In [Akmal et al., 2019], the degree of dynamic controllability (DDC) of a STNU is introduced. When considering uniform distributions only, the DDC is defined as the proportion of contingent edges realizations in which the temporal network remains dynamically controllable. In the context of a PSTN, the DDC must rather be defined in terms of the probability mass of the controllable realization space. That definition of DDC is equivalent to the robustness measure, independently introduced in [Brooks et al., 2015], as the probability of the network to be successfully executed under dynamic control. Assuming discrete distributions: where Ω is the set of all possible realizations of the random contingent edges' duration. The deterministic function Φ(N, ξ) takes value 1 iff the network N is dynamic controllable in scenario (a.k.a. situation) ξ. In fact, in both cases and given scenario ξ, a PSTN reduces to a regular STN, as the contingent edges get assigned fixed durations. Whereas Φ(N, ξ) can be checked in linear time, the computation of (1) is intractable in practice, as the size of Ω grows exponentially with the number of contingent edges. ## 3.3 Dispatching Protocols Operational contexts such as space missions usually forbid recomputing a schedule in the middle of the operations [Chi et al., 2019]. Yet, the use of a static schedule is often either impossible in practice, or comes with a significant waste in terms of operational time. Such approach is currently operating Curiosity rover, with static schedules that overestimate processing times by 30% in average [Gaines et al., 2016]. Future planetary rover M2020 will be equipped with a nonbacktracking onboard scheduler, designed to take online decisions based on current observations [Agrawal et al., 2019; Chi et al., 2018; Rabideau and Benowitz, 2017]. However, because of computational limitations, such online decisions must remain very light, thus following a predefined strategy: a dispatching protocol (DP). We derive the concept of DP from that of recourse strategy [Birge and Louveaux, 2011]. Given the state at time t and new observation ξ t , a DP function returns an assignment of (a subset of) the n remaining executable time points: We distinguish three families of DP's, depending on the complexity of DP(·). First, the case where DP(·) is constant time directly corresponds to a static/strong schedule. Second, the case of non-polynomial time functions generally stands for an online reoptimization process, aimed at solving the inherent multistage stochastic program. In that case, there is no predefined strategy, a new scheduling problem is solved at each time step, regardless the computational expense. Finally, the case of a (non-constant) polynomial-time DP(·) allows agents to dynamically adapt the schedule, while being computationally limited. For example, Rabideau and Benowitz [2017] describe a O(n2 ) quadratic DP(·) protocol to be computed by the future M2020 onboard scheduler, in order to make online decisions based on observations and pre-optimized parameters [Chi et al., 2019]. Brooks et al. [2015] consider a linear time protocol, called NextFirst protocol, which we further describe below. DP-Robustness. Most of existing work in the literature aims at computing the DDC in (1). Yet, one may be interested in the success probability of a network N under a specific dynamic dispatching protocol P, the DP-robustness: where ΦP (N, ξ) returns 1 iff following protocol P in situation ξ leads to a successful execution. Given a dispatching protocol P, the DP-robustness necessarily constitutes a lower bound on the true DDC of a network: It is worth noting that in many operational contexts, under computationally limited settings (e.g. Mars 2020 rover), a DP-robustness measure based on an appropriate protocol may be more adequate than the DDC, as the latter relies on optimal online re-scheduling, which is intractable in general. NextFirst dispatching protocol. The NextFirst protocol [Brooks et al., 2015], also known as DC-dispatch [Morris et al., 2001], achieves a O(n) linear time dynamic control by starting activities as soon as possible. Let tj be a controllable time point in a PSTN, and Ij = {(0, j), . . . , (i, j)} the set of incoming edges in tj. We assume Ij to contain controllable edges only, which one can easily enforce as shown in Fig. 2(b). Therefore, tj is assigned a time value as soon as all the preconditions are validated, that is, all the t0, . . . , ti time points are known: Figure 2: (a) An example of NextFirst incompleteness on a basic STN. (b) The network can be transformed in order to avoid synchronisation points involving contingent incoming edge(s). ![Image](https://ijcai.org/proceedings/2020/fulltext/576/image_000001_9d208f6976752d43aad0913b2129f454bfb8db9252f3ed6744736d53ef384ee9.png) Table 1: Existing DDC measurement methods. The key properties we consider are 1) Quality of the computed value: lower bound (≤) on DDC, approximation (≃) of DDC, and 2) Properties of the supported probability distributions: Uniform, Normal, any ordinary distribution, and finally whether distributions can be continuous). | | Comp. value - ≤ | Comp. value - ≃ | Prob. distribution - ∼U | Prob. distribution - ∼N | Prob. distribution - All | Prob. distribution - Cont. | |-------------------------------------------------------------|-------------------|-------------------|---------------------------|---------------------------|----------------------------|------------------------------| | Monte Carlo [Akmal et al., 2019] [Cui et al., 2015] et al., | | ✓ ✓ | ✓ ✓ ✓ | ✓ | ✓ | ✓ ✓ ✓ ✓ | | | | ✓ ✓ | ✓ | ✓ | | | | [Vaquero 2019] [Cesta et al., 1998] [Wilson et al., 2014] | | ✓ ✓ | ✓ ✓ | | | | | [Saint-Guillain, 2019] Our proposal | ✓ | ✓ ✓ | ✓ ✓ | ✓ ✓ | ✓ ✓ | | In the case tj >min(t0+u0j, . . . , ti+uij), the dynamic execution is considered as failed, and is interrupted. Back to our PSTN example in Fig. 1, the value of t11 is then dynamically set to max(t10, t6 + 5) as soon as tasks Rover2:expe and Rover1:relay are completed. Execution fails if t11 exceeds t6 + 10. Eventually, we hope for t13 ≤ 700. Incompleteness of NextFirst. The simplicity of NextFirst enables efficient DP-robustness computation, but comes at the expense of being incomplete. A more clever dispatching protocol assigns a time value based not only on past time events, but also remaining ones. Fig. 2(a) shows an example of a basic (deterministic) STN, for which operating t1 as soon as possible, following (3), leads to a failure. ## 4 Landscape of Robustness Measures Table 1 summarizes the existing contributions on computing (or approximating) the DDC of a network. Recent studies, such as [Cui and Haslum, 2019], focus on computing valid dynamic decisions for dynamically controllable networks, whereas we focus on uncontrollable PSTNs. Finally, we do not cover conditional (P)STNs [Williams et al., 2009], nor (P)STNs with resource usage [Kumar et al., 2018]. In the context of dynamic controllability, the work of [Akmal et al., 2019] is the first attempt to compute the true DDC of a network. They propose an approximation technique, achieving good accuracy rate. In [Brooks et al., 2015], a Monte Carlo sampling approach approximates the DDC, under the NextFirst protocol. Other approximated robustness metrics have been considered: Cesta et al. [1998] and Wilson et al. [2014] see the robustness of a network as a potential of solution flexibility (i.e. aggregate time slack). They coarsely approximate how easily a schedule can be adapted during operations. A quite similar approach has been proposed by [Tsamardinos, 2002], by reasoning on the probability distributions describing the gaps between the time constraint bounds. All these approaches suffer from the fact that they do not account for correlation between temporal constraints, hence over-estimating the true robustness (or flexibility). Cui et al. [2015] define the robustness of STNUs (i.e. under non-probabilistic uncertainty) as the maximum variations that all the contingent durations may face while still having strong/dynamic control. Based on the same idea, Vaquero et al. [2019] define the notion of activity temporal brittleness, by analysing how much duration deviation (based on a distribution) each activity, taken separately, can absorb before the network becomes dynamically uncontrollable. [Saint-Guillain, 2019] constitutes the first attempt at computing a valid lower bound on the DDC, handling ordinary distributions. Yet, their computational method applies to a particular PSTN only, leading to an approximation in the general case. Although not expressed by Table 1, only sampling based methods, such as Monte Carlo, allow to consider PSTNs with dependent contingent constraints realizations. ## 5 Exact Computation of DP-robustness Assumptions and network preprocessing. We assume discrete time horizon and probability distributions. The horizon is noted H = 1..h. We also assume independence between the activity duration probabilities. Let then pdij = P(tj - ti = d) be the probability that the uncertain activity duration, represented by contingent edge (i, j), is of d ∈ H time units. The dynamic execution follows the NextFirst dispatching protocol. To each time point ti ∈ T is always associated a constraint [l0i, u0i], defining the valid time window w.r.t. t0. If no such is specified, we assume [0,∞[. Following Fig. 2(b) we transform the network to avoid contingent synchronisation points. We call tleaf ∈ TC the final time event (e.g. t12 in Fig. 1). In case of multiple final events, we add a final synchronisation one, that links these with [0,∞[ edges. Exact computation. We now describe how to compute the DP-robustness rnf (N) of a network N, using closed-form expressions instead of (1), when using NextFirst protocol. We are interested in the probability that every controllable time point gets assigned a time unit within its boundaries: A little abuse of notations: probability P{α = ⊤} for a logical formula α to be true is denoted P{α}. Since NextFirst execution interrupts as soon as something goes wrong, the network's success probability is equivalent to that of tleaf: (4) reduces to (5), where Pj(t) is the random function that returns the unconditional probability that tj ∈ TC gets dynamically assigned time unit t, when following NextFirst protocol. Pj(t) is recursively computed from tj to t0. In general, the NextFirst DP-robustness of any time event tj is: The remaining of this section describes the computation of Pj(t). We necessarily have Pt0 (0) = 1 and Pt0 (t) = 0 for t > 0. For any time point tj, other than initial t0, let be the probability that tj may be assigned value t, when not considering its lower bounding constraint l0j, if any. Time bounds [lij, uij], i : 1..n are noted [li, ui] for short. NextFirst protocol tells us t must be equal to max(t1+l1, . . . , tn+ln), except if t comes too late, as suggested by the second condition of (7). Then, now considering constraints l0j as well: The summation in the first case accounts for the situations in which ti+lij < l0j. Finally, the computation of fj(t) depends on the type of time point tj which belongs to: either transition or synchronisation point. Transition point. The time point has at most one incoming edge (i, j), either contingent or controllable, in addition to the incoming controllable edge (0, j). This is true for all time points in Fig. 1 excepted t0 and t11. Under NextFirst, where for any controllable event, pdij = 1 if d = lij , 0 otherwise: Synchronisation point. A tj having three or more controllable incoming edges (e.g. t11 in Fig. 1) is called a synchronisation point. From a probability point of view: using the relation P{α ∧ β} = P{α} + P{β} - P{α ∨ β}. Let us assume that all ti's involved in the synchronisation are mutually independent, not to be confounded with that assumed on the contingent constraints TC. We later discuss how to deal with dependency. In such case, the P{α} and P{β} terms of (11) become straightforward to compute: where Fi(t) is the cdf of ti: Fi(t) = ∑t′ :1..t Pi(t′ ). If there is no upper bound constraint ui (i.e., ui = ∞, i : 1..n), then P{α ∨ β} = 1. Otherwise, we have P{α ∨ β} = Removing redundant conjunctions due to t-ui ≤ t-li leads to the noticeable square shaped clauses: Let Ai be the random event in which the conjunction at line i of (14) is true. The intersection of any two or more Ai's leads a conjunction of same size n. For example, P{A1 ∩ A2} = Similarly, A1 ∩ A2 ∩ Ai also leads to a A-shaped conjunction of exactly n inequalities, and so on. Since the ti random variables are assumed mutually independent, the probability of an event AI⊆{1..n} = ⋂i∈I Ai is simply the product of all the probabilities of its terms. For example, for AI = A1∩A2: Using the inclusion-exclusion principle, we finally rewrite: Since we assumed ti variables to be mutually independent, P{⋂i∈I Ai} is computable as a product of Fi(·)'s. However, what if (a subset of) the ti's are not independent? Proposition. Random variables t1, . . . , tn are dependent if they share at least one common unpredictable ancestor. A time point is a predictable ancestor of ti iff its value is deterministic, and can be reached from ti by reversing edges. Proof: Independence hypothesis between contingent constraints implies ti's to be mutually independent if they share no common ancestor. Now suppose: a) All common ancestors are predictable. An equivalent network is obtained by removing those and adding a constraint [l0j , ∞[ to all remaining events, where l0j is the predicted value of the closest ancestor. b) At least one common ancestor ta is not predictable. Knowing ti's value limits the possible realizations for ta, which in turn influences any ti′ having ta as ancestor. Corollary. In the case some contingent constraint has bounded probability distribution, (b) does not hold in general. Yet, we can still infer that if they do not share any common unpredictable ancestor, the events are consequently mutually independent. This is the case for t6 and t10 in Fig. 1. Imposing independence. Whenever a subset of the ti's are potentially dependent, we impose "local independence" on them, by fixing the time value of their closest common ancestor ta, using the law of total probability: In fact, {ta = 0, ta = 1, . . . , ta = h} is a partition of Ω. Probability fj(t | ta = t′ ) is computed after reprocessing part of the network, up to tj, with ta fixed to value t′ . That part corresponds to all the uncommon ancestors, that is, every time point being an ancestor of at least one, but all, of the ti's. Computational complexity. At synchronisation time points, the complexity of computing (15), given t, depends on the maximum number L of dependent events at a synchronisation point. The cdfs F(·) being incrementally maintained, (15) requires O(L·2L) operations, to be repeated at most h times through (16). Putting pieces together, the overall worst-case complexity of computing rnf for a PSTN involving m = |T | time events is bounded by O(mh2L · 2L). ## 6 Experimental Validation We validate our approach on the same dataset as [Akmal et al., 2019] , involving 452 dynamically controllable and 110 uncontrollable instances, with uniform contingent durations. Durations are continuous, whereas our method requires a discrete horizon H = 1..h, so we must round each time constraint [l, u], in a pessimistic way: ⌈l⌉, ⌊u⌋ in the controllable case, ⌈l⌉, ⌈u⌉ for contingent edges. For better accuracy, we include the first D decimals of time bounds l, u at rounding. More decimals leads to better accuracy, but increases the computation times as each decimal multiplies h by 10. Computational method. For each of the 110 uncontrollable PSTNs, we compare the rnf computed values with Monte Carlo (MC) simulations, which simply record the average success rate of NextFirst protocol on M randomly sampled scenarios. The following table gives an overview of the computation times (min, max, mean, geometric mean) as well as the average difference |rnf -MC|, and maximal difference dmax, between predictions and simulations: | | min | max | mean | geo | |rnf -MC| | dmax | |---------|--------|-------|--------|-------|-----------------------|--------| | M = 104 | 0.01 | 0.62 | 0.12 | 0.08 | 0.003 | 0.01 | | M = 105 | 0.14 | 5.58 | 1.06 | 0.73 | 0.0007 | 0.004 | | rnf D=2 | 0.0002 | 3.95 | 0.34 | 0.09 | n.a. | n.a. | | rnf D=3 | 0.0002 | 52.9 | 3.85 | 0.18 | n.a. | n.a. | We now replace the initial uniform distributions involved in the dataset by ordinary ones, randomly generated within the initial bounds. Examples are provided in Fig. 3. The following table shows the average results obtained, where we notice an increased computation time for MC, due to more expensive sampling operations on non-parametric distributions: Figure 3: Examples of randomly generated ordinary distributions. ![Image](https://ijcai.org/proceedings/2020/fulltext/576/image_000002_29fe665ee786f4c74df9535b886d120d74ea7b195fc908c9774c82d93d9272e4.png) | | min | max | mean | geo | |rnf -MC| | dmax | |---------|--------|-------|--------|-------|-----------------------|--------| | M = 104 | 0.02 | 2.47 | 0.39 | 0.24 | 0.002 | 0.01 | | M = 105 | 0.02 | 20.6 | 3.5 | 2.18 | 0.0007 | 0.004 | | rnf D=2 | 0.0004 | 3.23 | 0.29 | 0.08 | n.a. | n.a. | | rnf D=3 | 0.0006 | 53.8 | 4.38 | 0.21 | n.a. | n.a. | Experiments thus validate our equations, but also point potential limitations of our framework, in terms of computational time. When rounding time values to D=3 decimals, the resulting horizon is of h= 49300 time units in average. For some instances, rounding to 4 decimals results in unreasonable computation times (and memory usage). NextFirst dispatching protocol. We now compare our results (rounding to D=3 decimals) with that of [Akmal et al., 2019], on the 110 uncontrollable instances. In the table below, line a (resp. b) corresponds to the number of instances for which the robustness measure (resp. simulations) used in [Akmal et al., 2019] is of at least the probability p: | p | 0.1 | 0.2 | 0.3 | 0.4 | 0.5 | 0.6 | 0.7 | 0.8 | 0.9 | 1.0 | |-----|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------| | a | 97 | 92 | 86 | 80 | 73 | 67 | 61 | 49 | 32 | 0 | | b | 98 | 91 | 85 | 79 | 70 | 64 | 56 | 45 | 29 | 5 | | rnf | 99 | 94 | 89 | 82 | 76 | 68 | 59 | 48 | 32 | 5 | The average robustness difference a - rnf is of -0.011, a percent of probability gain. Tested on the 452 dynamically controllable instances, NextFirst obtains 1.0 robustness on all of them. It means the dynamically controllable instances should not be considered as "hardly controllable", since solved by a simple dispatching protocol. Our results show that despite its simplicity, NextFirst achieves noticeably good robustness compared with a state-of-the-art method. Consequently, the DP-robustness of NextFirst provides a pertinent, close lower bound to the true DDC of a PSTN. ## 7 Application: Mars 2020 Rover's Task Network Structural Analysis Our computational method allows to compute a valid lower bound on the probability of success of each time event of a PSTN, under dynamic control, following eq. (6). We exploit that ability and propose a generic structural brittleness analysis method (inspired by the analysis in [Vaquero et al., 2019]) which computes the impact, on each and every time events of the network, and on the network itself, of increasing (or decreasing) the uncertainty of an activity a by α%. As a proof-of-concept, let us analyse a typical Mars 2020 rover (M2020) sol type, represented as a PSTN, of 18 contingent activities (36 time events). As our M2020 PSTN only (currently) involves Normal distributions, increasing (or decreasing) an activity's uncertainty amounts at modifying its standard deviation by α%. The following table shows how the network gets structurally affected by α = +50%. Figure 4: Structural dependency matrix of a M2020 task network of typical size: 40 activities. Empty rows are not shown. The darker the color of a cell, the bigger the robustness impact. ![Image](https://ijcai.org/proceedings/2020/fulltext/576/image_000003_8ac38641d09afb94a6d6d12c6d76d8e978db5d4ee10bacc1592134ca51b3348d.png) Cell at row i, column j, gives a amount of probability loss of activity j success when i's uncertainty is increased by 50%: | 3 | 4 | ... | 12 | 13 | 14 | ... | 18 | rnf | |--------|------|-------|------|------|------|-------|------|-------| | 95.4 | 51.0 | ... | 90.5 | 90.5 | 90.4 | ... | 100 | 43.7 | | 3 -8.5 | | | | | | | | -3.9 | | 4 | -0.2 | | | | | | | -0.2 | | ... | | ... | | | | | | | | 12 | | | -9.6 | -9.6 | -9.6 | | | -4.7 | | 13 | | | | -0.0 | | | | -0.0 | | 14 | | | | | -0.3 | | | -0.1 | | ... | | | | | | ... | | | | 18 | | | | | | | -0.0 | -0.0 | Empty rows and column are not displayed. The second line of the table gives the initial success probability (%) of each activity; rnf (last column) stands for the entire network's DP-robustness. In fact, the resulting matrix appears quite sparse, meaning that most activities (1-2, 5-11, 15-17) have no impact at all on the robustness of the network. Some activities (3, 4, 13, 14, 18) impact only their own robustness, although some are really unstable: 4 has only 51% success probability, but does not affect the remaining activities. Finally, activity 12 (a long duration drive) here should be considered as structurally critical, as it impacts others (13, 14); it also has the biggest overall impact on the network (-4.7%). This activity has a tight execution time window, which in fact, makes it brittle. This is the same kind of hardly constrained activities observed in [Vaquero et al., 2019]. Finally, Fig. 4 gives an overview on the structural dependency of another M2020 task network. We notice the most critical activities as being 16, 22, 35, 38. Activities 16 and 22 are remote sensing activities (SuperCam). 35 and 38 are NavCam imaging activities. Unlike 12, they enjoy large time window and thus are likely to succeed (e.g. 22's uncertainty does not even impact its own success probability); however, they have a critical impact on many activities later on. These are typically the kind of activities that would not be spotted by previous brittleness analysis, unlike e.g. 5 and 6. Figure 5: The vehicle first travels to Patient 1 (P1) location with a stochastic travel duration. The patient show-up time is also stochastic, and may be late. P1 is then picked up (P1′ ) as soon as the vehicle arrives and the patient shows up. Then P2 is picked up (P2′ ). Now P2 is dropped to her appointment (D2), in time, which finishes at a time D2′ . Meanwhile, P1 is also dropped to her appointment. After dealing with other patients (e.g. P3), P1 is picked up (P1′′ ) at most 20 minutes after the end of her appointment. P2 (P2′′ ) is then picked up before dropping P1 (D1′′ ) at home, fulfilling a maximum ride time constraint, and so it is for P2. ![Image](https://ijcai.org/proceedings/2020/fulltext/576/image_000004_a9995ad61c432d6411bae533f2c42457c46e5864f2765a4aca32669a8c4fb05b.png) ## 8 Other Potential Application Domains PSTNs are not limited to the coordination of planetary rovers. When considering ordinary distributions, it could contribute at providing new, original tools for solving various challenging real life problems. In the following applications, both PSTN and NextFirst seem particularly well suited. On-demand public transportation. Consider the problem of transporting patients from their home to medical appointments [Paquay et al., 2020]. The so-called dial-a-ride problem (DARP) admits a significant part of temporal uncertainty: patient delays, traffic jams, appointment durations. Each request consists in picking up a patient from home and dropping it at an appointment, and return it to home. Because the limited number of vehicles, the requests are typically mixed. The problem consists in scheduling the pickup and deliveries so that the probability of meeting all the constraints is maximized. In such context, only sampling approaches have been proposed in order to approximate the probability of success of a schedule. The PSTN formalism is particularly well suited for describing such a schedule, as illustrated in Fig. 5. Not only the PSTN formalism applies to such operational context, but also the method we propose efficiently computes the exact success probability of a given schedule. Operations management in hospitals. Consider the problem of managing the use of operating rooms in a hospital. Whereas a number of non-urgent surgeries are known in advance, additional emergencies requiring an immediate surgery arise daily in a dynamic fashion. There is uncertainty associated with a surgery duration. Provided a limited number of rooms, hospitals must schedule their interventions in a way that any upcoming emergency can be scheduled as soon as possible. Given an a priori surgery schedule, what is the expected delay of each scheduled surgery due to the arising of emergencies? A possible PSTN representation of an operating room schedule, while considering online emergencies, is shown in Fig. 6. Given the probability of an emergency arising during a time interval, and the probability distribution of such an event duration, one can infer a contingent duration describing the additional time inquired at facing the emergency. Due to the inherent non-symmetric multi-modal nature of such distributions describing events that may or not arise, our method offers the only known efficient computation of the expected impact of online events on predefined schedules. Here, the goal is not to compute a success probability. Instead, our method can compute the exact probability distribution of each scheduled surgery's time assignment, and therefore its expected delay w.r.t. the initial schedule. Figure 6: Operations start with scheduled surgery S1, having uncertain duration. There is a probability that an emergency appears in the meanwhile. If it does, depending on its scheduled time, S2 may be delayed. Our framework has the particularity to infer the time value assignment probabilities at any time event, such as S2. This allows to compute expected delays, the probability to be on time, etc. ![Image](https://ijcai.org/proceedings/2020/fulltext/576/image_000005_cc3ec6333b70b934e73ede0e30635ebf0cf8c360ee73ce69035a4dfdf3add1ba.png) ## 9 Conclusions We introduced an exact approach to robustness computation in the context of dynamic control of uncontrollable probabilistic temporal networks, under discrete time assumption. By relying on simplifying operational assumptions, the computed robustness constitutes a strict lower bound on the degree of dynamic controllability under perfect dynamic assignment. Our method positions as an exact alternative to Monte Carlo simulations, by also allowing to compute the success probability of each activity of the network separately, leading to new potential applications and analysis frameworks. An open source C++ implementation of our method is available online: https://bitbucket.org/mstguillain/dprobustness. The developed method will be useful for Mars 2020 or rovers to come. Further applications are under considerations, including actual duration data histograms (i.e. nonparametric, ordinary distributions) from Mars Science Laboratory, for which the results should differ from those using approximated normal distributions. We also described potential contributions to significantly different application domains, for which the only possible approach so far relied on sampling approximations (e.g. Monte Carlo), as our method allows to compute exact probability distributions of any time point assignment, and deals with ordinary distributions. ## Acknowledgments The research was carried out at the Jet Propulsion Laboratory, California Institute of Technology, under a contract with the National Aeronautics and Space Administration. ## References 1. [Agrawal et al., 2019] Jagriti Agrawal, Wayne Chi, Steve Chien, Gregg Rabideau, Stephen Khun, and Daniel Gaines. Enabling Limited Resource-Bounded Disjunc- tion in Scheduling. Proceedings of the 11th International Workshop on Planning and Scheduling for Space (IWPSS), pages 7-15, 2019. 2. [Akmal et al., 2019] Shyan Akmal, Savana Ammons, Hemeng Li, and James C Boerkoel Jr. Quantifying Degrees of Controllability in Temporal Networks with Uncertainty. In 29th International Conference on Automated Planning and Scheduling (ICAPS), 2019. 3. [Bhargava and Williams, 2019] Nikhil Bhargava and Brian C. Williams. Complexity bounds for the controlla- bility of temporal networks with conditions, disjunctions, and uncertainty. Artificial Intelligence, 271:1-17, 2019. 4. [Birge and Louveaux, 2011] John R Birge and Franc ¸ois Lou- veaux. Introduction to stochastic programming. Springer, New York, NY, 2011. 5. [Brooks et al., 2015] Jeb Brooks, Emilia Reed, Alexander Gruver, and James C Boerkoel Jr. Robustness in Proba- bilistic Temporal Planning. In 29th AAAI Conference on Artificial Intelligence, pages 3239-3246, 2015. 6. [Cesta et al., 1998] Amedeo Cesta, Angelo Oddi, and Stephen F. Smith. Profile based algorithms to solve mul- tiple capacitated metric scheduling problems. In Interna- tional Conference on Artificial Intelligence Planning Sys- tems (AIPS), pages 214-223, 1998. 7. [Chi et al., 2018] Wayne Chi, Steve Chien, Jagriti Agrawal, Gregg Rabideau, Edward Benowitz, Daniel Gaines, El- yse Fosse, Stephen Kuhn, and James Biehl. Embed- ding a Scheduler in Execution for a Planetary Rover. In 28th International Conference on Automated Planning and Scheduling (ICAPS), 2018. 8. [Chi et al., 2019] Wayne Chi, Jagriti Agrawal, Steve Chien, Elyse Fosse, and Usha Guduri. Optimizing Parameters for Uncertain Execution and Rescheduling Robustness. In 29th International Conference on Automated Planning and Scheduling (ICAPS), 2019. 9. [Cui and Haslum, 2019] Jing Cui and Patrik Haslum. Dy- namic controllability of controllable conditional temporal problems with uncertainty. Journal of Artificial Intelli- gence Research, 64:445-495, 2019. 10. [Cui et al., 2015] Jing Cui, P Yu, Cheng Fang, Patrik Haslum, and Brian C Williams. Optimising Bounds in Simple Temporal Networks with Uncertainty under Dynamic Controllability Constraints. In 19th Interna- tional Conference on Automated Planning and Scheduling (ICAPS), pages 52-60, 2015. 11. [Dechter et al., 1991] Rina Dechter, Itay Meiri, and Judea Pearl. Temporal constraint networks. Artificial intelli- gence, 49(1-3):61-95, 1991. 12. [Gaines et al., 2016] Daniel Gaines, Robert Anderson, Gary Doran, William Huffman, Heather Justice, Ryan Mackey, Gregg Rabideau, Ashwin Vasavada, Vandana Verma, Tara Estlin, Lorraine Fesq, Michel Ingham, Mark Maimone, and Issa Nesnas. Productivity Challenges for Mars Rover Operations. Proceedings of the International Conference on Automated Planning and Scheduling, Planning and Robotics Workshop (PlanRob), 2016. 13. [Kumar et al., 2018] Satish T. K. Kumar, Zhi Wang, Anoop Kumar, Craig Milo Rogers, and Craig A. Knoblock. Load scheduling of simple temporal networks under dynamic resource pricing. In 32nd AAAI Conference on Artificial Intelligence, 2018. 14. [Morris et al., 2001] Paul Morris, Nicola Muscettola, and Thierry Vidal. Dynamic Control Of Plans With Tempo- ral Uncertainty. In 17th International Joint Conference on Artificial Intelligence (IJCAI), page 494-499. 15. [Morris, 2014] Paul Morris. Dynamic controllability and dis- patchability relationships. In International Conference on AI and OR Techniques in Constriant Programming for Combinatorial Optimization Problems, pages 464-479. Springer, 2014. 16. [Paquay et al., 2020] Célia Paquay, Yves Crama, and Thierry Pironet. Recovery management for a dial-a-ride system with real-time disruptions. European Journal of Operational Research, 280:953-969, 2020. 17. [Rabideau and Benowitz, 2017] Gregg Rabideau and Ed Benowitz. Prototyping an Onboard Scheduler for the Mars 2020 Rover. Proceedings of the International Workshop on Planning and Scheduling for Space, IWPSS, 2017. 18. [Saint-Guillain, 2019] Michael Saint-Guillain. Robust Oper- ations Management on Mars. In 29th International Con- ference on Automated Planning and Scheduling (ICAPS), Berkeley, CA, USA, 2019. 19. [Tsamardinos, 2002] Ioannis Tsamardinos. A probabilistic approach to robust execution of temporal plans with un- certainty. In Hellenic Conference on Artificial Intelligence, pages 97-108, 2002. 20. [Vaquero et al., 2019] Tiago Vaquero, Steve Chien, Jagriti Agrawal, Wayne Chi, and Terrance Huntsberger. Tem- poral Brittleness Analysis of Task Networks for Planetary Rovers. In 29th International Conference on Automated Planning and Scheduling (ICAPS), 2019. 21. [Vidal and Ghallab, 1996] Thierry Vidal and Malik Ghallab. Dealing with Uncertain Durations In Temporal Constraint Networks dedicated to Planning. In 12th European Con- ference on Artificial Intelligence (ECAI), pages 48-54. 22. PITMAN, 1996. 23. [Williams et al., 2009] Brian Williams, Patrick Conrad, and Julie Shah. Flexible Execution of Plans with Choice. In 19th International Conference on Automated Planning and Scheduling (ICAPS), pages 74-81, 2009. 24. [Wilson et al., 2014] Michel Wilson, Tomas Klos, Cees Wit- teveen, and Bob Huisman. Flexibility and decoupling in Simple Temporal Networks. Artificial Intelligence, 214:26-44, 2014.