TitleAsynchronous Backtracking without Adding Links: A new Member in the ABT Family
Publication TypeJournal Article
Year of Publication2005
AuthorsBessière C, Brito I, Maestre A, Meseguer P
JournalArtificial Intelligence
Volume161
Number1-2
Pagination7-24
Abstract

Following the pioneer work of Yokoo and colleagues on the ABT (asynchronous backtracking) algorithm, several ABT-based procedures have been proposed for solving distributed constraint networks. They di_er in the way they store nogoods, but they all use additional communication links between unconnected agents to detect obsolete information. In this paper, we propose a new asynchronous backtracking algorithm which does not need to add links between initially unconnected agents. To make the description simpler and to facilitate the comparisons between algorithms, we present a unifying framework from which the new algorithm we propose, as well as existing ones, are derived. We provide an experimental evaluation of these algorithms