Résolution de problèmes distribuée
La résolution de problèmes distribuée étudie comment un problème peut être résolu par plusieurs agents, chacun détenant une partie de l'information ou de la responsabilité, qui communiquent et combinent leurs résultats partiels pour former une solution globale.
Definition
La résolution de problèmes distribuée est la solution coopérative d'un problème par un groupe d'agents, chacun possédant des connaissances locales ou des sous-problèmes, qui se coordonnent par la communication pour produire une solution globale cohérente.
Scope
Ce domaine couvre la résolution coopérative de problèmes par des agents ne partageant pas de contrôleur central : le partage de tâches et de résultats, la satisfaction et l'optimisation de contraintes distribuées (DCSP/DCOP) avec des algorithmes tels que le retour arrière asynchrone, et la coordination de solutions partielles sous des contraintes de communication et de confidentialité. Il aborde la manière dont la décomposition, le calcul local et le passage de messages produisent des solutions globalement cohérentes. L'interaction purement compétitive et la conception d'incitations sont traitées dans le cadre de la théorie des jeux et de la conception de mécanismes.
Core questions
- Comment un problème est-il décomposé et distribué entre des agents ayant des vues partielles ?
- Comment les agents partagent-ils les tâches et les résultats intermédiaires pour construire une solution globale ?
- Comment un problème de contraintes est-il résolu lorsque les variables et les contraintes sont réparties entre les agents ?
- Comment l'équilibre est-il trouvé entre le coût de communication et l'autonomie locale par rapport à la qualité de la solution ?
Key concepts
- décomposition de problèmes
- partage de tâches et partage de résultats
- satisfaction de contraintes distribuées (DCSP)
- optimisation de contraintes distribuées (DCOP)
- retour arrière asynchrone
- passage de messages
- autonomie locale et confidentialité
- cohérence globale
Key theories
- Satisfaction et optimisation de contraintes distribuées
- La satisfaction de contraintes distribuées (DCSP) et l'optimisation de contraintes distribuées (DCOP) généralisent les problèmes de contraintes à des contextes où les variables et les contraintes sont détenues par différents agents, résolus par des algorithmes dans lesquels les agents échangent de manière asynchrone des affectations de valeurs et des informations de conflit.
- Partage de tâches et partage de résultats
- La résolution coopérative de problèmes distribuée procède par la décomposition et la distribution de tâches et par l'échange de résultats partiels que les agents intègrent, permettant à un groupe de résoudre des problèmes qu'aucun agent seul ne pourrait résoudre.
- Recherche distribuée asynchrone
- Des algorithmes tels que le retour arrière asynchrone permettent aux agents de rechercher une affectation globale cohérente sans contrôle central, en utilisant le passage de messages priorisés pour résoudre les conflits tout en préservant l'autonomie locale.
Clinical relevance
La résolution de problèmes distribuée s'applique à la surveillance et au suivi multi-capteurs, à la planification distribuée et à la coordination de réunions, à la gestion des réseaux électriques et du trafic, et à tout contexte où les données ou les responsabilités sont naturellement réparties entre des agents qui doivent trouver conjointement une solution cohérente tout en limitant la communication.
History
La résolution coopérative de problèmes distribuée fut un thème fondateur de l'IA distribuée, illustrée par les travaux des années 1980 sur les réseaux de capteurs distribués et les systèmes à tableau noir (blackboard systems). Yokoo et ses collègues ont formalisé la satisfaction de contraintes distribuées dans les années 1990, et l'optimisation de contraintes distribuées est devenue par la suite un cadre majeur pour la prise de décision multi-agents coopérative.
Key figures
- Edmund H. Durfee
- Victor R. Lesser
- Makoto Yokoo
- Daniel D. Corkill
Related topics
Seminal works
- yokoo1998
- durfee1989
Frequently asked questions
- En quoi la résolution de problèmes distribuée diffère-t-elle du calcul parallèle ?
- Le calcul parallèle divise généralement un problème entre des processeurs sous contrôle central pour accélérer l'exécution. La résolution de problèmes distribuée suppose des agents autonomes avec leurs propres connaissances locales et éventuellement des contraintes de confidentialité ou de communication ; le défi est donc la coordination et l'atteinte d'une solution cohérente, et non seulement la vitesse.
- Qu'est-ce qu'un problème d'optimisation de contraintes distribuées ?
- C'est un problème de contraintes dans lequel les variables et les contraintes sont détenues par différents agents, et les agents doivent attribuer coopérativement des valeurs pour optimiser un objectif global (tel que la minimisation du coût total) tout en ne communiquant que localement. Il modélise de nombreuses tâches de coordination coopérative entre agents.