Formation dynamique d’équipes dans les DEC-POMDPS ouverts à base de méthodes Monte-Carlo

« J’ai une politique très stricte de contrôle des armes à feu : s’il y a une arme à feu, je veux en avoir le contrôle. » Clint Eastwood  .

Capital City, États-Unis. Lorsque Morpheus lui propose de choisir entre la pilule bleue et la pilule rouge, Thomas A. Anderson, humble programmeur Américain dans une respectable entreprise de logiciels informatiques, sait qu’il se trouve face à la décision la plus importante de son existence. S’il choisit la pilule bleue, il oublie tout et se réveille chez lui, prêt à reprendre le cours de sa vie monotone, ignorant de la nature réelle des choses. S’il choisit la pilule rouge, alors il s’apprêtera à découvrir que le monde dans lequel il vit n’est en réalité pas tout à fait ce qu’il pensait.

Contexte

Si Matrix [Wachowskis, 1999] restera à jamais une œuvre marquante dans l’histoire du septième art, c’est notamment parce que le film comporte plusieurs scènes devenues cultes. Parmi celles-ci, la scène du choix entre la pilule bleue et la pilule rouge constitue l’une des séquences les plus mémorables du cinéma. Le choix fait par le héros à cet instant est crucial puisque derrière son apparence si simple vont découler des effets à long terme d’une ampleur considérable. La théorie de la décision [Binmore, 2008] est le domaine scientifique qui vise à décrire et à optimiser la capacité d’un agent à prendre ce genre de décisions où les conséquences futures doivent être prises en considération. Cette théorie se découpe en deux branches. D’une part, la théorie de la décision descriptive, qui vise à analyser pourquoi et comment les décisions sont prises. Autrement dit, cela revient à se demander pourquoi M. Anderson a choisi la pilule rouge. D’autre part, la théorie de la décision normative, qui s’occupe de déterminer les meilleures décisions à prendre compte tenu des informations imparfaites et incomplètes dont on dispose. Cette fois, cela revient à se demander quelle pilule M. Anderson aurait dû prendre. C’est de cette branche dont il sera question dans cette thèse.

Savoir prendre les bonnes décisions en analysant les conséquences futures de ses choix est un processus qui intervient quotidiennement dans de nombreuses situations : de l’astronaute qui doit être capable de réagir en quelques secondes lorsqu’une série d’alarmes se déclenche à bord de sa navette spatiale, à l’entraîneur sportif qui, depuis le bord du terrain, coordonne ses joueurs et leur donne continuellement les directives à suivre, en passant par la voiture autonome qui, percevant ce qui semble être un obstacle, doit décider de freiner brusquement ou non. Avec l’automatisation croissante des technologies dans de nombreux secteurs de l’industrie, est venue la nécessité de concevoir des systèmes fiables, sur lesquels on peut exercer un contrôle optimal. Malheureusement, au moins deux types de difficultés se présentent lorsqu’il s’agit de concevoir des systèmes capables de prises de décision autonomes. La première d’entre elles concerne l’incertitude liée au milieu dans lequel le système est implémenté. Imaginons une application militaire, où une flotte de drones autonomes est déployée sur un site sensible (par exemple, une zone de stockage d’armement nucléaire) dont elle doit en assurer la sécurité en signalant, le cas échéant, la présence d’unités ennemies. Les drones, équipés du matériel de défense nécessaire à la réussite de leur mission (caméras, radars, radios), survolent un périmètre, effectuent des rondes, envoient des messages d’alerte à un opérateur humain distant lorsqu’ils pensent avoir identifié une menace, ou décident de l’envoi d’un missile d’interception sol-air. Faire la différence entre un aéronef ennemi en approche du site surveillé et un aéronef qui ne représente pas une menace n’est pas toujours une tâche facile, surtout si l’aéronef ennemi tente délibérément de masquer sa présence et son identité. Suivant son altitude, ses messages radio ou encore sa vitesse de déplacement, il se peut que l’aéronef ennemi ne soit pas détecté en tant que tel par l’équipe de drones, pouvant ainsi mener à de graves brèches de sécurité. Inversement, attaquer un aéronef allié n’est évidemment pas souhaitable. L’incertitude induite par l’inexactitude des capteurs des drones peut également être un facteur rendant difficile la tâche de surveillance. Ces différentes formes d’incertitude sur l’environnement peuvent mener la flotte de drones à prendre des décisions non-optimales (signalements de faux positifs ou de faux négatifs).

La seconde difficulté qui émerge lorsque l’on conçoit un système autonome composé de plusieurs unités de calculs (comme c’est le cas dans cet exemple de drones de surveillance), est de réussir à coordonner efficacement les unités (ou agents) pour que le comportement global de l’équipe soit optimal. Pour des raisons de sécurité, les communications entre les drones peuvent être réduites au minimum, voire complètement interdites. Les drones doivent ainsi s’organiser pour ne pas que l’un empiète sur la zone de surveillance de l’autre, mais également pour qu’il n’y ait pas de zone hors de surveillance à un instant donné. En l’absence de communications, cette synchronisation doit avoir lieu en amont de l’exécution de la mission, de telle sorte que chaque agent sache quoi faire sans avoir besoin de savoir ce que font les autres agents au même moment. De plus, planifier pour un grand nombre d’agents devient vite un problème théorique complexe, puisque le nombre de stratégies possibles pour l’équipe sur le terrain va augmenter exponentiellement avec le nombre d’agents.

Définitions générales 

« Nous ne pourrons pas tout faire dans les cent premiers jours. Ni dans les mille premiers jours, ni pendant toute la durée de notre mandat, ni même peut-être pendant toute notre vie sur cette planète. Mais commençons ! » John Fitzgerald Kennedy 20 janvier 1961 .

Concepts de base

Le principal objectif de cette thèse consiste à construire un modèle pour planifier les entrées et sorties d’agents attelés à la résolution d’une tâche. On peut voir ce modèle comme un coach de basket-ball. Depuis le bord du terrain, il coordonne son équipe, donne les directives à suivre et, chose qui nous intéresse tout particulièrement, s’occupe du coaching, c’est-à-dire, décide quel joueur doit entrer sur le parquet et quel autre doit sortir à tel ou tel moment du match. Cette question, souvent ignorée, comme nous allons le voir, dans le domaine de la planification multiagents, revêt une importance primordiale puisque l’équipe en place doit s’adapter à la situation pour pouvoir être efficace. Imaginons que l’un des joueurs performe en-deçà de ses capacités car il joue contre un adversaire qui parvient à le contenir efficacement. Le coach doit intervenir et procéder soit à un changement de position, soit à un changement de joueur s’il veut optimiser les chances de victoire de son équipe. Mais avant d’aborder le problème des entrées et sorties d’agents dans un système, il nous faut tout d’abord commencer avec certaines notions essentielles à la compréhension de cette thèse. En premier lieu, qu’est-ce qu’un agent ? Ensuite, qu’est-ce-que ce système dans lequel cet agent évolue ? Après avoir donné ces définitions primordiales à l’étude de notre sujet, nous aborderons la question de la planification, et la place qu’elle occupe dans le domaine de l’intelligence artificielle.

Agents

Un agent est une entité qui interagit avec son environnement [Russell and Norvig, 2009]. L’interaction se fait de deux façons : d’une part, l’agent reçoit des informations de l’environnement. Ce sont ce que l’on appelle des perceptions, ou observations. Il les reçoit via ses capteurs. D’autre part, l’agent agit sur l’environnement par le biais d’actions. Il utilise pour cela ses actionneurs. Les actions que l’agent choisit d’effectuer sont dépendantes de ses perceptions et de son modèle de raisonnement interne.

Les exemples d’agents sont nombreux. Un joueur de basket-ball est un agent. Il reçoit des informations sur ce qu’il se passe sur le parquet via des signaux lumineux, sonores ou tactiles perçus par ses yeux, ses oreilles ou sa peau, et il agit sur son environnement avec ses mains, ses jambes ou sa voix pour effectuer une passe, une feinte, un appel de ballon, etc. Un drone de surveillance est également un agent. Il peut disposer d’une caméra noir et blanc et d’un laser pour effectuer des observations, et il peut agir sur son environnement en émettant des signaux radiophoniques pour communiquer avec sa centrale de sécurité. Une entreprise commerciale aussi est un agent. Elle observe les prix et les produits du marché ainsi que ses compétiteurs, et décide d’actions commerciales, de lancements de produits, d’une éventuelle entrée en bourse, etc., modifiant ainsi l’écosystème économique. Dans le domaine de la recherche en informatique, qui nous intéresse plus particulièrement ici, le terme d’agent permet de désigner de façon générique une unité dotée d’un certain degré d’autonomie et de capacités de calculs, d’une forme de raisonnement.

Un système multi-agents [Wooldridge, 2009] est une extension directe aux cas où plusieurs agents peuplent le système. Chaque agent est une unité indépendante qui dispose de ses propres capteurs et actionneurs, et qui prend donc ses propres décisions suivant un raisonnement interne. Au sein d’un système multi-agents, les agents peuvent être de différents types. Des agents coopératifs agissent dans un but commun. Ils cherchent à résoudre la même tâche de la meilleure façon possible. Par exemple, on peut représenter une équipe sportive comme un système multi-agents coopératif dont le but est de remporter le match. Des agents compétitifs en revanche ont des buts distincts et, le plus souvent, contradictoires. On peut également rencontrer des systèmes hybrides, où certains agents sont coopératifs entre eux mais en compétition avec d’autres. La modélisation d’une situation par un système multi-agents dépend à la fois du domaine étudié et du point de vue adopté. Par exemple, cinq joueurs des Chicago Bulls peuvent être vus comme cinq agents coopératifs, mais du point de vue d’un match entre les Chicago Bulls et les Los Angeles Lakers, il est nécessaire de considérer les cinq joueurs des Lakers comme des agents appartenant également au système, faisant ainsi de ce dernier un système hybride. Si l’on adopte un regard encore différent sur cette même situation, on peut aussi voir le match entre les Bulls et les Lakers comme une compétition entre deux agents, où chaque équipe, et non pas chaque joueur, est un agent.

Un système multi-agents ouvert [Nodine and Unruh, 1997,Eijk et al., 1999] est un système où les agents peuvent entrer et sortir à leur gré, ou sous certaines conditions. S’il n’est pas ouvert, il est dit fermé. Les agents dans un système multi-agents ouvert doivent tenir compte du fait que d’autres agents (coopératifs ou compétitifs) peuvent entrer ou sortir à tout moment. Ils doivent donc disposer de moyens leur permettant de réagir à de telles entrées/sorties. Par exemple, et parlons football plutôt que basket-ball cette fois, si un joueur se blesse en plein match, il va être soigné sur le bord du terrain en attendant de savoir s’il pourra retourner jouer ou s’il devra être remplacé. Pendant son absence, son équipe devra évoluer à dix contre onze et probablement adopter une stratégie de jeu plus défensive. S’il advient que le joueur peut regagner le terrain, alors son équipe pourra retrouver son style de jeu antérieur. S’il se trouve toutefois qu’un nouveau joueur doit le remplacer, alors il faudra peut-être que le schéma tactique de l’équipe change pour s’adapter aux spécificités du joueur remplaçant. Toutefois, la sortie ou l’entrée d’un agent n’est pas toujours contrainte, elle peut également être choisie : un pompier dont les ressources en eau sont épuisées a tout intérêt à quitter momentanément le système pour recharger ses réserves et revenir combattre le feu plus tard.

Table des matières

I Introduction
1 Introduction
1.1 Contexte
1.2 Thèse
1.3 Sommaire
II État de l’art
2 Définitions générales
2.1 Concepts de base
2.1.1 Agents
2.1.2 Rationalité
2.1.3 Environnement
2.2 Planification
2.2.1 Mesure de performance
2.2.2 Résolution
2.3 Conclusion
3 Planification sous incertitude
3.1 Introduction
3.2 Processus décisionnels de Markov
3.2.1 Définition du modèle
3.2.2 Exemple
3.2.3 Politiques
3.2.4 Principe d’optimalité
3.3 Observabilité partielle
3.3.1 Définition du modèle
3.3.2 État de croyance
3.3.3 Belief MDP
3.3.4 Complexité
3.4 Contrôle décentralisé
3.4.1 Définition du modèle
3.4.2 Historiques et politiques
3.4.3 Complexité
3.4.4 Méthodes de résolution
3.5 Conclusion
4 Équipes flexibles
4.1 Introduction
4.2 Allocation de rôles
4.2.1 Problème d’affectation
4.2.2 Modèle de décision pour l’allocation de rôles
4.2.3 Stratégies de ré-allocation de rôles
4.3 Formation de coalitions
4.3.1 Définitions
4.3.2 Propriétés
4.4 Contrôle partiel de systèmes multi-agents ouverts
4.4.1 Travail d’équipe ad-hoc
4.4.2 Agents non dévoués
4.5 Conclusion
III Modèles
5 POMDPs décentralisés & ouverts
5.1 Introduction
5.2 Vers un DEC-POMDP ouvert
5.2.1 Le problème TARS
5.2.2 Analyse de benchmarks
5.3 DEC-POMDPs ouverts
5.3.1 Définition du modèle
5.3.2 Niveaux de contrôle du processus d’entrées et sorties
5.3.3 Coûts des transitions d’équipes
5.3.4 Historiques, politiques et résolution
5.3.5 Avantages et inconvénients
5.4 L’algorithme BRD
5.4.1 Équilibre de Nash
5.4.2 Best Response Dynamics
5.4.3 Sélection des agents
5.5 L’algorithme POS-UCT
5.5.1 Présentation
5.5.2 Recherche arborescente Monte-Carlo dans les domaines partiellement observables
5.5.3 Historiques rares
5.6 Conclusion
6 Éléments de théorie des jeux pour le problème de formation dynamique d’équipes sous incertitude
6.1 Introduction
6.2 POMDP d’équipes
6.2.1 Définition du modèle
6.2.2 Historiques et politiques partiels
6.3 Propriétés structurelles
6.3.1 Concepts de base
6.3.2 Monotonie, suradditivité et convexité
6.3.3 Illustrations
6.3.4 Complexité algorithmique
6.4 Indices de pouvoir
6.4.1 Utilité différentielle
6.4.2 Le système de classement Elo
6.4.3 Matchs
6.4.4 Volatilité et stabilité
6.5 L’algorithme MELO
6.5.1 Recherche arborescente Monte-Carlo avec classement Elo
6.5.2 Matchs des meilleures équipes
6.5.3 Justification des classements Elo
6.5.4 Séparabilité
6.6 Conclusion
IV Évaluation expérimentale
V Conclusion

Lire le rapport complet