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.
Type de document :
Communication dans un congrès
Troisièmes Journées Francophones de Programmationpar Contraintes (JFPC07), Jun 2007, INRIA, Domaine de Voluceau, Rocquencourt, Yvelines France, France. 2007, JFPC07
Liste complète des métadonnées

Littérature citée [31 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00150745
Contributeur : Sylvain Soliman <>
Soumis le : jeudi 31 mai 2007 - 14:39:44
Dernière modification le : mardi 24 avril 2018 - 01:44:44
Document(s) archivé(s) le : vendredi 21 septembre 2012 - 16:00:53

Fichier

42.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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. 2007, JFPC07. 〈inria-00150745〉

Partager

Métriques

Consultations de la notice

234

Téléchargements de fichiers

481