Bi-Intervals for Backtracking on Temporal Constraint Networks

Jean-François Baget 1, 2 Sébastien Laborie 1, 3, 4
1 EXMO - Computer mediated exchange of structured knowledge
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
2 GRAPHIK - Graphs for Inferences on Knowledge
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier, CRISAM - Inria Sophia Antipolis - Méditerranée
3 WAM - Web, adaptation and multimedia
Inria Grenoble - Rhône-Alpes
Abstract : Checking satisfiability of temporal constraint networks involves infinite variables domains. We explore a solution based upon finite partitions of infinite domains. Though a straightforward partition results in a sound and complete backtrack, its extension to forward checking is not complete. Using bi-intervals, we obtain sound and complete backtrack and forward checking algorithms. Moreover, we show that bi-intervals used in a hybrid algorithm which also instanti- ates constraints improve backtrack efficiency.
Type de document :
Communication dans un congrès
TIME: Temporal Represetation and Reasoning, Jun 2007, Alicante, Spain. IEEE, International Symposium on Temporal Represetation and Reasoning, pp.163-168, 2007, <10.1109/TIME.2007.44>
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00195488
Contributeur : Jean-François Baget <>
Soumis le : mardi 11 décembre 2007 - 09:39:23
Dernière modification le : lundi 20 juin 2016 - 01:04:17

Identifiants

Collections

Citation

Jean-François Baget, Sébastien Laborie. Bi-Intervals for Backtracking on Temporal Constraint Networks. TIME: Temporal Represetation and Reasoning, Jun 2007, Alicante, Spain. IEEE, International Symposium on Temporal Represetation and Reasoning, pp.163-168, 2007, <10.1109/TIME.2007.44>. <lirmm-00195488>

Partager

Métriques

Consultations de la notice

310