Skip to Main content Skip to Navigation
Conference papers

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 metadata
Contributor : Jean-François Baget Connect in order to contact the contributor
Submitted on : Tuesday, December 11, 2007 - 9:39:23 AM
Last modification on : Friday, October 22, 2021 - 3:07:22 PM





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⟩



Record views