Stratégie d’exploration multi agent pour les environnements inconnus
Ce mémoire étudie la couverture d’environnements inconnus par des robots autonomes en intelligence artificielle distribuée. Il propose une approche réactive inspirée du comportement des insectes et des escargots pour concevoir un algorithme d’agrégation stratégique. L’extension de l’algorithme SMRSA permet de prendre en compte l’observabilité locale totale et les coupures de communication. Les résultats expérimentaux montrent une amélioration des performances par rapport à l’algorithme MRSAM original.
Université 08 Mai 1945-Guelma
Faculté des Mathématiques, d’Informatique et des Sciences de la matière
Département d’Informatique
Filière : Informatique
Spécialité : Ingénierie des Medias
Mémoire de fin d’étude de Master
Stratégie d’exploration multi agent pour les environnements inconnus
Présenté par :
Nedjoua.Brahmia & Rima .Boulahia
Sous la direction de :
Melle. ZEDADRA Ouarda
Juin 2013
[img_37]
[img_38]
[img_39]
Sommaire
Résumé Sommaire 1
Liste des figures 4
Introduction général 6
Chapitre I : état de l’art
Introduction 9
• Systèmes multi-agents: définition et principes 9l’intelligence artificielle distribuée 10Agents : concepts fondamentaux 10Définition 10Classification d’agent 11Architecture d’agent 13Principes des SMA 16Interactions dans les SMA 17Organisations dans les SMA 18Communication dans les systèmes multi-agents 19Définition par Russel 19Coopération 20Les mécanismes de coordination multi-agent 20Structuration organisationnelle 22Allocation 22Planification 23Négociation 24Coordination réactive 24Simulation multi agent 26Avantage des SMA 27Problèmes des SMA 28Champs d’application des systèmes multi-agents 29Conclusion 29
• l’intelligence artificielle distribuée 10
• Agents : concepts fondamentaux 10Définition 10Classification d’agent 11Architecture d’agent 13
• Définition 10
• Classification d’agent 11
• Architecture d’agent 13
• Principes des SMA 16
• Interactions dans les SMA 17
• Organisations dans les SMA 18
• Communication dans les systèmes multi-agents 19Définition par Russel 19
• Définition par Russel 19
• Coopération 20
• Les mécanismes de coordination multi-agent 20Structuration organisationnelle 22Allocation 22Planification 23Négociation 24Coordination réactive 24
• Structuration organisationnelle 22
• Allocation 22
• Planification 23
• Négociation 24
• Coordination réactive 24
• Simulation multi agent 26
• Avantage des SMA 27
• Problèmes des SMA 28
• Champs d’application des systèmes multi-agents 29
• Conclusion 29
Chapitre II : couverture et exploration des environnements inconnus
Introduction 31
• Les algorithmes de couverture 32Les algorithmes de couverture pour un seul robot 33
• Les algorithmes de couverture pour un seul robot 33
. Algorithme Spanning Tree Couvrant (STC) 35
. Algorithme Spiral STC 39
• Les algorithmes de couverture multi robots 40
• Les algorithmes de couverture multi robots 40
. Algorithme MRSAM 42
. nouvel algorithme de couverture multi-robot (MCF) 45
• Les champs de potentiels artificiels 46Comparaison des résultats des algorithmes de couverture mono-robot et multi-robots 40MFC & STC & MSTC 47Off-line STC & On-line STC & Ant-like STC 47
• Les champs de potentiels artificiels 46
• Comparaison des résultats des algorithmes de couverture mono-robot et multi-robots 40MFC & STC & MSTC 47Off-line STC & On-line STC & Ant-like STC 47
• MFC & STC & MSTC 47
• Off-line STC & On-line STC & Ant-like STC 47
• L’exploration d’un environnement inconnu 48Définition 48Les algorithmes d’exploration 49Frontière la plus proche 49Glouton 51Problème d’exploration 51
• Définition 48
• Les algorithmes d’exploration 49Frontière la plus proche 49Glouton 51
• Frontière la plus proche 49
• Glouton 51
• Problème d’exploration 51
• Conclusion 52
Chapitre III : Conception et réalisation
Introduction 53
• Conception 53Objectifs de l’application 53Modélisation du problème 63Modélisation de l’environnement 54Modélisation des agents 54Comportement des agents 55
• Objectifs de l’application 53
• Modélisation du problème 63Modélisation de l’environnement 54Modélisation des agents 54
• Modélisation de l’environnement 54
• Modélisation des agents 54
• Comportement des agents 55
• Réalisation 56Environnement de programmation 57
• Environnement de programmation 57
• Aspect matériel 57
• Environnement de développement 57Présentation de l’application 58Résultats expérimentaux 62
• Présentation de l’application 58
• Résultats expérimentaux 62
• Conclusion 67
Conclusion Générale et perspectives 68
Bibliographie 70
Liste des figures
Chapitre 1: état de l’art
Figure 1.1: Axe pratique d’évaluation de la capacité d’un agent à accomplir individuellement des tâches complexes et à planifier ses actions 12
Figure 1.2: Classification d’agents 13
Figure 1.3: Architecture BDI 14
Figure 1.4: Architecture subsumption 15
Figure 1.5: Les composantes principales d’un SMA 16
Figure 1.6: Communication directe 19
Figure 1.7: Principaux mécanismes de coordination multi-agent 21
Figure 1.8: Exemples de structures organisationnelles 22
Figure 1.9: Résolution d’un problème par un SMA 23
Figure 1.10: Système de planification multi-agent (exemple) 24
Figure 1.11: Exemple de protocole de négociation entre deux agents 25
Figure 1.12: Principes de la simulation multi-agent 27
Chapitre2 : les algorithmes de couverture et exploration des environnements inconnus
Figure 2.1 : Une couverture optimale ne signifie pas nécessairement une patrouille optimale
. 33
Figure 2.2: Un spanning tree (arcs bleus) d’un graphe grille 34
Figure 2.3:Un cycle hamiltonien réalisé à partir d’un spanning tree sur un environnement grille de 8×8 nœuds 35
Figure 2.4: Exemple de l’algorithme STC 36
Figure 2.5 : Un exemple d’exécution de l’algorithme STC off ligne 37
Figure 2.6: La fourmi peut se déplacer à carreaux ou des sommets, T1, T2, T3 et T4. (a)Le cercle est la plage du capteur efficace de la fourmi. (b) La forme équivalente dans un graphe non orienté 38
Figure 2.7: (a) une seule face, (b) à double face bord, (c) doublement de nœud à une cellule déconnectée 40
Figure 2.8: exemple de MSTC en fonctionnement 42
Figure 2.9: La région du disque recherché par SAD1 doublé à chaque étape 43
Figure 2.10: Un groupe de deux robots lancés par MRSAM à la recherche de la cible 44
Figure 2.11: exemple de l’algorithme MFC 46
Figure 2.12 : MFC et MSTC contre STC 47
Figure 2.13: Coordination implicite avec l’algorithme frontière la plus proche 50
Figure 2.14: Résultat de l’assignation avec l’algorithme Frontière la plus proche 50
Figure 2.15: Illustration de l’allocation de frontière avec l’algorithme glouton 51
Chapitre III : Conception et réalisation
Figure 3.1 : Interface principale 59
Figure 3.2 : Création d’environnement(a) 60
Figure 3.2 : Création d’environnement(b) 60
Figure 3.2 : Création d’environnement(c) 61
Figure 3.2 : Création d’environnement(d) 61
Figure 3.3: Lancer la simulation 62
Figure 3.4: Division de l’environnement selon le paramètre de rayon de carré 62
Figure 3.5: (etape1) lancer la couverture mono-robot 64
Figure 3.5: (Etape2) déplacement de robot vers la deuxième région 63
Figure 3.5: (Etape 3) déplacement de robot vers la troisième région 64
Figure 3.5: (Etape 4) couvrir la quatrième région 65
Figure 3.6 : (Eetape 1) lancer la couverture multi-robot 65
Figure 3.6 : (Eetape 2) lancer la couverture multi-robot 66
Bibliothèques :
[Adina, 02] : Adina Magda Florea « Agents et Systèmes Multi-agents » cours, l’Université Politehnica de Bucarest ,2002
[Arnaud ,11] : Arnaud Glad «Etude de l’auto-organisation dans les algorithmes de patrouille multi-agent fondés sur les phéromones digitales » théese pour l’obtention du
Doctorat de l’université Nancy 2, 2011.
[Bautin et al, 11] : A. Bautina, O. Simonin et F. Charpilleta , « Stratégie d’exploration multi- robot fondée sur les champs de potentiels artificiels», Manuscrit auteur, publié dans « Journées Francophones sur les Systèmes Multi-Agents (JFSMA) ,2011.
[Bond et al, 88]. Bond A. et Gasser L., « Readings in Artificial Intelligence». Morgan Kaufmann, 1988.
[Brian, 97] : Brian Yamauchi. A frontier-based approach for autonomous exploration: Proceedings of the 1997 IEEE International Symposium on Computational Intelligence in Robotics and Automation, page 146, Washington, DC, USA, 1997.
[Brooks 1986]: R. Brooks, « a Robust Layered Control System for a Mobile Robot » IEEE Journal of Robotics and Automation
[Champion, 03] :A. Champion. « Mécanisme de coordination multi –agent fondé sur des jeux: application à la simulation comportementale de trafic routier en situation de carrefour». Thèse de doctorat, l’université de valenciennes et du hainaut-cambrésis, 2003.
[Courdier , 07] : Rémy Courdier , «Systèmes Multi-Agents Partie 2 Agents et Systèmes Multi-Agents», Université de la Réunion , 2007
[Decker, 95] : Decker K., «Environment centred analysis and design of coordination mechanisms», University of Massachussetts, 1995
[Deloach 09]: Deloach.S.A. « Organizational model for adaptive complex systems ». In Virginia Dignum (ed.) Multi-Agent Systems: Semantics and Dynamics of Organizational, University, USA (2009).
[Doran et al. 97] : Doran.J. E., Franklin.S., Jennings.N.R., Norman.T.J. «On cooperation in multi-agent systems ». The Knowledge Engineering Review .1997
[Drogoul, 93] : A. Drogoul. « De la simulation multi agent à la résolution de problèmes. Une étude de l’émergence de structures d’organisation dans les systèmes multi agents ». 1993.
[Durfee et al , 89] : Durfee E.H., Lesser V. et Corkill D., Trends in cooperative distributed problem solving. IEEE Knowledge and Data Engeneering, 1989.
[Ferber, 95] : J. Ferber. « Les systèmes multi-agents vers une intelligence collective », inter éditions, 1995.
[Ferber et al, 09]: Ferber.J., Stratulat.T., Tranier.J, « Towards an integral approach of organizations in multi-agent systems: the MASQ approach», university de Montpellier,
France, 2009
[Frédérick, 13] : Frédérick Lessard « exploration optimale d’un segment de droite par deux agents mobiles», mémoire présenté comme exigence partielle de la maîtrise en informatique université du québec en outaouais, 2013.
[Gabriely and Al, 99]: Yoav Gabriely and Elon Rimon « Spanning-Tree Based Coverage of Continuous Areas by a Mobile Robot» Department de Mechanical Engineering Technion,
Israel Institute of Technology, 1999
[Glizes, 04]: Gleizes.M.P, «Vers la résolution de problèmes par émergence». Thèse d’habilitation de l’Université de Toulouse 2004.
[Glizes et al. 99]: Gleizes.M.P., Camps.V., Glize.P. «A theory of emergent computation based on cooperative self-organization for adaptive artificial systems». Institut de Recherche en Informatique de Toulouse, France, 1999.
[Haddad et Hamidi, 09] : A. Haddad et M. Hamidi. « Modélisation du contexte avec prise en compte d’incertitudes pour les applications sensibles au contexte (cas : les environnements intelligents) ». Mémoire de fin d’études Pour l’obtention du diplôme d’ingénieur d’Etat en génie : informatique, Alger, 2009.
[Jacky et al, 04] : H. Jacky Chang, C. S. George Lee, Yung-Hsiang Lu, and Y. Charlie Hu
«Energy-Time-Efficient Adaptive Dispatching Algorithms for Ant-Like Robot Systems »School of Electrical and Computer Engineering Purdue University, 2004.
[Jiquan et al, 08]: Jiquan.S., Zhiqiang.W. «Service-Oriented Organization Management and Coordination Control of MAS». In IEEE International Conference on Intelligent Computation Technology and Automation, (2008).
[Khatib, 1986]: Oussama Khatib, «Real-time obstacle avoidance for manipulators and mobile robots» Article; International Journal of Robotics Research, l’Université Stanford, 1986.
[Kaplan, 1998] : F. Kaplan «Role de la simulation multi-agent pour comprendre l’origine et l’évolution du langage», nom de journal: BARTHÈS, J.-P., CHEVRIER, V., et BRASSAC, C., éditeurs, Systèmes multi-agents: de l’interaction à la socialité (JFIADSMA98), 1998.
[Labidi et al, 93] : S. Labidi, W. Lejouad «De l’Intelligence Artificielle Distribuée aux Systèmes Multi-Agents »Institut national de recherche en informatique et en automatique, 1993
[Lopez et al, 97] R. Lopez De Mantaras, J. Amat, F. Esteva, M. Lopez, and C. Sierra. Generation of unknown environment maps by cooperative low-cost robots. 1997
[M.Gouasmi, 05] : M.GOUASMI Ingénieur d’état en informatique Option systèmes d’informations avancés «Intégration d’ontologie dans les actes de communication inter- agents» Université Ibn Khaldoun de Tiaret, 2005
[Melaye et al, 05] : Melaye.D., Demazeau.Y. «Modéles et Réseaux de confiance
Droits et Devoirs d’Agents Autonomes Confiance et modèles de confiances pour la régulation des droits et devoirs d’agents autonomes» Laboratoire Leibniz, Equipe MAGMA, 2005. [Moujahed, 07] S. Moujahed. « Approche multi-agent auto-organisée pour la résolution de contraintes spatiales dans les problèmes de positionnement mono et multi-niveaux ». Thèse de l’université de Technologie de Belfort-Montbéliard et de l’Université de Franche-Comté, 2007
[Noam et al, 05]: Noam Hazon and Gal A. Kaminka «Redundancy, Efficiency and Robustness in Multi-Robot Coverage »
[Nembrini et al, 07] : Julien Nembrini & Alcherio Martinoli «Robotique en Essaim,Récents Résultats et Directions Futures»Ecole Polytechnique Fedérale de Lausanne, 2007
[Sahki, 08] : Mr Hanine Sahki, « Vers une Architecture d’un Système de
Dialogue Multi Agents Basé sur l’Argumentation Application à la négociation dans le domaine de e-commerce», Mémoire présenté en vue de l’obtention du Magister en Informatique, 2008
[Sarid et Shapir, 06] : Shahar Sarid and Amir Shapiro «MRSAM: A Quadratically Competitive Multi Robots Navigation Algorithm»Department of Mechanical Engineering Ben Gurion University of the Negev, Israel, 2006.
[sarid, 11] : Shahar Sarid, « Heterogeneous Multi-Robot Search Algorithms», University de Negev, 2011.
[Shehory et al, 98] : Shehory O., Sycara K., Chalasani P. et Somesh J., Increasing resource utilisation and task performance by agent cloning, Proceedings of the ICMAS, ATAL 98,
[Panait et al, 05] : Panait.L., Luke.S. «Cooperative Multi-Agent Learning: The State of the Art. In Autonomous Agents and Multi-Agent Systems», University de George Mason. 2005. [Russel, 06] : Russell.S, «Intelligence artificielle». Pearson Education 2e édition. 2006
[Sabouret, 09] : Sabouret.N. «Interactions sur le fonctionnement dans les systèmes multi- agents ouverts et hétérogènes». Habilitation à Diriger des Recherches, Université Pierre &Marie Curie 2009.
[Thomas, 05] : Thomas.V, «Proposition d’un formalisme pour la construction automatique d’interactions dans les systèmes multi-agents réactifs». Thèse de doctorat de l’université Nancy 1, 2005.
[Tom et al, 97] : Tom Duckett and Ulrich Nehmzow. Experiments in evidence based localisation for a mobile robot. In Proceedings of the AISB Workshop on Spatial Reasoning in Mobile Robots and Animals, Manchester, UK, 1997.
[Velagapudi et al, 07] : Velagapudi.P, Prokopyev.O, Sycara.K., Scerri.P. «Maintaining Shared Belief in a Large Multiagent Team». In Proceedings of FUSION, 2007.
[Wesley, 01]: Wesley H. Huang, «Optimal Line-sweep-based Decompositions for Coverage Algorithms» Department of Computer Science Rensselaer Polytechnic Institute Troy, New York, 2001.
[Xiaoming et al, 05] : Xiaoming Zheng ,Sonal Jain ,Sven Koenig ,David Kempe «Multi- Robot Forest Coverage» Department of Computer Science University of Southern California Los Angeles, 2005
[Yoav et al, 02]: Yoav Gabriely and Elon Rimon «Spiral-STC: An On-Line Coverage Algorithm of Grid Environments by a Mobile Robot» Technion, Israel Institute of Technology, 2002.
[Yoav et al, 99]: Yoav Gabriely and Elon Rimon, «Spanning-Tree Based Coverage of Continuous Areas by a Mobile Robot», Dept. of Mechanical Engineering
Technion, Israel Institute of Technology, 1999