Checking the Dynamic Consistency of Conditional Temporal Networks with Bounded Reaction Times
Checking the Dynamic Consistency of Conditional Temporal Networks with Bounded Reaction Times
复制标题
检查具有有限反应时间的条件时态网络的动态一致性
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Roberto Posenato
中科院分区：
文献类型：
--
作者：
Luke Hunsberger;Roberto Posenato
条件简单时态网络（Conditional Simple Temporal Network，CNOW）包括时间点、时态约束和观测时间点，它们的执行在运行时产生信息。时间点和约束条件在一个CCENTRAL可能只适用于某些情况下。一个动态一致性（DC），如果它有一个策略来执行它的时间点，使得所有相关的约束都将得到满足，无论观察结果如何。动态策略可以在真实的时间内对观测作出反应，但仅在任意小的正延迟之后。最近的工作引入了一个更现实的ε-DC属性，对于固定的ε>0，要求所有反应时间都以ε为界。这项工作提出了一种指数算法，通过将指数数量的组件网络转换为超时间网络来检查ε-DC属性。但它尚未得到实施或经验评估。本文首先提出了一种替代的，等效的语义ε-动态一致性。然后，它提出了一个健全的和完整的epsilon-DC-检查算法的基础上传播的标记约束。最后，它提出了一个新算法的实证评估，在文献中的任何ε-DC检查算法的第一个实证评估。
A Conditional Simple Temporal Network (CSTN) includes time-points, temporal constraints, and observation time-points, whose execution yields information during run-time. Time-points and constraints in a CSTN may only apply in certain scenarios. A CSTN is dynamically consistent (DC) if it has a strategy for executing its time-points such that all relevant constraints will be satisfied no matter how the observations turn out. A dynamic strategy can react to observations in real time, but only after arbitrarily small, but positive delays. Recent work introduced a more realistic epsilon-DC property which, for a fixed epsilon>0, requires all reaction times to be bounded below by epsilon. That work presented an exponential algorithm for checking the epsilon-DC property by translating an exponential number of component networks into a Hyper Temporal Network. But it has not yet been implemented or empirically evaluated. This paper begins by presenting an alternative, equivalent semantics for epsilon-dynamic consistency. It then presents a sound-and-complete epsilon-DC-checking algorithm based on the propagation of labeled constraints. Finally, it presents an empirical evaluation of the new algorithm, the first empirical evaluation of any epsilon-DC-checking algorithm in the literature.