Application of Constraint Networks Filtering Techniques to Truth Maintenance Systems - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 1993

Application of Constraint Networks Filtering Techniques to Truth Maintenance Systems

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.
Fichier principal
Vignette du fichier
caia93.pdf (238.44 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

lirmm-02310598 , version 1 (10-10-2019)

Identifiers

  • HAL Id : lirmm-02310598 , version 1

Cite

Christian Bessiere. 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⟩
48 View
81 Download

Share

Gmail Facebook X LinkedIn More