DisCSP

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


DisCSP est l'acronyme anglais pour DIStributed Constraint Satisfaction Probem. 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]

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

  1. (en) Boi Faltings, « Distributed constraint programming », dans Francesca Rossi, Peter Van Beek, Toby Walsh, Handbook of constraint programming, Elsevier,‎ 2006 (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,,‎ 1992, p. 614-621