Skip to Main content Skip to Navigation
Conference papers

Application of Constraint Networks Filtering Techniques to Truth Maintenance Systems

Christian Bessière 1 
1 COCONUT - Agents, Apprentissage, Contraintes
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : A truth maintenance system (TMS) is a general problem solving facility designed to work in tandem with an inference engine. Justification-based TMSs (the most commonly used TMSs) have not a sufficient expressive power for many applications. Logic-based TMSs overcome this limitation but are untractable. So, McAllester, or Forbus and de Kleer, have proposed to encode formulae in clauses and to run the efficient Boolean Constraint Propagation algorithm (BCP), what lose the completeness of the deductions. In this paper, we introduce the model of Constraint Networks (CNs), underlining that the notion of local completeness (called local-consistency in CNs) has been widely treated in CNs. We then propose an encoding of McAllester's TMS in Dynamic CN to be able to use CNs techniques. We show that not only we can compute as many deductions as BCP for the same time-consuming, but also we can outperform the local completeness computed for a slight more running-time. AI topic: reasoning Domain area: Expert systems, problem solving Impact: The estimated benefit is 40% more information deduced (in average) in a problem solver, while keeping reasonable time-consuming.
Document type :
Conference papers
Complete list of metadata

Cited literature [19 references]  Display  Hide  Download
Contributor : Isabelle Gouat Connect in order to contact the contributor
Submitted on : Thursday, October 10, 2019 - 12:13:01 PM
Last modification on : Friday, August 5, 2022 - 3:02:57 PM


Files produced by the author(s)


  • HAL Id : lirmm-02310598, version 1



Christian Bessière. Application of Constraint Networks Filtering Techniques to Truth Maintenance Systems. CAIA: Conference on Artificial Intelligence for Applications, Mar 1993, Orlando, FL, United States. pp.41-47. ⟨lirmm-02310598⟩



Record views


Files downloads