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 metadatas

Cited literature [21 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00108867
Contributor : Christine Carvalho de Matos <>
Submitted on : Saturday, October 12, 2019 - 5:01:14 PM
Last modification on : Thursday, May 14, 2020 - 6:58:06 PM
Long-term archiving on: : Monday, January 13, 2020 - 1:21:15 PM

File

ecai04.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-00108867, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

127

Files downloads

12