Supervision : Amal EL FALLAH SEGHROUCHNI

Co-supervision : PECHANSKI Frédéric

Contributions à la résolution de problèmes d'optimisation de contraintes distribuées dynamiques à l'aide de modèles graphiques pour la coordination multiagents

Les systèmes informatiques sont de plus en plus autonomes et couplés. Le contrôle de leur comportement nécessite le développement d'algorithmes dédiés prenant en compte simultanément les problèmes de décision auxquels ceux-ci ont à faire face ainsi que l'architecture distribuée sous-jacente de ces systèmes. Ce domaine est celui de la coordination de systèmes multiagents. Les systèmes multiagents sont persistants, ouverts et doivent gérer des problèmes évoluant dynamiquement tout en garantissant leur comportement dans un contexte opérationnel incertain. En tant que système artificiel, il est souhaitable qu'une procédure de coordination garantisse l'optimalité des décisions. En tant que système réel, il est souhaitable qu'une solution soit trouvée le plus rapidement possible. En tant que programme informatique distribué, il est souhaitable que la procédure de coordination soit capable de s'adapter à la modification dynamique du système ainsi que d'exploiter le parallélisme. Nous abordons le problème de la coordination multiagents modélisé en tant qu'un problème d'optimisation de contraintes distribué dynamique (DynDCOP), et où nous utilisons les modèles graphiques comme mécanismes de base pour résoudre ceux-ci. Notre démarche consiste à étendre ces approches pour les adapter aux contraintes d'exécution des systèmes multiagents. Nous proposons trois contributions. La première est un algorithme approché avec garanties qui permet de réaliser un compromis paramétrable entre optimalité et décentralisation de la résolution. La seconde contribution est un algorithme adaptant la création du modèle graphique aux ressources du système multiagents (structure du réseau de communication, bande passante des liens de communication et vitesse de calcul des agents) et à l'ordonnancement des calculs sur celui-ci. Enfin dans notre troisième contribution nous proposons un algorithme de clusterisation partielle paramétrable permettant, pour un temps maximal d'inférence donné, d'exploiter à la fois la réactivité des modèles graphiques cycliques et la qualité des solutions des modèles graphiques acycliques.

2009-2011 Publications

• 2011
  • N. Stefanovitch, A. El Fallah‑Seghrouchni : “Partially Decentralised Junction Trees for Quality Guaranteed Approximate Coordination in Open Multi-agent Systems with Optimality/Runtime Trade-Off”, International Conference on Intelligent Agent Technology, Lyon, France, pp. 377-380, (IEEE) (2011)
  • N. Stefanovitch, A. El Fallah‑Seghrouchni : “Arbres de jonction dynamiques décentralisés”, Modèles formels de l'interaction, MFI'11, Rouen, France (2011)
  • N. Stefanovitch, A. Farinelli, A. Rogers, N. Jennings : “Resource-Aware Junction Trees for Efficient Multi-Agent Coordination”, International Conference on Autonomous Agents and Multiagent Systems, Taipei, Taiwan, Province of China, pp. 363-370 (2011)
• 2010
  • N. Stefanovitch : “Contributions à la résolution de problèmes d’optimisation de contraintes distribuées dynamiques à l’aide de modèles graphiques pour la coordination multiagents”, thesis, phd defence 10/22/2010, supervision El fallah seghrouchni, Amal, co-supervision : Pechanski, Frédéric (2010)
  • N. Stefanovitch, A. Farinelli, A. Rogers, N. Jennings : “Efficient Multi-Agent Coordination Using Resource-Aware Junction Trees (extended abstract)”, International Conference on Autonomous Agents and Multiagent Systems, Toronto, ON, Canada, pp. 1413-1414 (2010)
• 2009
  • N. Stefanovitch, A. El Fallah‑Seghrouchni, F. Peschanski : “Towards Efficient Coordination in Open MAS using Graphical Utility Models”, International Workshop on Optimisation in Multi-Agent Systems, Budapest, Hungary (2009)
  • N. Stefanovitch : “­Efficient Recomputation of Social Welfare in Open MAS using Graphical Models”, The International Workshop on Multi-Agent Systems Technology and Semantics, Bucharest, Romania (2009)