Improving Asynchronous Backtracking for Dealing with Complex Local Problems - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2004

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.
Fichier principal
Vignette du fichier
ecai04.pdf (76.31 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

lirmm-00108867 , version 1 (12-10-2019)

Identifiers

  • HAL Id : lirmm-00108867 , version 1

Cite

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

Share

Gmail Facebook X LinkedIn More