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

• Tagged
• XML
• BibTex