Skip to Main content Skip to Navigation
Conference papers

Une approche DPLL pour l'abduction

Florian Letombe 1 Bruno Zanuttini 2
2 Equipe MAD - Laboratoire GREYC - UMR6072
GREYC - Groupe de Recherche en Informatique, Image, Automatique et Instrumentation de Caen
Résumé : L'abduction est le processus consistant à expliquer une observation $q$ étant donnée une base de connaissances $KB$, c'est-à-dire à trouver un ensemble de faits $E$, appelé une explication, tel que $KB$ et $E$ impliquent conjointement $q$. De plus, les explications sont contraintes par un ensemble d'hypothèses $H$, c'est-à-dire un ensemble de littéraux sur lesquels elles doivent être formées. Ce problème est reconnu pour avoir de nombreuses applications, en particulier en intelligence artificielle (IA), et a beaucoup été étudié des points de vue de l'IA comme de la complexité. Dans cet article, nous présentons un algorithme à la DPLL adapté aux problèmes d'abduction. En particulier, cet algorithme nous permet de proposer une approche heuristique pour ces problèmes, et de développer des techniques {\em ad hoc\/} d'élagage de l'arbre de recherche. \par Nous développons un prouveur, dédié aux problèmes d'abduction et baptisé {\tt zlas}, et nous proposons une comparaison de notre méthode à celle du projet QUIP, qui utilise une traduction en une formule booléenne quantifiée (QBF) pour résoudre ce type de problèmes. En plus du prouveur {\sc qbf} inclus dans QUIP, nous enrichissons les tests avec les meilleurs prouveurs {\sc qbf} actuels. Nous montrons que pour la plupart des tests proposés, notre algorithme permet d'améliorer significativement les résultats obtenus avec une modélisation en QBF.
Document type :
Conference papers
Complete list of metadata

Cited literature [31 references]  Display  Hide  Download

https://hal.inria.fr/inria-00150745
Contributor : Sylvain Soliman <>
Submitted on : Thursday, May 31, 2007 - 2:39:44 PM
Last modification on : Thursday, February 7, 2019 - 5:37:26 PM
Long-term archiving on: : Friday, September 21, 2012 - 4:00:53 PM

File

42.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00150745, version 1

Citation

Florian Letombe, Bruno Zanuttini. Une approche DPLL pour l'abduction. Troisièmes Journées Francophones de Programmationpar Contraintes (JFPC07), Jun 2007, INRIA, Domaine de Voluceau, Rocquencourt, Yvelines France, France. ⟨inria-00150745⟩

Share

Metrics

Record views

307

Files downloads

552