TitleLa famille ABT
Publication TypeConference Paper
Year of Publication2002
AuthorsBessière C, Maestre A, Meseguer P
EditorAutomatique INational d
Conference Name8èmes Journées Nationales sur la Résolution Pratique de Problèmes NP-Complets, JNPC´02
PublisherInstitut National de Recherche en Informatique et en Automatique
Pagination57-67
Abstract

Depuis quelques années, la communauté IA affiche un intérêt croissant pour la résolution de problèmes distribuées. Dans le domaine du raisonnement par constraintes distribuées, plusieurs procédures de recherche arborescente ont été proposées pour trouver une solution dans un réseau de contraintes. Elles se distinguent par la manière dont elles mémorisent les combinaisons de valeurs infructueuses (nogoods) et par les méthodes qu´elles mettent en oevre pour détecter l´obsolescence potentielle des données mémorisées. Dans cet article, nous proposons un cadre unificateur pour ces algorithmes de recherche asynchrones. Nous étudions les choix qui peuvent être faits pour obtenir un algorithme correct et complet. Notre cadre permet de décrire et de comprendre les éléments de base de ces procédures, et de mettre en relief leurs similarités et leurs différences.