Instantaneous Reaction-Time in Dynamic-Consistency Checking of Conditional Simple Temporal Networks

Abstract : 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.
Type de document :
Communication dans un congrès
TIME 2016 23rd International Symposium on Temporal Representation and Reasoning, Oct 2016, Kongens Lyngby, Denmark. IEEE, pp.80-89, 2016, Temporal Representation and Reasoning (TIME), 2016 23rd International Symposium on. 〈10.1109/TIME.2016.16〉
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

https://hal-upec-upem.archives-ouvertes.fr/hal-01577460
Contributeur : Admin Upem <>
Soumis le : vendredi 25 août 2017 - 17:46:41
Dernière modification le : jeudi 5 juillet 2018 - 14:45:47

Fichier

conditional-temporal-networks-...
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Massimo Cairo, Carlo Comin, Romeo Rizzi. Instantaneous Reaction-Time in Dynamic-Consistency Checking of Conditional Simple Temporal Networks. TIME 2016 23rd International Symposium on Temporal Representation and Reasoning, Oct 2016, Kongens Lyngby, Denmark. IEEE, pp.80-89, 2016, Temporal Representation and Reasoning (TIME), 2016 23rd International Symposium on. 〈10.1109/TIME.2016.16〉. 〈hal-01577460〉

Partager

Métriques

Consultations de la notice

124

Téléchargements de fichiers

30