Bi-Intervals for Backtracking on Temporal Constraint Networks - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2007

Bi-Intervals for Backtracking on Temporal Constraint Networks

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.
No file

Dates and versions

lirmm-00195488 , version 1 (11-12-2007)

Identifiers

Cite

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⟩
189 View
0 Download

Altmetric

Share

More