DisCSP

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

DisCSP est l'acronyme anglais pour DIStributed Constraint Satisfaction Problem. Il s'agit de la résolution de problème de satisfaction de contraintes distribué sur un réseau de machines[1]. Cette approche de résolution de problèmes est associée aux systèmes multi-agents. Chaque machine est représentée par un agent qui communique de manière asynchrone avec les autres afin de résoudre le problème. Le domaine est fortement lié à celui de l'optimisation combinatoire sous contraintes distribuées.

Le problème est distribué sur un ensemble d'agents qui sont responsables soit d'un ensemble de variables, soit d'un ensemble de contraintes, et qui communiquent entre eux. Il est résolu par des variantes des algorithmes permettant de résoudre les problèmes de satisfaction de contraintes, comme les algorithmes de backtracking adapté au contexte distribué, comme l'algorithme ABT (Asynchronous Backtracking)[2], ou des algorithmes de synchrones. Les étapes peuvent rester identiques aux algorithmes de résolution de problèmes classique, la propagation de contraintes, backjumping...

Notes et références[modifier | modifier le code]

  1. (en) Boi Faltings, Francesca Rossi, Peter Van Beek et Toby Walsh, « Distributed constraint programming », dans Handbook of constraint programming, Elsevier, (ISBN 978-0-444-52726-4), p. 701
  2. M. Yokoo, E. H. Durfee, T. Ishida et K. Kuwabara, « Distributed Constraint Satisfaction for Formalizing Distributed Problem Solving », Proceedings of the 12th ICDCS,,‎ , p. 614-621