Résolution des problèmes de satisfaction de contraintes distribués (DisCSP) par les systèmes muti-agents (SMA)

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.