Skip to Main content Skip to Navigation
Journal articles

Asynchronous Backtracking Without Adding Links: A New Member in the ABT Family

Abstract : Following the pioneer work of Yokoo and colleagues on the ABT (asynchronous backtrack-ing) algorithm, several ABT-based procedures have been proposed for solving distributed constraint networks. They differ 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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [16 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00105347
Contributor : Christine Carvalho de Matos <>
Submitted on : Saturday, October 12, 2019 - 5:09:49 PM
Last modification on : Monday, November 16, 2020 - 4:26:03 PM
Long-term archiving on: : Monday, January 13, 2020 - 2:12:05 PM

File

aij05-abt.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Christian Bessière, Arnold Maestre, Ismel Brito, Pedro Meseguer. Asynchronous Backtracking Without Adding Links: A New Member in the ABT Family. Artificial Intelligence, Elsevier, 2005, 161 (1-2), pp.7-24. ⟨10.1016/j.artint.2004.10.002⟩. ⟨lirmm-00105347⟩

Share

Metrics

Record views

221

Files downloads

93