Méthodes avancées de génération de structures de coalitions dans les systèmes multi-agents.

Abstract

La génération de structures de coalitions est une problématique de recherche importante dans les systèmes multi-agents (SMA). Elle consiste à diviser l’ensemble des agents en sous-ensembles disjoints appelés coalitions, de manière à maximiser le gain. Trouver la structure de coalitions optimale est un problème NP-complet qui est donc difficile à résoudre, même avec des hypothèses assez restrictives. Cela a motivé les chercheurs à développer divers algorithmes déterministes et ap- proches heuristiques pour résoudre efficacement le problème. Dans ce mémoire, nous avons d’abord proposé une nouvelle représentation de l’espace de recherche basée sur le graphe des partitions. Ensuite, nous avons développé une approche heuristique innovante et efficace pour rechercher ef- ficacement l’espace des structures de coalitions afin de trouver une solution proche de l’optimum dans un temps court. Notre technique d’énumération des structures de coalitions (CSE), qui com- bine une heuristique originale et une nouvelle représentation de l’espace de recherche, offre une nouvelle façon d’explorer le graphe des partitions en calculant directement les structures de coali- tions. L’analyse des performances de notre approche montre son efficacité en termes de temps et de qualité des solutions trouvées par rapport à l’algorithme exact le plus rapide, à savoir ODP-IP. Nous avons ensuite développé un algorithme imparfait (ADP) basé sur deux observations sur les valeurs des coalitions. Cet algorithme fournit la solution optimale pour plus de 97% des cas avec un gain de temps pouvant atteindre 300 secondes pour 25 agents. Nous avons ensuite présenté un problème négligé des algorithmes existants, à savoir leurs besoins en mémoire, et proposé notre troisième algorithme pour faire face à ce problème majeur. Notre algorithme fournit des solutions de haute qualité avec un gain de temps qui avoisine les 100 % tout en ne nécessitant que moins de 1 % de la mémoire requise par les algorithmes existants (0,02 % pour 26 agents).