HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 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 Connect in order to contact the contributor
Submitted on : Thursday, May 31, 2007 - 2:39:44 PM
Last modification on : Wednesday, October 20, 2021 - 9:58:17 AM
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

128

Files downloads

418