Apprentissage interactif et Coordination d’agents Mémoire de fin d’étude Master Informatique option IA & Multimédia PHAM PHUONG THAO Encadrant ALEXIS DROGOUL Laboratoires L’équipe MSI- IFI à Hanoi Laboratoire Géodes au Centre IRD à Bondy Hanoi Août 2009 1 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Remerciements Je tiens tout d’abord à remercier Alexis Drogoul pour m’avoir proposé ce sujet et pour son encadrement dévoué durant tout mon stage. Mes remerciements vont aussi à Chu Thanh Quang et Vo Duc An du laboratoire MSI pour leur support, leur aide chaleureuse et les documents qu’ils m’ont fournis. Merci à Patrick Taillandier et Bertrand Chaussat pour leurs conseils et leur aide sur les SIG. Je remercie tous mes camarades de la promotion 13 pour leur amitié et leur support pendant les deux années passées à l’IFI.
Je souhaite remercier ma mère, ma sœur et également la famille de Fabrice pour leur soutien, leur attention et pour m’avoir encouragé tout au long de mes études et de mon stage, à Hanoi et à Bondy. Enfin, je voudrais remercier particulièrement Fabrice Trillaud pour son aide précieuse et son soutien de chaque instant. 2 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Résumé Le projet AROUND (Autonomous Robots for Observation of Urban Networks after a Disaster), un des projets principaux du laboratoire MSI à l’IFI, se propose de concevoir et d’implémenter un système complet d’aide à la décision en temps-réel pour la gestion des catastrophes naturelles en milieu urbain. Mon stage se concentre sur l’augmentation du réalisme de la simulation AROUND, en implémentant la coordination entre les agents pour gérer les conflits, et en améliorant les comportements d’apprentissage en ligne.
Il s’intéresse aussi à l’initialisation de la simulation à partir de scénarios réalistes. Pour gérer les conflits dans la prise de décision des agents, j’ai proposé deux approches : le modèle centralisé et le modèle décentralisé. Pour améliorer l’apprentissage en ligne des agents, j’ai implémenté un mécanisme de diffusion de connaissances par la communication. Mots-clés : Apprentissage interactif, décision multi-critères, fonction d’utilité, système d’aide à la décision, coordination entre les agents.
Abstract The project AROUND (Autonomous Robots for Observation of Urban Networks after a Disaster), one of the principal and important projects of the laboratory MSI at IFI, intend to conceive and implement a complete decision support system in real time for managing the natural catastrophe in the urban area. My work focuses on increasing the realism of the simulation AROUND, by implementing the coordination between the agents to manage conflicts, and by improving on-line learning behaviors. I also worked on the simulation’s initialization, based on realistic scenarios. To manage the conflicts between the decisions taken by different agents, I proposed two approaches: the centralized model and the decentralized model.
To improve the on-line learning, I built a learning diffusion mechanism through communication. Keywords: Interactive learning, multi-criteria decision, utility function, decision support system, coordination between agents. 3 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Table des matières Remerciements. 3 Table des matières.
4 Table des figures. 6 Liste des tableaux. Objectif du stage. Modèle AROUND-RESCUE.
Coordination entre les agents dans le système de secours en cas de catastrophe. Problème de coordination. Technique de coordination commune. Echange de méta-information.
Planification Multi-Agent. Problème de coordination dans AROUND-RESCUE. Deux modèles proposés pour gérer les conflits dans AROUND-RESCUE. Modèle de décision décentralisée.
Modèle de décision centralisée. Comparaison des temps d’exécution. Comparaison de la gestion de conflits. Apprentissage interactif dans le système multi-agents.
Problème de l’apprentissage dans AROUND-RESCUE. Fonction d’utilité et ensemble de critères de décision. Apprentissage interactif par le modèle de « préférence additive ». Limites de l’existant.
Approche pour le partage intelligent de connaissance entre les agents. Implémentation de l’action de décision dans GAML. Critères « collectifs » de décision des agents dans AROUND-RESCUE. 39 4 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.
Diffusion et partage de connaissance. Exécution de la nouvelle action « choose ». Comparaison de la performance des deux actions « choose » dans GAML. Comparaison de la performance avec des zones de diffusion différentes.
Comparaison les méthodes d’initialisation de fonction d’utilité. Conclusion et perspectives. 54 5 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Table des figures Figure 1 : L’interface de la simulation AROUND-RESCUE. 9 Figure 2 : L’indicateur « Victims ».
12 Figure 3 : L’indicateur « Fires ». 13 Figure 4 : Conflits entre les ambulances dans le modèle de VO Duc An. 20 Figure 9 : Le temps total nécessaire (en millisecondes) pour charger et sauver les victimes. 28 Figure 10 : Le temps total nécessaire (en cycles de simulation) pour charger et sauver les victimes dans les deux modèles de décision.
29 Figure 11 : L’indicateur du nombre de victimes sur le terrain, mortes, dans l’ambulance et à l’hôpital. 30 Figure 12 : Volume de communication entre les agents dans AROUND-RESCUE. 31 Figure 13 : Un exemple de conflits dans AROUND-RESCUE. 32 Figure 14 : Le nombre de conflits dans les deux modèles de décision.
32 Figure 17 : L’ambulance va chercher la victime victim10125. 43 Figure 18 : l’ambulance va chercher la victime victime10125. 44 Figure 19 : l’ambulance va chercher la victime victime10169. 44 Figure 20 : La comparaison de la performance de deux actions « choose » dans GAML.
45 Figure 21 : La différence de la fonction d’utilité des ambulances et celle des experts. 49 Figure 22 : Pourcentages de conflits entre les décisions des agents et ceux de l’expert. 50 Figure 23 : Les différences entre la fonction des agents et celle de l’expert. 51 Figure 24 : Les proportions de conflits des décisions des agents sur ceux des décisions de l’expert.
51 Figure 5 : Les tâches des agents dans le modèle décentralisé d’AROUND-RESCUE. 22 Figure 6 : Diagramme de la diffusion de la décision de cible d’une ambulance. 23 Figure 7 : Diagramme de la réponse de la diffusion de la décision de cible d’une l’ambulance. 24 Figure 8 : Les tâches des agents dans le modèle centralisé d’AROUND-RESCUE.
25 Figure 15 : Diffusion de la fonction d’utilité aux ambulances. 41 Figure 16 : La mise à jour de la fonction d’utilité d’une ambulance. 42 6 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Liste des tableaux Tableau 1 : Les espèces d’agents dans la simulation AROUND-RESCUE. 11 Tableau 2 : Les paramètres principaux de la simulation AROUND-RESCUE.
12 Tableau 3 : Les paramètres d’expérimentation de la simulation AROUND-RESCUE. 27 Tableau 4 : Le nombre de conflits dans la simulation AROUND-RESCUE. 32 Tableau 5 : L’ensemble de critère de décision d’une ambulance A pour choisir une victime V. 34 Tableau 6 : Les critères de décision des ambulances pour le choix des victimes.
40 Tableau 7 : Les critères de décision des pompiers pour le choix des incendies. 41 Tableau 8 : Les temps d’exécution et la différence. 46 7 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Objectif du stage Le projet AROUND (Autonomous Robots for Observation of Urban Networks after a Disaster) se propose de concevoir et d’implémenter un système complet d’aide à la décision en temps-réel pour la gestion des catastrophes naturelles en milieu urbain.
Le site web du projet : http://www.org/site/content/view/48/84/ Dans le cadre de ce projet, une simulation de l’organisation des secours dans la ville de Hanoi après un tremblement de terre, permet à des experts d’interagir avec les agents du modèle afin de leur apprendre, dynamiquement, les critères à respecter pour porter secours aux victimes. Cet apprentissage permet d’affiner le modèle afin qu’il puisse servir dans un cadre d’aide à la décision [1]. L’apprentissage actuel ne prend cependant pas en compte les dimensions collectives de compétition et de coordination entre équipes de secours. Les critères utilisés ne portent en effet que sur la localisation et la gravité des victimes reportées, ainsi que sur la localisation et la disponibilité des centres de soins existants, mais pas sur l’activité parallèle des autres agents de la simulation.
D’autre part, les comportements appris par une équipe de secours ne sont pas partagés avec les autres agents. De plus, la communication est déjà implémentée dans la plate-forme GAMA [2] comme un outil efficace pour échanger les informations entre les agents. Mon sujet de stage se concentre sur la mise en place d’un mécanisme pour améliorer la performance et le réalisme de la simulation AROUND-RESCUE. Il faut développer : - un ensemble de critères « collectifs » permettant de prendre en compte dans l’apprentissage la localisation et la disponibilité des autres équipes de secours ; - une méthode de communication permettant aux agents de partager intelligemment les modèles de décision appris ; - une méthode de coordination ou de négociation, s’appuyant sur les mécanismes de communication, et permettant de régler les éventuels conflits entre les agents possédant des modèles de décision différents.
L’ensemble sera réalisé au sein de la plate-forme GAMA, développée au sein de l’équipe MSI et de l’UR Geodes, et sur laquelle fonctionne la simulation actuelle. Mon stage se déroule sous la direction du professeur Alexis DROGOUL et reprend les travaux de Chu Thanh Quang et Vo Duc An, deux thésards du laboratoire MSI. Ce rapport présente mes recherches et mes expérimentations au cours du stage en quatre parties. La première est l’introduction générale du stage et la description de la simulation 8 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com AROUND-RESCUE.
La deuxième partie parle de la coordination dans le système de secours en cas de catastrophe, les techniques principales existantes et la solution apportée pour la coordination des agents. Le problème d’apprentissage est présenté dans la troisième partie, ainsi que les expérimentations pour le mécanisme de partage et de diffusion de connaissances. Enfin ce rapport parle en conclusion des perspectives envisagées pour la simulation. Modèle AROUND-RESCUE Le modèle AROUND-RESCUE est développé pour simuler les activités de secours terrestres après un tremblement de terre.
La simulation a été créée pour la première fois par Alexis Drogoul et Chu Thanh Quang [1]. Ils ont implémenté à ce moment un modèle simple de prise de décision dans les comportements des agents. Ce modèle a été ensuite amélioré par Vo Duc An [2] en y ajoutant la communication et la coordination entre les agents. L’initialisation de la simulation est en cours d’amélioration par Bertrand Chaussat, qui intègre le calcule des positions des victimes et des incendies en se basant sur le niveau de dommages des bâtiments après le tremblement de terre.
Le projet est toujours en cours de recherche par les thésards et les stagiaires de MSI. Figure 1 : L’interface de la simulation AROUND-RESCUE 9 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Après un tremblement de terre, les bâtiments sont détruits, les habitants sont coincés et blessés dans les effondrements de béton et de briques. Des incendies se déclenchent également. L’organisation des secours dans les quartiers détruits est effectuée au minimum par la police, les pompiers, les hôpitaux et les ambulances.
Les espèces d’agents de la simulation se composent donc de : les victimes les incendies les militaires les explorateurs les pompiers les hôpitaux les ambulances La description de chaque espèce est présentée dans le tableau suivant : Espèce Représentation Comportements Tâches 1 victim Situated, visible Si une victime est sur le terrain, son état de santé s’aggrave au cours du temps. Si une victime n’est pas prise à l’heure par une ambulance, elle meurt sur le terrain. Si une victime est dans une ambulance ou dans un hôpital, son état de la santé s’améliore au fur et à mesure. 2 fire Situated, visible Si un incendie n’est pas pris en charge par des pompiers, son intensité augmenté au cours du temps.