Instantaneous reaction-time in dynamic consistency checking of conditional simple temporal networks

摘要

Conditional Simple Temporal Networks (CSTNs) is a constraint based graph-formalism for conditional temporal planning. Three notions of consistency arise for CSTNs: 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, Comin and Rizzi [12] introduced epsilon-DC (a refined, more realistic, notion of DC), providing an algorithmic solution to it. Next, given that DC implies epsilon-DC for some sufficiently small epsilon > 0, and that for every epsilon > 0 it holds that epsilon-DC implies DC, it was offered a sharp lower bounding analysis on the critical value of the reaction-time (epsilon) over cap under which the two notions coincide. This delivered the first (pseudo) singly-exponential time algorithm for the DC-Checking of CSTNs. However, the epsilon-DC notion is interesting per se, and the epsilon-DC-Checking algorithm of Comin and Rizzi [12] rests on the assumption that the reaction-time satisfies epsilon > 0; leaving unsolved the question of what happens when epsilon = 0. In this work, we introduce and study pi-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 pi-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 epsilon = 0. Motivated by this observation, as a second contribution, our previous tools are extended in order to handle pi-DC, and the notion of ps-tree is introduced, also pointing out a relationship between pi-DC and consistency of Hyper Temporal Networks. Thirdly, a simple reduction from pi-DC to (classical) DC is identified. This allows us to design and to analyze the first sound-and-complete pi-DC-Checking algorithm. Remarkably, the time complexity of the proposed algorithm remains (pseudo) singly-exponential in the number of propositional letters. Finally, it is observed that the technique can be leveraged to actually reduce from pi-DC to 1-DC, this allows us to further improve the exponents in the time complexity. (C) 2020 Elsevier Inc. All rights reserved.