DisCSP

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, le retour sur trace non chronologique (backjumping)...