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.
Document type :
Conference papers
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00195488
Contributor : Jean-François Baget <>
Submitted on : Tuesday, December 11, 2007 - 9:39:23 AM
Last modification on : Friday, October 25, 2019 - 1:25:31 AM

Identifiers

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. pp.163-168, ⟨10.1109/TIME.2007.44⟩. ⟨lirmm-00195488⟩

Share

Metrics

Record views

607