Soutenance mémoire
Les tâches génériques
Les premières recherches sur la coopération multi-agents portaient sur l’étude du milieu animal, notamment celui des insectes. Ces études ont rapidement montré que chaque insecte n’avait pas ou peu conscience de son rôle dans la tâche globale réalisée par l’ensemble de l’essaim. Ces actions étaient uniquement guidées par des changements de comportement. Ce phénomène a rapidement intéressé les roboticiens qui se sont inspirés de ce milieu afin de réaliser des flottes de robots coopérants. Les premiers articles concernant les systèmes multiagents remontent au début des années 80 pour la robotique. Les premiers objectifs furent de définir des méthodes simples et fiables afin de réaliser des tâches courantes [Drogoul 92] et [Arkin 92]. Ces tâches, généralement inspirées du milieu animal (principalement les fourmis), peuvent se décomposer en trois grandes familles de tâches génériques qui sont la mine, la consommation et l’exploration (Sur la Figure 1 les gros ronds noirs représentent les obstacles. Les attracteurs sont symbolisés par les petits. Les traits gras ou pointillés représentent le parcours des robots (deux robots et sept attracteurs)). La mine La consommation L’exploration La mine consiste à trouver une ou plusieurs mine(s) et à rapporter le minerai à la base. C’est l’une des applications les plus courantes. Les principaux intérêts de cette tâche résident dans le fait que l’environnement n’est pas connu à l’avance, que les robots sont obligés de faire des aller-retours entre la base et la source. Ces points en particulier font que la coopération prend parfois toute son ampleur. La consommation similaire à la précédente, la consommation est une tâche qui se différencie de la mine dans le fait que l’action est effectuée sur place. Dans la mine, le minerai est ramassé, puis ramené à la base alors que pour la consommation, la tâche est réalisée sur place comme par exemple de la peinture ou de l’assemblage. C’est parfois cette action qui va nécessiter la coopération entre les robots. L’exploration consiste à parcourir la plus grande surface possible de l’environnement. Dans bien des cas, plus les agents sont nombreux, plus la tâche est réalisée rapidement. C’est justement sur ce point que la coopération devient importante, le système global doit être bien pensé pour éviter de voir un agent explorer une zone qui l’a déjà été. C’est également pour cela que la communication est l’un des éléments essentiels des systèmes multi-agents.
Tom Thumb
La première modification apportée à ce » Silly Robot » a été inspirée par la nouvelle de Charles Perrault : Le Petit Poucet (Tom Thumb). En effet, l’idée est de déposer des signes sur le chemin du retour à la base lorsqu’une mine a été découverte. Cette stratégie permet aux autres robots de suivre ces marques afin de se rendre plus rapidement aux attracteurs. De plus,lorsqu’un agent vient de déposer un échantillon, il retourne directement en prélever un autre sans passer dans une phase de déplacement aléatoire. Le principal inconvénient de ce principe est qu’une mine vide continue d’attirer les robots puisque les marques ne sont pas ramassées. Pour éviter ce phénomène, nous allons permettre aux robots d’effacer les marques. Lorsqu’il a détecté une mine, il laisse une marque sur son chemin qu’il ramassera lors de son retour à la base. Les résultats de simulation ne sont pas des plus satisfaisants. En effet, supprimer complètement la marque cache un grand nombre d’informations aux autres robots. D’un autre côté, lorsqu’une mine est vide, ils ne sont plus attirés par celle-ci. Un compromis des deux méthodes précédentes a été proposé par Steels [Steels 91]. Le concept est de pouvoir effacer les marques, mais lentement. Les robots déposent donc 2 marques sur le chemin de la base et en ramassent une lorsqu’ils se dirigent vers la mine. Les résultats de la simulation réalisée par A. Drogoul et J. Ferber montrent une efficacité et une stabilité bien meilleure. Seulement, lorsque le nombre de robots est supérieur à 85, les performances diminuent. Par exemple, pour une population de 100 robots, le nombre de cycles nécessaires pour ramasser la totalité des échantillons est équivalent à celui d’une population de 25. Ce phénomène d’embouteillage est constaté lorsque le nombre d’agents est élevé et est dû à une forte concentration autour de la base et des sources de minerai.
Chain-Making Robot
Après avoir présenté et comparé les deux méthodes précédentes A. Drogoul et J. Ferber proposent un nouveau type de comportement nommé Chain-Making. Celui-ci est inspiré des dockers, qui plutôt que de s’amasser autour de la porte du bateau, forment une chaîne allant du bateau au point de déchargement. Pour réaliser ce comportement il est indispensable d’ajouter de nouvelles fonctionnalités à nos agents : la possibilité de détecter un échantillon transporté par un autre agent et de lui prendre. Par exemple, une lampe disposée au-dessus des robots, lorsqu’elle est allumée, signifie qu’il est en train de regagner la base tout en transportant un échantillon. Cette émission de l’état interne pourra être détectée par un robot se trouvant dans une phase de déplacement aléatoire et lui permettra d’adopter le même comportement que s’il venait de découvrir une mine. Il prélèvera l’échantillon transporté avant de se diriger vers la base. De même, s’il rencontre un robot vide sur son chemin, il abandonnera sa cargaison à son successeur pour revenir dans un état d’errance.
Les protocoles de communication distribué
La tendance actuelle évolue vers l’utilisation de protocoles Internet (TCP/IP) [Winfield 00]. Ce type de protocole nécessite un processeur embarqué puissant et l’utilisation de cartes PCMCIA Wireless LAN embarquée sur les robots. Ce type d’architecture onéreuse présente des consommations non négligeables. De plus, malgré l’utilisation d’émetteurs/récepteurs UHF à fort débit, le taux de communication global reste faible : 10 messages par robot par seconde dans l’application de A. Winfield et O. Holland. Nous allons maintenant présenter les trois protocoles les plus représentatifs :
Principe du multiplexage. Ce protocole est employé dans le cas d’un canal unique : chaque agent se voit attribué un laps de temps ou une fréquence du canal. Dans le cas d’un découpage temporel, les agents peuvent utiliser à tour de rôle la bande passante afin d’y envoyer leurs messages. Avec cette méthode, les taux de transferts décroissent fortement avec le nombre d’agents. De plus, l’utilisation de la bande passante est mauvaise, si par exemple un ou plusieurs agents n’ont pas de message à envoyer pendant plusieurs périodes, leur laps de temps est quand même attribué et non utilisé. Ce type de communication demande de synchroniser parfaitement les agents et le nombre d’utilisateurs est limité par le découpage. De plus l’allocation dynamique (ajout ou suppression d’un agent) est envisageable, mais complexe à mettre en œuvre.
Principe de CSMA (Carrier Sense Multiple Access). Ce protocole, issu des réseaux informatiques, consiste à émettre des trames de façon » anarchique » mais de tolérer les collisions et d’accepter de devoir renvoyer une trame plus tard. Ce type de protocole écoute le canal et envoie la trame dès que celui-ci est libre. Si une collision est détectée, la trame sera à nouveau envoyée après un laps de temps aléatoire afin d’éviter une nouvelle collision. Evidement, ce type de protocole n’est efficace que lorsque le taux de charge du canal reste inférieur au maximum. Lorsque tous les agents veulent émettre une trame, les collisions constantes accumulent les messages réitérés, augmentant ainsi la charge du réseau.
Les protocoles de communication locaux. Dans le cas des systèmes multi-agents distribués, il n’est pas toujours possible (ou utile) de transmettre des messages à l’ensemble des agents. Dans le cas de l’architecture proposée par O. Simonin [Simonin 01], la propagation des signaux se fait de façon naturelle par l’architecture. Donc les communications locales sont amplement suffisantes. Dans ce type de systèmes, la configuration évolue constamment : des agents quittent et rejoignent fréquemment des groupes locaux communicants. C’est pour cette raison que l’allocation doit pouvoir être dynamique.
Il existe donc divers protocoles de communication spécifiques à différentes applications. Toutefois, ces protocoles, souvent inspirés des réseaux informatiques, ne permettent pas toujours de répondre aux problèmes spécifiques des systèmes multi-agents distribués. Nous proposons dans ce manuscrit un nouveau protocole de communication permettant de répondre spécifiquement aux besoins de nos systèmes [section 5.3.4].
Les réseaux neuronaux
En 1943, deux bio-physiciens de l’université de Chicago, Mac Cullogh et Pitts proposent le premier modèle de neurone biologique [Cullogh 43]. Ce neurone formel, aussi appelé neurone à seuil, est inspiré des récentes découvertes en biologie. Ce sont des neurones logiques (0 ou 1). En 1949, le psychologue Donald Hebb introduit le terme connexionisme pour parler de modèles massivement parallèles et connectés [Hebb 49]. Il propose de nombreuses règles de mise à jour des poids dont la célèbre » règle de Hebb « . En 1958, le psychologue Frank Rosenblatt, combinant les idées de ses prédécesseurs, propose le premier perceptron [Rosenblatt 58]. Ce réseau, capable d’apprendre à différencier des formes simples et à calculer certaines fonctions logiques, est inspiré du système visuel. Au début des années 60, les travaux de Rosenblatt suscitent un vif enthousiasme dans le milieu scientifique. Mais en 1969, deux scientifiques américains de renom, Minsky et Papert, publient un livre [Minsky 69] qui démontre les limites du perceptron proposé par Rosenblatt. En particulier, son incapacité à résoudre les problèmes non linéairement séparables, dont la fonction logique XOR est un célèbre exemple. Les travaux ralentissent considérablement jusqu’aux années 80. En 1982, Hopfield démontre l’intérêt des réseaux entièrement connectés [Hopfield 82]. Parallèlement, Werbos conçoit un mécanisme d’apprentissage pour les réseaux multicouches de type perceptron: la rétropropagation (Back-Propagation). Cet algorithme, qui permet de propager l’erreur vers les couches cachées sera popularisé en 1986 dans un livre » Parallel Distributed Processing » par Rumelhart et al [Rumelhart 86]. Depuis ces travaux, les applications des réseaux de neurones n’ont cessé de croître. Il a d’ailleurs été démontré qu’un réseau MLP (Multi Layer perceptron) avec seulement deux couches peut approximer n’importe quelle fonction de Rn dans Rm avec une précision arbitraire.
Un algorithme évolutionniste distribué
L’expérience menée par Dario Floreano et Franscesco Mondada montre la possibilité d’apprendre des comportements réactifs en utilisant les algorithmes génétiques. La méthode employée est dite supervisée, elle nécessite de centraliser l’ensemble des chaînes chromosomiques afin de produire la génération suivante. Une panne du système central engendre immédiatement une panne globale sur l’ensemble du système. De plus, si le système de communication n’est pas global, les agents doivent se rassembler pour transmettre leurs codes génétiques. Les méthodes supervisées peuvent s’appliquer sans problème aux systèmes simulés ou logiciels, mais dans le cas des systèmes multi-robots, la robustesse n’est pas garantie. Cette méthode est directement inspirée de l’hypothèse d’évolution des espèces proposée par Darwin. La population actuelle de la terre est estimée à 6 milliards d’individus. Pour créer une nouvelle génération, les 6 milliards de séquences ADN ne sont pas réunies pour produire 6 milliards de nouveaux individus. D’ailleurs, la taille de la population peut varier sans pour autant perturber le système. Afin de conserver les propriétés inhérentes aux systèmes distribués, c’est une fois de plus dans le vivant que nous allons trouver une nouvelle source d’inspiration. Lorsque deux individus vont se rencontrer et que toutes les conditions seront réunies, leurs chaînes chromosomiques seront échangées pour créer deux nouveaux individus.
|
Table des matières
Remerciements
Table des figures, tableaux et algorithmes
1. INTRODUCTION GENERALE
2. LES SYSTEMES MULTI-AGENTS
2.1 Introduction
2.2 Définition
2.3 Les tâches génériques
2.4 L’approche réactive
2.4.1 Introduction
2.4.2 Silly Robot
2.4.3 Tom Thumb
2.4.4 Chain-Making Robot
2.4.5 Systèmes réactifs et cognitifs
2.5 Les communications dans les systèmes multi-agents
2.5.1 Introduction
2.5.2 Les protocoles de communication supervisé
2.5.3 Les protocoles de communication distribué
2.6 Conclusion
3. LES METHODES D’APPRENTISSAGE
3.1 Introduction
3.2 Les réseaux neuronaux
3.2.1 Introduction et historique
3.2.2 Notation
3.2.3 La rétropropagation du gradient
3.2.4 Les réseaux à fonctions radiales
3.2.5 Conclusion
3.3 L’apprentissage par renforcement
3.3.1 Introduction
3.3.2 Les processus markoviens
3.3.3 La programmation dynamique
3.3.4 Le Q-learning
3.3.5 Conclusion
3.4 Les algorithmes évolutionnistes
3.4.1 Introduction
3.4.2 Les opérateurs génétiques
3.4.4 Conclusion
3.5 L’estimation de la performance
3.6 Conclusion
4. NOTRE PLATE-FORME EXPERIMENTALE
4.1 Introduction
4.2 Le robot Type 1
4.2.2 Description matérielle
4.2.3 Description du logiciel
4.3 Le manipulateur mobile miniature(M3)
4.3.1 Introduction
4.3.2 Repères de référence
4.3.4 Positions et orientations
4.4 Bird Of Prey (BOP)
4.4.1 Introduction
4.4.2 Description générale
4.4.3 Positions et orientations
4.5 Conclusion
5. ALGORITHMES EVOLUTIONNISTES POUR LES SYSTEMES MULTI-ROBOTS HOMOGENES
5.1 Introduction
5.2 Un algorithme évolutionniste supervisé
5.2.1 Introduction
5.2.2 Description de la tâche
5.2.3 Résultats
5.2.4 Conclusion
5.3 Un algorithme évolutionniste distribué
5.3.1 Introduction
5.3.2 Description de la tâche
5.3.3 Les opérateurs
5.3.4 Protocole de communication
5.3.5 Résultats
5.4 Conclusion
6. METHODES D’APPRENTISSAGE POUR LES SYSTEMES MULTI ROBOTS HETEROGENES
6.1 Introduction
6.2 Recuit simulé
6.2.1 Introduction
6.2.1 Structure du contrôleur
6.2.2 Approche classique
6.2.3 Résultats expérimentaux I
6.2.4 Approche adaptative
6.2.5 Résultats expérimentaux II
6.2.6 Conclusion
6.3 Extension de l’apprentissage par renforcement au domaine continu
6.3.1 Introduction
6.3.2 Approximation de la Q-fonction
6.3.3 Recherche du maximum
6.3.4 Résultats expérimentaux 1
6.3.4 Résultats expérimentaux 2
6.4 Conclusion
7. CONCLUSION GENERALE
BIBLIOGRAPHIE
A.1. Vitesses angulaire
A.2. Equations de la dynamique
A.2.1. Corps 4 (l’organe terminal et la charge)
A.2.2. Corps 3 (l’avant bras) et 2 (le bras)
A.3.3. Corps 1 (la base mobile)
ANNEXE B : SCHEMA ELECTRONIQUE DU ROBOT TYPE 1
Télécharger le rapport complet
