Simpler and Faster Algorithm for Checking the Dynamic Consistency of Conditional Simple Temporal Networks
Simpler and Faster Algorithm for Checking the Dynamic Consistency of Conditional Simple Temporal Networks
复制标题
用于检查条件简单时态网络动态一致性的更简单、更快的算法
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Roberto Posenato
中科院分区：
文献类型：
--
作者：
Luke Hunsberger;Roberto Posenato
最近关于条件简单时间网络（CSTNs）的工作
重点检查动态一致性（DC）属性，假设
执行策略可以即时对观察做出反应。
提出了三种可供选择的语义--IR-DC、0-DC和π-DC。
本文仅分析了CSTNs中最实用的DC检测算法
相对于IR-DC语义，0-DC语义被证明具有严重缺陷
这是π-DC语义所修复的。IR-DC语义是否
同样的缺陷，如果是这样的话，
DC检查算法仍然是开放的问题。
本文（1）证明了IR-DC语义也是有缺陷的;
(2)显示了来自
IR-DC检查算法相对于IR-DC是不健全的
语义学;
(3)提出了一种简单的π-DC校验算法;
(4)证明了它在π-DC语义上是可靠的和完备的;
以及（5）对新算法进行经验评估。
Recent work on Conditional Simple Temporal Networks (CSTNs) has
focused on checking the dynamic consistency (DC) property assuming
that execution strategies can react instantaneously to observations.
Three alternative semantics---IR-DC, 0-DC, and π-DC---have been presented.
The most practical DC-checking algorithm for CSTNs has only been analyzed
with respect to the IR-DC semantics, while the 0-DC semantics was shown to have a serious flaw
that the π-DC semantics fixed. Whether the IR-DC semantics had
the same flaw and, if so, what the consequences would be for the
DC-checking algorithm remained open questions.
This paper (1) shows that the IR-DC semantics is also flawed;
(2) shows that one of the constraint-propagation rules from
the IR-DC-checking algorithm is not sound with respect to the IR-DC
semantics;
(3) presents a simpler algorithm, called the π-DC-checking algorithm;
(4) proves that it is sound and complete with respect to the π-DC semantics;
and (5) empirically evaluates the new algorithm.