Abstract
Simple Temporal Networks (STNs) are a wellstudied model for representing and reasoning about time. An STN comprises a set of realvalued variables called timepoints, together with a set of binary constraints, each of the form Y <= X+w. The problem of finding a feasible schedule (i.e., an assignment of real numbers to timepoints such that all of the constraints are satisfied) is equivalent to the Single Source Shortest Path problem (SSSP) in the STN graph.
Simple Temporal Networks with Uncertainty (STNUs) augment STNs to include contingent links that can be used, for example, to represent actions with uncertain durations. The duration of a contingent link is not controlled by the planner, but is instead controlled by a (possibly adversarial) environment. Each contingent link has the form, <A,l,u,C>, where 0 < l <= u < infty. Once the planner executes the activation timepoint A, the environment must execute the contingent timepoint C at some time A+Delta, where Delta in [l,u]. Crucially, the planner does not know the value of Delta in advance, but only discovers it when C executes. An STNU is dynamically controllable (DC) if there is a strategy that the planner can use to execute all of the noncontingent timepoints, such that all of the constraints are guaranteed to be satisfied no matter which durations the environment chooses for the contingent links. The strategy can be dynamic in that it can react in real time to the contingent durations it observes. Recently, an upper bound of O(N^3) was given for the DCchecking problem for STNUs, where N is the number of timepoints.
This paper introduces a new algorithm, called the RUL^ algorithm, for solving the DCchecking problem for STNUs that improves on the O(N^3) bound. The worstcase complexity of the RUL^ algorithm is O(MN+K^2N+KN log N), where N is the number of timepoints, M is the number of constraints, and K is the number of contingent timepoints. If M is O(N^2), then the complexity reduces to O(N^3); however, in sparse graphs the complexity can be much less. For example, if M is O(N log N), and K is O(sqrt{N}), then the complexity of the RUL^ algorithm reduces to O(N^2 log N).
The RUL^ algorithm begins by using the BellmanFord algorithm to compute a potential function. It then performs at most 2K rounds of computations, interleaving novel applications of Dijkstra's algorithm to (1) generate new edges and (2) update the potential function in response to those new edges. The constraintpropagation/edgegeneration rules used by the RUL^ algorithm are distinguished from related work in two ways. First, they only generate unlabeled edges. Second, their applicability conditions are more restrictive. As a result, the RUL^ algorithm requires only O(K) rounds of Dijkstra's algorithm, instead of the O(N) rounds required by other approaches. The paper proves that the RUL^ algorithm is sound and complete for the DCchecking problem for STNUs.
BibTeX  Entry
@InProceedings{cairo_et_al:LIPIcs:2018:9773,
author = {Massimo Cairo and Luke Hunsberger and Romeo Rizzi},
title = {{Faster Dynamic Controllability Checking for Simple Temporal Networks with Uncertainty}},
booktitle = {25th International Symposium on Temporal Representation and Reasoning (TIME 2018)},
pages = {8:18:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770897},
ISSN = {18688969},
year = {2018},
volume = {120},
editor = {Natasha Alechina and Kjetil N{\o}rv{\aa}g and Wojciech Penczek},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9773},
URN = {urn:nbn:de:0030drops97734},
doi = {10.4230/LIPIcs.TIME.2018.8},
annote = {Keywords: Simple Temporal Networks with Uncertainty, Dynamic Controllability, Temporal Planning under Uncertainty}
}
Keywords: 

Simple Temporal Networks with Uncertainty, Dynamic Controllability, Temporal Planning under Uncertainty 
Collection: 

25th International Symposium on Temporal Representation and Reasoning (TIME 2018) 
Issue Date: 

2018 
Date of publication: 

08.10.2018 