Faster Dynamic Controllability Checking for Simple Temporal Networks with Uncertainty
Faster Dynamic Controllability Checking for Simple Temporal Networks with Uncertainty
复制标题
具有不确定性的简单时态网络的更快动态可控性检查
DOI：
10.4230/lipics.time.2018.8
复制
发表时间：
2018
期刊：
影响因子：
2.1
通讯作者：
Romeo Rizzi
中科院分区：
文献类型：
--
作者：
Massimo Cairo;Luke Hunsberger;Romeo Rizzi
简单时间网络（STNs）是一种用于表示和推理时间的模型。时间点由一组称为时间点的实值变量和一组二元约束组成，每个约束的形式为Y ≤ X + w。找到一个可行的时间表的问题（即，将真实的数分配给时间点，使得满足所有的约束（艾德）等价于图中的单源最短路径问题（SSSP）。具有不确定性的简单时间网络（STNU）增强了STNs，以包括可用于表示具有不确定持续时间的动作的偶然链接。偶然链接的持续时间不受计划者控制，而是由（可能是敌对的）环境控制。每个偶然的链接具有形式，h A，'，u，Ci，其中0 < ' ≤ u < ∞。一旦计划器执行激活时间点A，环境必须在某个时间A + u执行偶然时间点C，其中u ∈ [ '，u ]。至关重要的是，规划者事先并不知道css的值，而只是在C执行时才发现它。STNU是动态可控的（DC），如果有一个策略，规划者可以使用它来执行所有的非偶然时间点，这样，无论环境为偶然链接选择什么持续时间，都可以保证萨蒂斯所有的约束。策略可以是动态的，因为它可以在真实的时间内对它观察到的偶然持续时间做出反应。最近，一个上限为O（N3）的DC检查问题的STNU，其中N是时间点的数量。本文介绍了一种新的算法，称为RUL-算法，用于解决
Simple Temporal Networks (STNs) are a well-studied model for representing and reasoning about time. An STN comprises a set of real-valued variables called time-points, 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 time-points 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, h A, ‘, u, C i , where 0 < ‘ ≤ u < ∞ . Once the planner executes the activation time-point A , the environment must execute the contingent time-point C at some time A +∆, where ∆ ∈ [ ‘, u ]. Crucially, the planner does not know the value of ∆ 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 non-contingent time-points, 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 DC-checking problem for STNUs, where N is the number of time-points. This paper introduces a new algorithm, called the RUL − algorithm, for solving the