Agile Asynchronous Backtracking for Distributed Constraint Satisfaction Problems

Abstract : Asynchronous Backtracking is the standard search procedure for distributed constraint reasoning. It requires a total ordering on the agents. All polynomial space algorithms proposed so far to improve Asynchronous Backtracking by reordering agents during search only allow a limited amount of reordering. In this paper, we propose Agile-ABT, a search procedure that is able to change the ordering of agents more than previous approaches. This is done via the original notion of termination value, a vector of stamps labelling the new orders exchanged by agents during search. In Agile-ABT, agents can reorder themselves as much as they want as long as the termination value decreases as the search progresses. Our experiments show the good performance of Agile-ABT when compared to other dynamic reordering techniques.
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00595688
Contributeur : Mohamed Wahbi <>
Soumis le : mercredi 25 mai 2011 - 23:04:57
Dernière modification le : jeudi 11 janvier 2018 - 06:26:23
Document(s) archivé(s) le : jeudi 30 mars 2017 - 10:38:14

Fichier

TechnicalReport_RR-11017.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-00595688, version 2

Collections

Citation

Christian Bessière, El Houssine Bouyakhf, Younes Mechqrane, Mohamed Wahbi. Agile Asynchronous Backtracking for Distributed Constraint Satisfaction Problems. RR-11017, 2011, pp.01-20. 〈lirmm-00595688v2〉

Partager

Métriques

Consultations de la notice

322

Téléchargements de fichiers

201