Skip to Main content Skip to Navigation
Conference papers

Improving Asynchronous Backtracking for Dealing with Complex Local Problems

Abstract : Distributed constraint satisfaction, in its most general acceptation, involves a collection of agents solving local constraint satisfaction subproblems, and a communication protocol between agents, in order to allow the distributed system converge to a global solution. The literature, however, often concentrates on the reduction where each agent owns exactly one variable, under the rationale that the corresponding algorithms are easily extended to the most general case. While this is mostly true, the specificities of agents handling local CSPs give way to numerous improvements, since a trade-off becomes possible between local and distributed search effort. In this paper, we seek to improve nogood learning and solver cooperation in multi-variables distributed constraint satisfaction problems. We propose incremental improvements to be implemented on top of an ABT-like algorithm, and make experimental evaluations of the performance improvement they bring.
Document type :
Conference papers
Complete list of metadata

Cited literature [21 references]  Display  Hide  Download
Contributor : Christine Carvalho De Matos Connect in order to contact the contributor
Submitted on : Saturday, October 12, 2019 - 5:01:14 PM
Last modification on : Friday, August 5, 2022 - 3:02:57 PM
Long-term archiving on: : Monday, January 13, 2020 - 1:21:15 PM


Files produced by the author(s)


  • HAL Id : lirmm-00108867, version 1



Arnold Maestre, Christian Bessière. Improving Asynchronous Backtracking for Dealing with Complex Local Problems. ECAI: Europeen Conference on Artificial Intelligence, Aug 2004, Valencia, Spain. pp.206-210. ⟨lirmm-00108867⟩



Record views


Files downloads