Improving Asynchronous Backtracking for Dealing with Complex Local Problems - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Communication Dans Un Congrès Année : 2004

Improving Asynchronous Backtracking for Dealing with Complex Local Problems

Résumé

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
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

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

Identifiants

  • HAL Id : lirmm-00108867 , version 1

Citer

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 Consultations
19 Téléchargements

Partager

Gmail Facebook X LinkedIn More