A Streamlined Model of Conditional Simple Temporal Networks - Semantics and Equivalence Results
A Streamlined Model of Conditional Simple Temporal Networks - Semantics and Equivalence Results
复制标题
条件简单时态网络的简化模型 - 语义和等价结果
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Romeo Rizzi
中科院分区：
文献类型：
--
作者：
Massimo Cairo;Luke Hunsberger;Roberto Posenato;Romeo Rizzi
条件简单时间网络（Conditional Simple Temporal Network，简称CSTN）是对简单时间网络的扩充，它包含了一种新的时间点，称为观测时间点。观察时间点的执行在真实的时间中生成信息，具体地，命题字母的真值。此外，时间点和时间约束可以通过（肯定或否定）命题字母的连词来标记。如果存在一个动态策略来执行它的时间点，使得无论观察结果如何，其标签与这些观察一致的时间点都已被执行，并且其标签与这些观察一致的约束都已被满足，则称为动态一致（DC）。该策略是动态的，因为其执行决策可能会对观察做出反应。CSTNs的原始公式仅包括时间点上的命题标签，但DC检查算法是不切实际的，因为它是基于将语义约束转换为指数大小的析取时态网络。后来的工作将命题标签添加到时间约束中，并产生了一个基于声音和完整传播的DC检查算法，经验证明在各种CSTN中是实用的。本文介绍了一个简化版本的Cynomial中，命题标签可能会出现在约束，但不是时间点。此更改简化了DC属性的定义以及DC检查算法的传播规则。它还简化了这些规则的可靠性和完备性的证明。本文提供了两种从传统的CSTNs到流线型CSTNs的翻译。每个转换都保留了DC属性，并且对于任何DC网络，确保该网络的任何动态执行策略都可以扩展为其精简的对应策略。最后，本文提出了一个经验比较的两个版本的DC检查算法：原始版本和简化版本的精简CSTNs。该比较基于早期工作中的CSTN基准测试。对于小规模的CSTN，原始版本表现出最好的性能，但两个版本之间的性能差异随着时间点的CSTN中的数量的增加而减小。我们的结论是，简化算法是一个实用的替代检查CSTNs的动态一致性。1998年ACM主题分类G.2.2图论，I.2.8问题解决，控制方法和搜索
A Conditional Simple Temporal Network (CSTN) augments a Simple Temporal Network to include a new kind of time-point, called an observation time-point. The execution of an observation time-point generates information in real time, specifically, the truth value of a propositional letter. In addition, time-points and temporal constraints may be labeled by conjunctions of (positive or negative) propositional letters. A CSTN is called dynamically consistent (DC) if there exists a dynamic strategy for executing its time-points such that no matter how the observations turn out during execution, the time-points whose labels are consistent with those observations have all been executed, and the constraints whose labels are consistent with those observations have all been satisfied. The strategy is dynamic in that its execution decisions may react to observations. The original formulation of CSTNs included propositional labels only on time-points, but the DC-checking algorithm was impractical because it was based on a conversion of the semantic constraints into an exponentially-sized Disjunctive Temporal Network. Later work added propositional labels to temporal constraints, and yielded a sound-and-complete propagation-based DC-checking algorithm, empirically demonstrated to be practical across a variety of CSTNs. This paper introduces a streamlined version of a CSTN in which propositional labels may appear on constraints, but not on time-points. This change simplifies the definition of the DC property, as well as the propagation rules for the DC-checking algorithm. It also simplifies the proofs of the soundness and completeness of those rules. This paper provides two translations from traditional CSTNs to streamlined CSTNs. Each translation preserves the DC property and, for any DC network, ensures that any dynamic execution strategy for that network can be extended to a strategy for its streamlined counterpart. Finally, this paper presents an empirical comparison of two versions of the DC-checking algorithm: the original version and a simplified version for streamlined CSTNs. The comparison is based on CSTN benchmarks from earlier work. For small-sized CSTNs, the original version shows the best performance, but the performance difference between the two versions decreases as the number of time-points in the CSTN increases. We conclude that the simplified algorithm is a practical alternative for checking the dynamic consistency of CSTNs. 1998 ACM Subject Classification G.2.2 Graph Theory, I.2.8 Problem Solving, Control Methods, and Search