DokuWiki

Voir la thèse p78 : https:tel.archives-ouvertes.fr/file/index/docid/362529/filename/these_matignon.pdf ==== Définitions ==== * Agent : Un agent est une entité capable de : percevoir, au moins partiellement, son environnement, agir sur son environnement, décider de manière autonome, communiquer avec d'autres agents. * SMA : Un SMA est composé d'agents qui interagissent entre eux. * Emergence : Les SMA orientés émergence considèrent des ensembles d'agents autonomes interagissant pour résoudre un problème donné dont la difficulté est au-delà de leurs capacité ou connaissances individuelles. * Kénétique : Désigne la science qui étudie les organisations artificielles et les interactions entre entités, qu'elles soient informatiques, physique, biologiques... * Situation de coopération : Lorsque des agents ont des objectifs compatibles mais que les ressources ou les compétences d'un ou plusieurs agents sont insuffisantes. * Observalité : L'observalité d'un environnement caractérise l'ensemble des informations qui sont accessibles à un agent. * Observalité partielle : L'observalité est partielle quand toutes les informations nécessaires à la connaissance de l'état du système ne sont pas accessibles. * Jeu matriciel : n-uplet <m, A1, ..., Am, R1, ..., Rm> dans lequel m est le nombre d'agents (joueurs), Ai est l'ensemble des action pour le joueur i, Ri est la fonction de récompense pour l'agent i qui dépend de l'action jointe des agents. * Stratégie : Fonction π : Ai -> [0; 1] qui définit une distribution de probabilité sur les actions du joueur i. * Stratégie pure : Stratégie déterministe. * Stratégie mixte : Stratégie non déterministe. * Gain espéré : Esperance de récompense étant donné la stratégie de l'agent i et celle des autres agents. * Equilibre de Nash : Une stratégie jointe est un équilibre de Nash lorsque chaque joueur ne peut améliorer son gain en changeant de stratégie (chaque joueur suit une stratégie “égoïste” => pas forcément très efficace). * Optimum de Pareto : Une stratégie domine au sens de Pareto si tous les joueurs gagnent au moins autant qu'en suivant leur stratégie dominante et qu'au moins un joueur ai un gain supérieur à ce qu'il recevrait en suivran sa stratégie dominante. * Pareto Optimal : Si la stratégie jointe n'est dominée par aucune autre stratégie. * MMDP : Processus décisionnels de Markov multi-agents. Définit par un n-uplet <m, S, A1, ..., Am, T, R> où S, A, et T sont définis comme pour un jeu de Markov. * DEC-POMDP : Processuss décisionnel de Markov décentralisé partiellement observable. Définit par un n-uplet <m, S, A1, ..., Am, T, Ω1, ..., Ωm, O, R> où le n-uplet <m, S, A1, ..., Am, T, R> est un jeu de Markov, Ω est l'ensemble des observations oi de l'agent i, O est une fonction d'observation définissant une distribution de probabilité sur les actions et observations jointes. ==== Généralités sur les SMA ==== Les états, actions et fonctions de récompense d'un PDM (processus décisionnel de Markov) peuvent être défini à 2 niveaux : * niveau global : observation de la dynamique globale du système, observation de l'avancement de la résolution du problème. * niveau local : les agents perçoivent leur environnement et prennent leur décisions. Problème de distribution des récompenses : Objectif est défini de manière globale, la récompense peut-être définie par une fonction commune à tous les agents selon l'état global et les actions jointes. Deux possibilités : * La récompense peut être distribuée individuellement à chaque agent (tout en dépendant des actions jointe, maximiser ses satisfactions individuelles ne conduit pas forcément à maximiser celle du groupe) * Distribuer une récompense globale et laisser les agents décider eux-même dans quelle mesure leur comportement a participé à la résolution du problème. Définir les politiques individuelles : * Architecture centralisée : un contrôleur central dispose de l'état global du système, des actions jointes, des récompenses. Il calcule la politique jointe et distribue les commandes individuellement parmi les agents. Avantages/Inconvénients : * +Nombre limité d'unités de contrôles nécessaire * +Pas de mécanisme de coordination inter-agent * -Peu robuste * -Difficilement modifiable (pas de modularité) * Architecture décentralisée (architecture hétérarchique) : chaque agent construit sa propre politique à partir de ses connaissances. Avantages/Inconvénients : * +Meilleure modularité * +Meilleure robustesse * -Perception partielle * -Communication inter-agent * -Coordination inter-agent ==== Jeux matriciels ==== Types de jeux matriciels : * Jeu d'équipe : Tous les joueurs ont la même fonction de récompense. * Jeu à somme nulle : La somme des fonctions de récompense de tous les joueurs est nulle. * Jeu à somme générale : N'est ni un jeu d'équipe ni un jeu à somme nulle Théorème : Tout jeu en forme stratégique fini admet au moins un équilibre de Nash. ==== Jeux de Markov ==== MMDP = spécialisation du jeu de Markov dans laquelle la fonction récompense est la même pour tous les agents.