Instantaneous Reaction-Time in Dynamic-Consistency Checking of Conditional Simple Temporal Networks
Instantaneous Reaction-Time in Dynamic-Consistency Checking of Conditional Simple Temporal Networks
复制标题
条件简单时态网络动态一致性检查中的瞬时反应时间
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Romeo Rizzi
中科院分区：
文献类型：
--
作者：
Massimo Cairo;Carlo Comin;Romeo Rizzi
条件简单时态网络CSTN是一种基于约束的图形式的有条件时态规划方法。CSTN和CSTP出现了三个一致性概念：弱、强和动态。动态一致性(DC)是最有趣的概念，但也是最具挑战性的。为了解决DC检查问题，在[Comin and Rizzi，Time 2015]中，我们引入了ε-DC(一种改进的、更现实的DC概念)，并提供了它的算法解决方案。其次，假设DC对足够小的ε>；0蕴含ε-dc，并且对于每个ε>；0它认为ε-dc蕴含dc，我们给出了这两个概念重合的反应时间ε的临界值的一个尖锐的下界分析。这为CSTN的DC检查提供了第一个(伪)单指数时间算法。然而，ε-DC概念本身很有趣，[Comin and Rizzi，Time 2015]中的ε-DC-Checking算法基于反应时间满足ε>；0的假设，没有解决当ε=0时会发生什么的问题。在这项工作中，我们引入并研究了π-DC，这是一个合理的DC概念，具有瞬时反应时间(即规划者可以在进行观测的同一时刻对任何观测做出反应)。首先，我们通过一个反例证明了π-DC不等价于0-DC，并且0-DC实际上不足以建模具有瞬时反应时间的DC。这表明，我们以前工作中得到的主要结果并不直接适用于ε=0的情况。受此启发，作为第二个贡献，我们对以前的工具进行了扩展，以处理π-DC，并引入了PS-树的概念，指出了π-DC与HyTN-一致性之间的关系。第三，证明了从π-DC-Checking到DC-Checking的一种简单简化。这使我们能够设计和分析第一个声音和完整的π-DC检查程序。值得注意的是，该算法的时间复杂度仍然是命题字母数的(伪)单指数。
Conditional Simple Temporal Network CSTN is a constraint-based graph-formalism for conditional temporal planning. Three notions of consistency arise for CSTNs and CSTPs: weak, strong, and dynamic. Dynamic-Consistency (DC) is the most interesting notion, but it is also the most challenging. In order to address the DC-Checking problem, in [Comin and Rizzi, TIME 2015] we introduced ε-DC (a refined, more realistic, notion of DC), and provided an algorithmic solution to it. Next, given that DC implies ε-DC for some sufficiently small ε > 0, and that for every ε > 0 it holds that ε-DC implies DC, we offered a sharp lower bounding analysis on the critical value of the reaction-time ε under which the two notions coincide. This delivered the first (pseudo) singly-exponential time algorithm for the DC-Checking of CSTNs. However, the ε-DC notion is interesting per se, and the ε-DC-Checking algorithm in [Comin and Rizzi, TIME 2015] rests on the assumption that the reaction-time satisfies ε > 0, leaving unsolved the question of what happens when ε = 0. In this work, we introduce and study π-DC, a sound notion of DC with an instantaneous reaction-time (i.e. one in which the planner can react to any observation at the same instant of time in which the observation is made). Firstly, we demonstrate by a counter-example that π-DC is not equivalent to 0-DC, and that 0-DC is actually inadequate for modeling DC with an instantaneous reaction-time. This shows that the main results obtained in our previous work do not apply directly, as they were formulated, to the case of ε = 0. Motivated by this observation, as a second contribution, our previous tools are extended in order to handle π-DC, and the notion of ps-tree is introduced, also pointing out a relationship between π-DC and HyTN-Consistency. Thirdly, a simple reduction from π-DC-Checking to DC-Checking is identified. This allows us to design and to analyze the first sound-and-complete π-DC-Checking procedure. Remarkably, the time complexity of the proposed algorithm remains (pseudo) singly-exponential in the number of propositional letters.