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 metadatas

Cited literature [19 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-02310598
Contributor : Isabelle Gouat <>
Submitted on : Thursday, October 10, 2019 - 12:13:01 PM
Last modification on : Thursday, May 14, 2020 - 6:58:06 PM

File

caia93.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-02310598, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

48

Files downloads

48