Abstract:
Dans ce mémoire, nous présentons un formalisme appelé problème de satisfaction de
contraintes distribué (CSP distribué) et des algorithmes de résolution de CSP distribué. Un
CSP distribué est un problème de satisfaction de contraintes dans lequel les variables et les
contraintes sont distribuées entre plusieurs agents. Divers problèmes d'application dans
l'intelligence artificielle distribuée peuvent être formalisés en tant que CSP distribué.
Nous présentons un algorithme appelée asynchrone backtracking qui permet aux agents d'agir
de manière asynchrone et concurremment sans aucun contrôle global, tout en garantissant
l'exhaustivité de l'algorithme. De plus, nous décrivons comment ce dernier peut être modifié en
un algorithme plus efficace appelé asynchronous weak-commitment search, qui peut réviser une
mauvaise décision sans recherche exhaustive en changeant l'ordre de priorité des agents de
manière dynamique.
Les résultats expérimentaux sur divers exemples de problèmes montrent que l'algorithme
asynchronous weak-commitment search est de loin plus efficace que l'algorithme de asynchrone
backtracking et peut résoudre des problèmes à grande échelle.
