Miroir

Axe de rotation du
miroir

Platine

Figure 30 : Le système de vision stéréoscopique BOP Camera 1

Camera 2
Servomoteur
La Figure 30 présente une vue d’ensemble du système. Les deux caméras sont fixées
l’une par rapport à l’autre par l’intermédiaire de la platine. Les objectifs des deux caméras Figure 31 : Organe terminal
sont orientés vers le haut, un miroir mobile situé au-dessus des caméras permet d’orienter le
champ de vision. Ce système permet de modifier l’angle de vue rapidement sans avoir à
bouger les caméras. La Figure 31 montre un schéma du mécanisme terminal. Le miroir est Organe terminal
actionné par un servomoteur miniature. Pour alléger au maximum les pièces mobiles, cet Rotule
actionneur devait être fixe sur le châssis et la transmission devait se faire par l’intermédiaire Châssis
d’un câble. Mais, étant donné le poids d’un servomoteur miniature (8 grammes), nous avons
choisi de l’embarquer sur la platine. La transmission jusqu’au miroir se fait via une petite
bielle. Axe 3

Pour que le système puisse être viable, il faut que le temps séparant deux acquisitions soit Rotule
le plus court possible. Afin d’augmenter la dynamique du système, nous avons fait le choix de
n’embarquer aucun moteur sur les parties mobiles (à l’exception du servomoteur miniature
présenté précédemment). Une architecture mécanique du type série était donc à exclure. Nous
nous sommes inspirés des mécanismes parallèles: l’organe terminal est mu par deux Axe 2
servomoteurs qui sont fixes sur le châssis. Le mécanisme forme une chaîne fermée constituée
de la séquence suivante :
un servomoteur (servomoteur 1),
un axe fixe sur le servomoteur (axe 1), Rotule
une liaison pivot reliant l’axe et l’organe terminal,
l’organe terminal,
une liaison rotule reliant l’organe terminal et l’axe suivant, Servomoteur 2
un axe (axe 3), Axe 1
une liaison rotule reliant les axes 2 et 3 Servomoteur 1
un axe fixé sur le servomoteur 2
et le servomoteur 2. Figure 32 : Schéma global de notre système de vision BOP

63 64
 Les positions dans le repère fixe peuvent ainsi être calculées (Équation 21, Équation
Un schéma de l’ensemble du mécanisme est proposé sur la Figure 32. Le servomoteur 22, Équation 23 et Équation 24).
1 permet de positionner l’organe terminal. Le servomoteur 2 déforme le parallélogramme
formé par les axes afin de modifier l’orientation de l’angle de vue. Un exemple d’acquisition  X O2 X O1 (l1 ) x C1
est présenté sur la Figure 33 : Exemple de positions d’acquisition. Les deux actionneurs 
permettent de modifier à la fois la position de l’organe terminal, mais aussi son orientation. YO2 YO1 (l1 ) x S1
Le mécanisme étant de petite taille (le diamètre du châssis est de 30 cm), nous avons choisi 
Z O2 R (l1 ) z
d’utiliser du matériel de modélisme pour la réalisation de ce premier prototype. Les
servomoteurs utilisés présentent des accélérations suffisantes pour permettre au système Équation 21 : position absolue du repère 2
d’obtenir la dynamique désirée.  X O3 X O1 ((l1 ) x l 2 C 2 )C1

YO3 YO1 ((l1 ) x l 2 C 2 ) S1

Z O3 R (l1 ) z l 2 S 2
Équation 22 : position absolue du repère 3

 X O4 X O1 ((l1 ) x l 2 C 2 l 3 C3 )C1

YO4 YO1 ((l1 ) x l 2 C 2 l3 C3 ) S1

Z O4 R (l1 ) z l 2 S 2 l3 S 3
Équation 23 : position absolue du repère 4

 X O5 X O1 ((l1 ) x l 2 C 2 l3C 3 (l 4 ) x C 4 (l 4 ) z S 4 )C1


YO5 YO1 ((l1 ) x l 2 C 2 l3C 3 (l 4 ) x C 4 (l 4 ) z S 4 )S1
Figure 33 : Exemple de positions d’acquisition 
Z O5 R (l1 ) z l 2 S 2 l3 S 3 (l 4 ) x S 4 (l 4 ) z C 4
Équation 24 : position absolue du repère 5
La dynamique du manipulateur mobile est décrite en Annexe A.

La Figure 34 montre la disposition des différents points et repères. Afin de ne pas

alourdir le schéma, les longueurs des axes n’ont pas été reportées sur la figure. Voici les
principales longueurs utilisées dans la suite des calculs :

l1 : distance entre l’origine O et le point M1, Comme son nom l’indique, Bird of Prey est un système de vision inspiré des oiseaux
l2 : distance entre le point M1 et le point M2, de proies. Certains oiseaux peuvent repérer précisément leurs proies à plusieurs dizaines de
l3 : distance entre le point M2 et le point M3, mètres. Grâce à un mouvement vif de la tête, ils peuvent estimer précisément la position
l4 : distance entre le point M3 et le point M4, relative de leur cible. Nous nous sommes inspirés de cette technique pour créer BOP. En effet,
l5 : distance entre le point M4 et le point M5, le système est équipé de deux caméras. Ces deux caméras sont montées sur un châssis mobile
l6 : distance entre le point M6 et l’origine O. permettant l’acquisition de deux séries images. Nous disposons donc au final de quatre
images prises de quatre angles de vue différents. En connaissant les positions relatives des 4
Le calcul des positions et des orientations se fait entièrement dans le repère fixe (O, X, Y). prises de vues, il est alors possible de calculer précisément la position d‘un objet fixe dans
L’objectif est de calculer les coordonnées des points M3 et M2. Commençons par calculer la l’environnement. Mais cette technique permet également de connaître la position et la vitesse
position des points M1, M2, M4 et M5 (Équation 25). d’un objet mobile. Mathématiquement, une acquisition de deux images permet de connaître la
position d’un objet dans l’espace, donc deux acquisitions successives donnent deux positions
espacées d’un écart de temps t. Avec ces deux positions, il est alors très simple de calculer la
vitesse instantanée de l’objet traqué.

65 62
Nous poserons :
X M1 l1 X M l6 5

C i cos(q i ) YM1 0 YM 0 5


S i sin( qi ) X M 2 X M 2 [Link]( 1)
Les positions et orientations des autres repères de référence sont faciles à calculer
YM 2 YM 2 [Link]( 1)
(Équation 16, Équation 17 et Équation 18). X M 4 X M 5 [Link]( 2)
( xO2 )1 (l1 ) x
YM 4 YM5 [Link]( 2)
 Équation 25 : Coordonnées des points M1, M2, M4 et M5
( y O2 )1 0

( z O2 )1 (l1 ) z
Équation 16 : position du repère 2.

( xO3 )1 (l1 ) x l2C2


( y O3 )1 0

( z O3 )1 (l1 ) z l2 S2
Équation 17 : position du repère 3 M3
( xO4 ) 1 (l1 ) x l2C2 l3 C3 M2

( y O4 )1 0 1
 Y
( z O4 )1 (l1 ) z l2 S2 l3 S 3
Équation 18 : position du repère 4
M4
Calculons maintenant la position du dernier point de référence lié à l’organe terminal 2

(Équation 19).
O
M5 M1 X
( xO5 ) 1 (l1 ) x l2C2 l3 C3 (l 4 ) x C 4 (l 4 ) z S 4

( yO4 )1 0

( z O4 )1 (l1 ) z l2 S2 l3 S 3 (l 4 ) x S 4 (l 4 ) z C 4
Figure 34 : Disposition des différents points et repères
Équation 19 : position du repère 5

Le problème réside dans le calcul des coordonnées du point M3. La méthode consiste
Finalement, nous pouvons obtenir la matrice de transformation homogène (Équation
à calculer l’intersection des deux cercles de centres M4 et M2. Ces cercles ont des rayons
20).
respectifs de longueur l4 et l3. Les équations des cercles sont données par l’Équation 26.
C1 S1 0 X O1 
S C1 0 YO1 
0
T1  1
0 0 1 R 
(X M 3 X M 4)² (YM3 YM 4)² l4²

0 0 0 1 
 (X M3 X M 2)² (YM 3 YM 2)² l3²
Équation 20 : matrice de transformation homogène
Équation 26 : Equation des deux cercles de centre M4 et M2

61 66
 La résolution de ce système de deux équations à deux inconnues permet de trouver les
coordonnées de l’Équation 27.
 X M 3 c bYM3
YM 3 B B² 4AC
 2A
avec :

a 2X M 2 2X M 4
(2 Y M 2 2 Y M 4)
b
a
( l2 ² l3 ² X M 2 ² X M 4 ² Y M 2 ² Y M 4 ²)
c
a
A b² 1
B 2bX M 4 2cbYM 4 2YM 4
C c² 2cX M 4 X M 4 ² YM 4 ² l2²

Équation 27 : Coordonnées du point M3

Afin d’expérimenter nos architectures d’apprentissage dans des conditions réelles,

nous avons dessiné et construit notre plate-forme expérimentale. Cette plate-forme est Figure 29 : Disposition des différents repères
constituée d’un système de vision stéréoscopique (BOP) et de cinq robots mobiles Type 1
dont un est équipé du manipulateur mobile miniature (M3). Chacun de ces robots a été décrit
en détail dans ce chapitre. Bien sûr, les méthodes présentées dans les chapitres suivants n’ont
pas été implémentées directement sur la plate-forme expérimentale. Les algorithmes ont été
testés en premier lieu en simulation. Un simulateur 2D a été programmé sous Matlab afin de Les positions et orientations du véhicule sont définies par X O1, YO1 et q1 (Figure 29). La
simuler le comportement d’un ou plusieurs robots mobiles. Ce simulateur permet hauteur Z O1 est constante. Posons r et l la vitesse angulaire respective des roues droite et
principalement de gérer les communications entre les robots, les 8 capteurs infrarouges la
gauche, R le rayon d’une roue et 2d l’empattement. Si l’on assure constamment un point de
détection d’obstacles et les collisions. Le déplacement des robots est géré par le modèle
contact entre les roues et le sol, les équations cinématiques du véhicule sont données par
géométrique du robot Type 1, deux consignes sont appliquées aux moteurs droit et gauche. Ce
l’équation 1.
simulateur a principalement été conçu pour disposer de résultats rapidement afin de pouvoir
comparer les méthodes et les réglages de paramètres.
 r l
v R 2

 X O1 vC1

YO1 vS1

Z O1 R

q1 R r l

 2d

Avec q1, l’angle de rotation autour de l’axe vertical du véhicule.

Équation 15 : Equations cinématiques

67 60
 La plupart des manipulateurs mobiles réalisés pour la recherche sont constitués d’un
bras manipulateur industriel monté sur une plate-forme mobile conventionnelle. Une telle
configuration engendre une redondance des 3 degrés de liberté de la base, mais en général les
deux composants sont commandés séparément : la base mobile amène le manipulateur dans la
zone de travail. Puis la base reste fixe et la manipulation commence. De cette façon la base et
le manipulateur sont asservis séparément. Quelques travaux antérieurs ont déjà traité la
modélisation et la commande d’un manipulateur mobile comme un seul ensemble, incluant le
couplage entre le bras et la plate-forme. Dans le cas de la manipulation de lourdes charges ou
quand des accélérations importantes sont nécessaires, le couplage en force et inertiel doit être
pris en compte afin d’optimiser la commande des moteurs et d’assurer la stabilité de
l’ensemble.

Dans notre cas, le bras a été spécialement dessiné pour s’adapter sur le robot mobile
Type 1. Nous avons construit un prototype basé sur le principe de la Figure 28. Le bras est
constitué de trois moteurs qui actionnent les axes 1 et 2, ainsi que l’organe terminal. Tous les
moteurs sont fixés sur le châssis, la transmission est réalisée grâce à des poulies, des courroies
et un câble. Ce type de construction permet d’alléger la partie mobile du bras et d’obtenir
ainsi une dynamique particulièrement performante (aucun moteur ne doit supporter le poids
d’un autre actionneur).

Ce manipulateur mobile a été conçu pour être utilisé sur un sol parfaitement plat. Les
coordonnées absolues sont référencées dans le repère fixe (O, X, Y, Z), où le plan (O, X, Y) est
horizontal. Un repère de référence (Oi, xi, yi, zi) est également attribué à chaque corps du
robot : la base Type1 (Corps 1), le bras (Corps 2), l’avant bras (Corps 3) et l’organe terminal
(Corps 4). Ces 4 derniers repères, visibles sur la Figure 29, restent constamment parallèles les
uns aux autres grâce à une transmission à base de courroies et de poulies (Figure 28). Les
poulies ont des diamètres égaux, de telle façon que le bras se comporte comme un double
parallélogramme. Les points de référence Oi sont localisés au milieu des axes, dans le plan de
symétrie du manipulateur mobile. Sur la Figure 29, les lettres majuscules décrivent les
coordonnées relatives aux repères fixes et les lettres minuscules les repères mobiles. Les
vecteurs sont représentés en italique.

Poulies couplées
Actionneur q4 Poulies couplées

Courroie
Courroie
Courroie

Base

Organe terminal
Actionneur q3
Actionneur q2

Figure 28 : La cinématique du bras

59 68
 vers d’autres plate-formes, nous avons opté pour un compilateur C/C++ (Nous avons utilisé
un compilateur C/C++ distribué gratuitement par la société Borland).

Aspect temps réel : même si le DOS n’est pas un système temps réel, il est possible de
garantir l’exécution cyclique d’une tâche. Pour l’asservissement, la consigne appliquée aux
moteurs doit être mise à jour toutes les 10 ms. Nous avons reprogrammé le timer servant de

5
base à l’horloge du PC de sorte à déclencher un TOC toutes les 10ms a lieu des 19.8ms
d’origine. Ensuite l’interruption a été déroutée afin de lancer l’exécution de notre routine
d’asservissement. Diverses mesures ont montré que cette méthode permettait l’exécution de la
routine avec une précision supérieure à 99.9%. Ce timer sert de base pour le reste du
programme, si une tâche doit être exécutée pendant 2 secondes, le programme attendra l’appel
de 200 routines d’interruption, ce qui correspondra à un temps de 200*10ms = 2 secondes.
Cette méthode est complètement transparente pour le reste du programme, puisque lors de
l’appel d’une interruption, les registres du processeur sont sauvegardés, puis restaurés à la fin
de l’exécution de la routine.
5. Algorithmes évolutionnistes pour les
Asservissement : chaque moteur est asservi en vitesse, ce qui nous donne la garantie que les
systèmes multi-robots homogènes consignes appliquées seront respectées indépendamment de la charge des accus. Cela est très
important, surtout lorsque la récompense de l’agent est une fonction de la distance parcourue
ou de la vitesse moyenne du robot. Après avoir identifié les paramètres de notre système,
nous avons expérimenté deux types d’asservissement : un asservissement classique de type
PID et une méthode adaptative (la règle du MIT [Astrom 95]). Le principal avantage de la
seconde est de s’adapter automatiquement à la charge du robot. Mais nous avons estimé que
la complexité des calculs implémentés ne justifiait pas la légère différence de performances
entre les deux méthodes. En effet, le PID donne un résultat d’excellente qualité et cette
performance varie peu selon la charge du robot.

___________________________________________________________________________

Ce chapitre va s’intéresser à l’apprentissage de comportements pour des ensembles de

robots homogènes. Tous les agents formant le système multi-robots seront strictement
identiques et disposeront des mêmes capacités de perception et d’action. Les systèmes multi-
agents distribués peuvent facilement tirer parti du parallélisme du système. C'est-à-dire que
l’on peut diviser une tâche complexe et distribuer à chaque agent une partie de la
problématique. Ici, c’est la tâche d’apprentissage qui sera distribuée. Quelques travaux
antérieurs considèrent le temps de calcul comme le paramètre à optimiser. Or, dans le cas
d’apprentissage appliqué sur des systèmes réels, ce temps de calcul est négligeable par rapport
au temps global nécessaire à l’apprentissage. Dans une expérimentation sur robots réels, le
point le plus long est l’estimation de la performance de chaque comportement. Prenons
l’exemple des algorithmes évolutionnistes : le point le plus long dans l’apprentissage ne sera
pas la réalisation des croisements ou des mutations, mais l’estimation de la population. Pour
Figure 27 : Notre manipulateur mobile miniature M3

69 58
 Les parties électroniques et puissance ont volontairement été découplées afin que estimer la performance d’un comportement, il faut s’assurer que le système a rencontré
l'électronique ne soit pas perturbée par les pics de consommation des moteurs. suffisamment de configurations possibles pour obtenir une performance significative. Dans le
Théoriquement, en utilisation normale, le robot peut être utilisé pendant 97 minutes avant cas d’une tâche d’évitement d’obstacles, il faut que la durée d’une expérience soit
d'atteindre la décharge complète des accus. En pratique, l'expérience la plus longue a duré 90 suffisamment longue pour rencontrer un maximum de configuration d’obstacles (obstacle
minutes. devant, à droite, derrière etc.). Ce temps d’expérimentation est relatif à une durée mécanique,
alors que les temps de calcul de l’algorithme d’apprentissage sont relatifs à une durée
Processeur : Comme processeur, nous avons choisi d'utiliser un PC embarqué sur le robot. logicielle. Le plus long dans l’apprentissage sera bien l’estimation de la performance.
Ce type de processeur, assez gourmand en énergie (environ 10W) présente les avantages
suivants : Afin de diminuer les durées d’apprentissage, le parallélisme des systèmes multi-agents
doit être utilisé à profit. Et ce qui est distribué sur l’ensemble des agents sera l’élément le plus
possibilité d'enregistrer un grand nombre de données et de les conserver hors tension, coûteux (en temps) de l’apprentissage, c'est-à-dire l’estimation de la performance. Ce qui
possibilité d'utiliser des noyaux temps réels, revient à distribuer à chaque individu de la population un comportement à tester. Il semble
grande puissance de calcul, donc que les algorithmes évolutionnistes soient la méthode la plus à-même pour réaliser
grand nombre d'entrées / sorties (BUS ISA). l’apprentissage dans le cas des systèmes multi-robots homogènes. Il faut toutefois ne pas
s’éloigner des hypothèses de départ, à savoir que le système ne doit pas être supervisé. Or, les
Dans les expérimentations présentées ici, nous avons utilisé des architectures basées sur des algorithmes évolutionnistes tel qu’ils ont été formulés par D. Goldberg, demandent de
processeurs 486DX2x66 MHz, avec 8 Mo de RAM et 64 Mo de disque dur Compact Flash. centraliser les séquences génétiques. Un algorithme évolutionniste distribué sera présenté
Le BUS PC104 nous permet d'empiler les cartes en mezzanine et de rajouter des cartes par- dans la deuxième partie de ce chapitre.
dessus le PC afin d'ajouter de nouvelles fonctionnalités au robot.
Des travaux antérieurs ont déjà été menés sur l’utilisation des algorithmes
évolutionnistes appliqués à l’apprentissage de comportements réactifs. Bien que ces travaux
aient été menés avec une approche supervisée, la pertinence des résultats obtenues justifie que
ces travaux soient présentés dans la première partie de ce chapitre.

Choix du système d’exploitation : en premier lieu, il a fallu choisir le système d’exploitation

et, étant donné les contraintes imposées par nos applications, nous avions la possibilité
d’installer les systèmes suivants : Linux, Windows 95 ou le DOS.
Dans un premier temps, une distribution de type Linux semblait le meilleur choix.
Effectivement, des distributions Linux de petite taille sur lesquelles il est possible d’ajouter un
noyau temps réel sont distribuées gratuitement. Seulement, les distributions Linux et " Real
Time Linux " sont particulièrement délicates à installer sur des disques durs de type Compact Les résultats présentés dans cette première partie ont été publiés en 1994 par Dario
Flash. De plus, il est impératif de quitter proprement le système, c'est-à-dire qu’une extinction Floreano et Franscesco Mondada. L’ensemble des résultats et figures présentées ici est extrait
brutale du PC ou une coupure d’alimentation peut endommager les données de façon d'un article de Dario Floreano [Floreano 94]. L’expérience consiste à faire apprendre un
irréversible. comportement réactif à un robot mobile, il s’agit en l’occurrence d’une tâche d’évitement
Un système de type Windows 95 quant à lui permet principalement de disposer d’une d’obstacles. La méthode d’apprentissage utilisée est basée sur les algorithmes génétiques.
interface homme-machine conviviale. Mais ce type de système ne garantit aucunement
l’aspect temps réel des tâches. De plus, comme pour Linux, une extinction brutale du PC peut
endommager le système.
Nous nous sommes donc orientés vers un système de type DOS. Il s’agit d’un DOS Un seul robot sera utilisé pour l’expérience. Afin de pouvoir expérimenter de grandes
6.0 dans sa version de base. Ce choix peut aujourd’hui paraître archaïque, mais présente populations d’individus, les comportements des 80 individus sont testés successivement sur le
nombre d’avantages : le DOS s’installe sans problème sur ce type de machine, c’est un OS de même robot. Il s’agit du robot mobile Khepera [Mondada 89] montré sur la Figure 35. Ce
petite taille. Même si l’aspect temps réel n’est pas garanti sur ce type de système, nous avons robot est de forme cylindrique, son diamètre est de 55 mm. Sa petite taille permet de faire
l’assurance que le programme en cours d’exécution est le seul à utiliser le processeur du PC, évoluer plusieurs robots dans des environnements de taille restreinte. Ici l’unique robot évolue
car le DOS n’est pas un système multi-tâches. Pour des systèmes plus complexes, les dans un environnement de 80x50 cm, montré sur la Figure 36.
limitations du DOS se feront vite ressentir : la gestion du réseau, du BUS PCI et des ports
USB ne sont pas prise en compte. L’objectif est donc d’évoluer en sécurité dans cet environnement c'est-à-dire d’éviter
les obstacles et d’avancer le plus rapidement possible. La récompense instantanée attribuée à
Compilateur : il existe un grand nombre de compilateurs sous DOS, les plus connus étant le l’agent est donnée par l’Équation 28. Ce type de récompense instantanée a été discuté dans le
BASIC, le Turbo Pascal et le C/C++. Afin d’assurer la portabilité des programmes du robot chapitre 3.

57 70
 réfléchissant. Afin de pouvoir généraliser la fonction de transfert liant la valeur numérique
renvoyée et la distance avec l’obstacle, nous l’avons interpolé en utilisant la méthode des
moindres carrés. Les droites en pointillés discontinus représentent les interpolations locales
pour chaque type d’obstacles. Les courbes en pointillés représentent la réponse mesurée du
capteur et la droite continue représente la fonction de transfert effectivement utilisée dans le
robot. Dans les conditions expérimentales de notre laboratoire, les obstacles sont
majoritairement constitués de polystyrène blanc, ce qui n’endommage pas les robots en cas de
collisions et permet une bonne réflexion IR. Nous avons naturellement pris cette réponse
comme référence pour nos expériences (droite continue).

Valeur renvoyée par le capteur Valeur renvoyée par le capteur

Figure 35 : Le robot mobile Khepera

Distance (cm)

Valeur renvoyée par le capteur Valeur renvoyée par le capteur Distance (cm)

Figure 36 : L’environnement de l’expérience (D'après [Floreano 94]) Distance (cm) Distance (cm)

Figure 26 : Réponse des capteurs en fonction de la structure de l’obstacle

Odométrie : les robots sont également équipés de capteurs proprioceptifs : chaque moteur est
Ri V.(1 v ).(1 i) équipé d'un codeur incrémental magnétique. Ces codeurs disposent de deux canaux de 16
où : impulsions par tour de moteur, soit 352 impulsions par tour de roue. Ces capteurs sont utilisés
V est la vitesse moyenne de rotation des deux roues, pour l’odométrie et permettent notamment de calculer la position du robot. Le modèle
v est la différence signée de la vitesse des deux roues, géométrique sera présenté au chapitre 4.3.1. Il faut noter que la dérive est importante et que
i est une valeur proportionnelle à la quantité d'obstacles proches du robot. l’odométrie devra être couplée avec un autre capteur pour estimer la position absolue du
robot. En revanche, elle peut être utilisée localement lors de courts déplacements, par exemple
reculer d’une distance fixe en cas de collision avec un obstacle. Les codeurs sont utilisés dans
Équation 28 : Récompense instantanée attribuée à l’agent (D'après [Floreano 94]) la boucle de retour de l’asservissement. Ils renvoient une information sur la vitesse de
chacune des roues.
Le comportement de l’agent est régi par un contrôleur neuronal. Le but de
l’apprentissage est donc de déterminer les poids synaptiques optimaux de ce réseau de Énergie : Le robot est alimenté par deux accus NiMH de 1300mAH chacun. Un accus de
neurones. Les poids sont codés dans la séquence chromosomique de chaque agent. 12V alimente toute la partie électronique et un second de 6V alimente la partie puissance
(moteurs et émission infrarouge).

71 56
 Voici les paramètres utilisés pour l’algorithme génétique :

Type 1 est un robot mobile autonome équipé de deux roues différentielles montées sur des Taille de la population : 80 individus
moteurs à courant continu. La photo de la Figure 25.a montre le châssis du robot équipé des Nombre de générations : 100
moteurs, des roues et des billes porteuses qui assurent la stabilité du robot. Ce robot est de Probabilité de croisement : 0.1
forme cylindrique, d'environ 13 cm de diamètre et 12 cm de hauteur. Les plans des cartes Probabilité de mutation : 0.2
électroniques sont détaillé dans l'Annexe B. Intervalle de mutation : ± 0.5
Intervalle initial des poids : ± 0.5
Les capteurs de proximité : Une ceinture de capteurs infrarouges (IR) permet aux robots de Intervalle final des poids : non borné
détecter les obstacles, mais aussi de communiquer localement. Cette ceinture est constituée de Durée de vie d’un individu : 80 actions
8 capteurs et 16 émetteurs. Ces 8 capteurs infrarouges sont uniformément répartis sur la Durée d’une action : 300ms
périphérie du robot (Figure 25.c). La portée des capteurs peut être ajustée de quelques
centimètres à quelques mètres, soit par logiciel, soit de façon matérielle. Ces capteurs
(développés par la société Wany Robotics) sont basés sur la mesure de l’amplitude de l’onde
réfléchie par les obstacles. Ils sont également utilisés pour permettre aux robots de Le robot mobile Khepera a été capable d’apprendre une stratégie d’évitement
communiquer localement. Dans le cas de communications locales, la portée est supérieure au d’obstacles en moins de 100 générations. L’évolution de la performance est montrée sur la
double de la celle mesurée dans les cas de détection d’obstacles. En effet, en détection Figure 37. L’estimation d’une génération dure environ 39 minutes. Après 50 générations
d’obstacles, l’onde IR doit parcourir deux fois le trajet entre le robot et l’obstacle, une fois à environ, les meilleurs individus ont développé une stratégie proche de l’optimale, leurs
l’aller puis une fois au retour. De plus, une partie de l’onde est absorbée par l’obstacle. Dans trajectoires sont fluides et ils évitent les obstacles. Ce qui leur permet de faire le tour complet
le cas d’une communication directe, l’onde doit juste parcourir la distance entre les deux du corridor. La disposition des capteurs n’est pas symétrique sur un robot Khepera. L’avant
robots. du robot dispose de six capteurs et l’arrière seulement deux. La fonction de récompense ne
prenant pas en compte la vitesse signée du robot, aucun sens de déplacement n’est imposé au
a b robot. Et pourtant, une direction prioritaire émerge au fil des générations, le robot se déplace
dans la direction la mieux représentée par les capteurs.

c d

Figure 25 : Détails du robot Type 1

Figure 37 : Performance moyenne de la population et du meilleur individu en fonction des générations
Afin de pouvoir utiliser les capteurs de l’agent, nous avons étudié leur réponse en (D'après [Floreano 94])
fonction de l’obstacle. La Figure 26 montre la réponse du capteur sur quatre types
d’obstacles : un obstacle blanc, un bleu, un rouge et un obstacle constitué de papier

55 72
 Afin de tester et comparer les méthodes, nous avons mis au point une plate-forme
expérimentale complète. Cette plate-forme est constituée de quatre robots mobiles (Type 1);
ces robots ont principalement été construits dans l’optique de réaliser des expériences sur des
systèmes hétérogènes. Cette même plate-forme a d’ailleurs été utilisée pour valider les
travaux d’Olivier Simonin et de Jacques Ferber en 2000 [Lucidarme 02] portant sur l'étude de
l'architecture Satisfaction / Altruisme.

Ces travaux de thèse s’intègrent au sein des recherches actuelles du laboratoire. C’est
pourquoi notre plate-forme expérimentale doit pouvoir rester générique et non dédiée à une
application typique. Nous avons choisi de compléter le parc de robots homogènes par une
plate-forme hétérogène inspirée du concept de l’aveugle et du paralytique : ce concept,
proposé par A. Liègeois et P. Rongier [Rongier 01], consiste à classer les agents en deux
catégories :

les aveugles : ce sont des agents qui ne possède soit aucune perception de
l’environnement, soit une perception réduite. En contrepartie, ces agents peuvent agir
sur l’environnement, se déplacer, prendre des objets etc,
Figure 38 : Evolution de chacun des paramètres de la récompense au fil des générations (D'après
[Floreano 94]) les paralytiques : ces agents ne peuvent interagir avec l’environnement, ils ne sont pas
équipés de bras manipulateur, voire de moyen de locomotion. En revanche, ils ont une
perception plus fine de l’environnement.
Les trois composantes de la récompense ont été découplées afin de pouvoir étudier
l’évolution de l’apprentissage (Figure 38). Chaque point représente la position dans l’espace L’hypothèse de départ était de travailler sur des systèmes en mode dégradé : les
d’état du meilleur agent de la génération. Dans un premier temps, les agents cherchent à aveugles sont des agents dont le système de vision est défaillant et les paralytiques des agents
diminuer le nombre de collisions. En réalité le contrôleur neuronal sait de mieux en mieux dont le système de locomotion n’est plus utilisable. L’idée globale de ce genre de système est
discriminer les obstacles des zones libres. Une fois que l’agent sait se déplacer en évitant les inspirée d’une fable de Jean Pierre de Florian de Clarisse où un aveugle et un paralytique
obstacles, il incrémente progressivement la vitesse de déplacement en conservant ses s’allient afin de diminuer leurs misères respectives. Grâce aux communications directes entre
propriétés d’évitement d’obstacles. D’autres résultats montrent également la stabilité du les agents, il est facile d’imaginer un système où les agents paralytiques guident les agents
système. L’expérience consiste à écarter les comportements du point d’adaptation et à aveugles dans leurs actions. Notre plate-forme expérimentale a été conçue tout en restant
observer la réaction du système: les agents retournent automatiquement dans la position fidèle à ce concept. Nous avons construit en premier lieu un manipulateur mobile
initiale d’équilibre. miniature(M3) de type aveugle qui ne possède pas de vision fine, en revanche il peut
doublement agir sur l’environnement : par la locomotion et par l’utilisation du bras
manipulateur. Nous avons ensuite construit un système de vision stéréoscopique (BOP) qui ne
dispose d'aucun moyen d’action sur l’environnement, mais qui peut avoir une perception très
fine du monde.
Nous venons de présenter des travaux et résultats antérieurs, qui démontrent déjà la
possibilité d’appliquer des méthodes évolutionnistes sur des ensembles de robots mobiles.
Bien que ces résultats expérimentaux n’aient été obtenus que sur un seul robot mobile, cela
n’enlève en rien aux conclusions scientifiques relatives aux systèmes multi-robots. D’ailleurs,
disposer de 80 robots évoluant en parallèle dans des environnements différents ne changerait
pas les résultats.
Le robot Type 1 représentant la base de la plate-forme est un robot de petite taille et
Ces résultats montrent qu’une population d’agents peut apprendre un jeu de stratégies évolutif. Nous disposons d'une plate-forme de quatre robots mobiles Type 1. Voici les
et de comportements en s’adaptant à sa propre structure et à son environnement. Deux critères principales contraintes qui forment le cahier des charges :
principaux ont émergé : la sélection naturelle d’un sens de déplacement et l’adaptation
automatique de la vitesse de l’agent. L’agent a naturellement déterminé la vitesse optimale de puissance de calcul embarquée,
déplacement permettant de maximiser la récompense, sans pour autant percuter d’obstacles. A 45 minutes d'autonomie énergétique minimum,
la vue de ces résultats, l’analogie avec le vivant se fait clairement ressentir. Et c’est une fois vitesse du robot atteignant les 1 m.s-1,
de plus le vivant qui va nous inspirer la suite de ses travaux. Afin de pouvoir appliquer ces ceinture de capteurs de proximité,
méthodes sur des systèmes multi-robots, une version distribuée des algorithmes communications locales entre les robots,
évolutionnistes est proposée dans la deuxième partie de ce chapitre. possibilité de rajouter des cartes avec de nouvelles fonctionnalités.

73 54
 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

4
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.

4. Notre plate-forme expérimentale 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.

La tâche étudiée est basée sur la navigation d’un ensemble de robots mobiles dans un
environnement inconnu. Il ne s’agit en aucun cas de construire une carte ou une quelconque
représentation de l’environnement, mais de déterminer un ou plusieurs comportements
réactifs permettant aux robots de naviguer dans l’environnement en toute sécurité. Les
expériences ont été menées sur les robots mobiles Type 1. Les entrées du système sont les
capteurs de distances et les sorties, les deux moteurs du robot. Afin de diminuer les temps
d’apprentissage les entrées et sorties du système ont été grossièrement discrétisées. Les
___________________________________________________________________________ entrées du système sont rassemblées en 5 états et les sorties en 4 actions. L’objectif de
l’apprentissage étant d’associer à chaque état la meilleure action. Les différents états sont
présentés sur le Tableau 4 et les actions sur le Tableau 5.

Ce système présente 1024 (45) combinaisons, néanmoins l’objectif n’est pas de

Les travaux sur l’apprentissage que nous avons étudiés précédemment n’étaient pas montrer que les algorithmes évolutionnistes peuvent résoudre des problèmes complexes. Mais
toujours appliqués à la robotique. Les applications les plus fréquentes sont la résolution de simplement de montrer qu’il existe des alternatives distribuées aux méthodes supervisées. Si
problèmes mathématiques, la recherche d’optimum dans des fonctions complexes ou encore les hypothèses considérées avaient été exactement les mêmes que pour l’expérience menée à
la recherche de stratégies gagnantes dans des jeux comme les échecs ou le célèbre joueur de l’EPFL décrite précédemment, il aurait fallu mettre en œuvre simultanément 80 robots. En
backgammon programmé par Tesauro [Tesauro 94]. Ces applications, comme les premiers supposant que la relation liant les temps d’apprentissage au nombre de robots et de
travaux appliqués à la robotique, étaient simulées sur un ordinateur. Rapidement, des générations soit linéaire, la durée des accus ne nous aurait pas permis de dépasser la 11ème
différences notables entre le monde simulé et l’environnement réel ont empêché une génération avec 5 robots. Alors qu’il en faut une centaine pour obtenir la convergence. C’est
transposition exacte des résultats simulés vers de véritables plate-formes. C’est pour cette pourquoi nous avons choisi de discrétiser les états et actions.
raison que la nécessité d’expérimenter les méthodes proposées sur de véritables robots
mobiles s’est faite ressentir. Parmi les contraintes imposée : les temps d’apprentissage doivent
être inférieurs aux temps de décharge des accus, les méthodes doivent être robustes vis à vis
des pannes, de la décharge des batteries et du bruit, qu’il s’agisse aussi bien de celui des
capteurs, que celui des actionneurs.

53 74
 Etat 1 Pas d’obstacle
Etat 2 Un obstacle à gauche
Etat 3 Un obstacle à droite
Etat 4 Un obstacle devant
Etat 5 Le robot est bloqué

Tableau 4 : Différents états du système

Action 1 Avancer
Action 2 Tourner à droite
Action 3 Tourner à gauche
Action 4 Reculer

Tableau 5 : Jeu d’actions possibles

La chaîne chromosomique est une concaténation de N mots {0,1} dans le sous-espace

M. N est le nombre d’entrées et M le nombre de sorties. Bien sûr il n’y a qu’un seul 1 dans
chaque espace N (Figure 39). Les générations de robots vont évoluer selon les transformations
de ces chaînes embarquées sous l’action des opérateurs génétiques.

0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0

Figure 39 : Un exemple de chaîne chromosomique

Dorénavant, les croisements ne se font plus sur l’ensemble de la population, mais sur
un couple d’individus. Il a donc fallu réviser les conditions et les opérateurs de mutations et
de croisements.

Initialisation : au début, les différentes chaînes chromosomiques peuvent être remplies

aléatoirement ou toutes initialisées à la même valeur. Dans les expériences décrites dans le
présent chapitre, les chaînes sont initialisées aléatoirement.

Estimation de la performance individuelle : Dans les algorithmes génétiques classiques et

d’autres techniques d’apprentissage, c’est parfois la couche supérieure qui calcule la
performance de chaque individu. Ces individus sont alors classés avant d’y appliquer les
opérateurs génétiques. Ici, au contraire, comme nous recherchons une estimation autonome de
la performance, une capacité d’auto-évaluation locale de la performance est attribuée à chaque
individu qui n’est jamais conscient de la performance globale de l’ensemble de la population.

En suivant les principes de base des algorithmes d’auto-apprentissage, chaque individu

calcule sa propre récompense courante (Équation 29).

75 52
Le coût : La plupart des méthodes d'apprentissage sont présentées comme cherchant à R N ( i ) (i ) (1 (i )) R N (i ) 1 (i ) ( i ) F N ( i ) (i )
maximiser la récompense. L'objectif de la tâche peut aussi être de minimiser un critère, par
exemple une consommation d'énergie ou un temps de déplacement. Dans ces cas, on parle de
coût et non de récompense. Mathématiquement, minimiser une fonction de coût peut toujours Où :
se ramener à maximiser une récompense. 1
(i)
Les récompenses retardées : Une récompense retardée est attribuée à la fin d'une séquence 1 N (i )
d'actions. Elle estime la performance de l'ensemble de ces actions. Un exemple de
récompense retardée est le Tic-Tac-Toe présenté ci-dessus. Le joueur est récompensé à la fin N(i) est le nombre de pas élémentaires depuis le début de l’estimation par l’agent i
de la partie pour l'ensemble de ses coups. Ce type de récompense est parmi les moins RN(i)(i) est la récompense courante estimée à l’instant N(i)
contraignants. FN(i)(i) est la récompense instantanée à l’instant N(i)

Équation 29 : Calcul de la récompense courante de l’agent i

Nous avons présenté différentes techniques d’apprentissage possédant chacune leurs Dans le problème d’exploration étudié ici, la récompense instantanée est calculée
propres spécifications : les réseaux de neurones peuvent apprendre à mimer des fonctions comme étant la distance signée parcourue durant un pas élémentaire. De fait, la récompense
mathématiques à partir d’une base d’exemples, l’apprentissage par renforcement permet courante associée à la stratégie en cours (liée à la chaîne chromosomique) est la distance
d’apprendre des stratégies sans intervention extérieure, ni même d’exemple, enfin les moyenne parcourue depuis l’initialisation ou depuis le dernier changement dans la chaîne
algorithmes évolutionnistes peuvent faire évoluer des comportements afin d’en améliorer chromosomique par croisement ou mutation. Une telle récompense pénalise les trajectoires
leurs performances. non rectilignes.

Mais aucune de ces techniques ne peut résoudre à elle seule la problématique qui nous Croisements : la plupart des solutions existantes font généralement appel à une
est imposée ici. Les réseaux de neurones demandent des exemples pour pouvoir fonctionner, communication globale entre les agents. De cette façon, l’approche traditionnelle est utilisée :
ils sont incapables de générer d’eux-mêmes une stratégie permettant de résoudre un problème la sélection est réalisée sur l’ensemble de la population. Afin de contourner les problèmes liés
ou un conflit. Si l’apprentissage par renforcement permet d’apprendre sans exemple une à cette approche, la solution proposée ici est basée sur des communications locales. De cette
stratégie optimale, cette technique demande de discrétiser l’univers en états et actions façon, un couple de robots se rencontrant peut ainsi réaliser des croisements. Il résultera de
échantillonnés. Or, une quantité importante de données doit pouvoir être stockée, ce qui peut ces croisements deux nouveaux individus. Les conditions formelles sont les suivantes :
alors être disproportionné au regard des capacités de stockage actuelles. Enfin, si les
algorithmes évolutionnistes semblent bien appropriés à notre problématique, il n’en reste pas la distance inter-robots est faible,
moins que c’est une technique supervisée. Le point faible réside dans le rassemblement des les deux robots n’ont pas récemment réalisé de mutations ou de croisements.
séquences génétiques pour pouvoir réaliser les croisements et les mutations.
La première condition est nécessaire pour garantir les communications entre les robots. La
Les techniques présentées dans ce chapitre représentent pour nous des outils qui seconde évite qu’un robot ne change sa chaîne chromosomique avant d’avoir complètement
permettent d’appliquer l’apprentissage sur nos systèmes. Comme nous venons de le voir, évalué sa stratégie courante durant une durée suffisante. Quand les croisement sont
aucune de ces techniques ne peut être appliquée tel quel afin de répondre à la problématique réalisables, les agents i et j disposent de deux nouvelles chaînes chromosomiques selon la
donnée. C’est pourquoi nous allons, dans les chapitres suivants, présenter des versions probabilité donnée par l’Équation 30.
améliorées, voire combiner plusieurs techniques afin de répondre aux critères imposés. Afin
de tester et valider les techniques proposées nous disposons d’une plate-forme expérimentale
sur laquelle les méthodes sont testées. Cette plate-forme est présentée dans le chapitre suivant.
R N ( i ) (i )
P (i )
R N (i ) (i ) RN ( j) ( j)

Équation 30 : Probabilité que la chaîne i se retrouve dans les générations futures suite à un croisement
entre les agents i et j

Les croisements ne sont pas suffisants pour assurer la convergence du système vers la
solution globalement optimale, particulièrement lorsque la taille de la population est faible.
Dans ce cas, les agents peuvent être attirés par un minimum local et la population restera

51 76
bloquée dans cet état final. Les mutations sont donc nécessaires pour extirper le système des évident, mais des récompenses trop contraintes sont parfois utilisées et elle verrouillent
solutions locales et pour explorer plus largement l’espace d’état. l'apprentissage dans une stratégie qui n'est pas nécessairement optimale. Dans [Madani 02],
l'auteur explique "Pour notre application la fonction de renforcement choisie permet de
Mutations : dans les algorithmes génétiques traditionnels, les mutations sont réalisées de délivrer un signal +0.5 lorsque le robot choisit une bonne action (récompense) et -0.5 pour
façon aléatoire. Ici, cela pourrait être un inconvénient, puisque l’objectif est de réaliser un une mauvaise (punition)". Si les bonnes et les mauvaises actions sont connues par avance,
apprentissage de type "on-policy". Il n’est pas admissible qu’un robot puisse changer sa l'apprentissage n'a aucun intérêt. Il s'agit dans cet article d'un ralliement de cible avec
stratégie pour une moins bonne et attende longtemps pour retrouver une chaîne évitement d'obstacles; une récompense moins contraignante aurait pu être :
chromosomique acceptable par croisement ou mutation. Pour résoudre ces problèmes, la
stratégie de mutation suivante a été adoptée : +1 lorsque la cible est atteinte,
-1 en cas de collision avec un obstacle,
Les agents n’ont pas réalisé de mutation récemment 0 sinon.
La performance courante de l’agent est faible
Un autre exemple intéressant est l'apprentissage d'un comportement d'évitement d'obstacles
Comme pour les croisements, la première condition garantit que l’agent dispose de [Floreano 94]. Il est important de préciser que l'expérience se déroulait dans un
suffisamment de temps pour estimer correctement sa propre performance. La seconde environnement très contraint. La récompense est donnée par l’Équation 14.
condition évite de dégrader une stratégie qui serait correcte. La probabilité de mutation d’un
agent est une fonction de l’estimation courante de la performance. Cela permet de garantir que Ri V.(1 v ).(1 i)
les stratégies les plus mauvaises ont davantage de chances de muter, contrairement aux où :
bonnes stratégies qui, elles ont une faible probabilité (non nulle, ce qui leur permet de V est la vitesse moyenne de rotation des deux roues,
s’extraire des minimum locaux).
v est la différence signée de la vitesse des deux roues,
i est une valeur proportionnelle à la quantité d'obstacles proches du robot.

Équation 14 : Récompense instantanée attribuée à un robot mobile pour une tâche de navigation sans
Différents protocoles de communication ont été présentés dans le chapitre consacré collision (D'après [Floreano 94])
aux systèmes multi-agents. Tous ces protocoles sont globaux, or, ici les agents ne réalisent
que des communications locales. De plus, les robots utilisent les mêmes capteurs pour les Cette estimation de la performance se divise en trois termes: le premier tend à
communications et pour la détection d’obstacles. Il a donc été nécessaire de proposer un maximiser la vitesse du robot, le second, à récompenser les trajectoires rectilignes et le
protocole dédié à cette application. Voici les hypothèses inhérentes au système : dernier à minimiser les collisions. Ma première analyse a été de penser que maximiser la
vitesse des deux roues revenait à minimiser la vitesse de rotation du robot et que les deux
• pas de synchronisation, premiers termes étaient redondants, voire contraignants. Francesco Mondada (qui est l’auteur
• utiliser la même bande passante pour les capteurs et pour les communications. de [Floreano 94]) a expliqué que l'environnement était tellement contraint qu'une des
meilleures stratégies trouvée par le robot était de tourner en rond sur place, maximisant ainsi
la vitesse moyenne des deux roues et minimisant le nombre de collisions. Il a donc choisi
d’adapter la récompense à l’environnement et par conséquent l’apprentissage ne sera valide
que dans des cas où l’environnement sera très contraint.

J'ai classé les différents types d'estimations de la performance en 4 catégories :

L'erreur : Utilisée dans les réseaux de neurones, l'erreur donne une information
proportionnelle à la différence entre la sortie désirée et la sortie obtenue. De plus lorsque la
sortie du système est un vecteur, l'erreur est également un vecteur de même dimension. Cette
estimation de la performance est la plus contraignante car elle exige un modèle de
comportement connu et fait tendre l'apprentissage à copier ce modèle.

Les récompenses instantanées : Les récompenses instantanées donnent une estimation de la

performance correspondant à la stratégie courante. Contrairement à l'erreur, même si la sortie
du système est un vecteur, la récompense instantanée est un paramètre unidimensionnel. La
Figure 40 : Détail du protocole de communication. récompense présentée par l’Équation 14 est un exemple de récompense instantanée.

77 50
solution optimale et la stabilité du système est atteint après une quarantaine de générations. Une trame du protocole commence systématiquement par une détection d’obstacle, la
En réalisant l'apprentissage plusieurs fois, on trouve 4 résultats équivalents (L'objectif était carte locale est mémorisée afin de déterminer l’état courant du système. Ensuite vient une
d'atteindre le chiffre 142) : phase d’écoute (l’agent n’émet aucune information). Si l’agent ne détecte aucun autre agent, il
termine son cycle sensori-moteur. Si des infrarouges sont perçus durant la phase d’écoute,
(( 7 * 25 ) – 7 ) – 25 = 143 cela signifie que l’agent n’est pas seul. Deux possibilités apparaissent alors :
(( 25 * 7 ) – 7 ) – 25 = 143
(( 7 * 25 ) – 25 ) – 7 = 143 Les informations reçues sont décodées comme une trame de synchronisation valide,
(( 25 * 7 ) – 25 ) – 7 = 143 l’agent émet sa propre trame, puis les deux agents s’échangent leurs chaînes
chromosomiques et leurs estimations de la performance.
Les informations reçues ne sont pas décodées comme une trame de synchronisation
valide, l’agent émet sa propre trame et attend celle de l’autre agent. Une fois la
synchronisation réussie, les deux agents s’échangent leurs chaînes chromosomiques et
Les algorithmes évolutionnistes semblent particulièrement bien indiqués pour leurs estimations de la performance.
l’apprentissage des systèmes multi-agents. En premier lieu, il faut disposer d’une population
d’individus, ce qui est le cas dans tout système multi-robots. Ensuite, la possibilité de coder Ce protocole ne nécessite pas de synchronisation globale entre les agents. Une
toutes sortes de comportements dans la chaîne chromosomique ouvre un grand nombre de synchronisation s’effectue entre les deux agents sur le premier front descendant valide durant
possibilités. Toutefois, la méthode est supervisée : après chaque expérience, l’ensemble des la réception de la trame de synchronisation.
chaînes chromosomiques doit être rassemblé pour construire la génération suivante. Ce type
d’apprentissage demande de centraliser les données. De plus, les agents ne peuvent pas
toujours interrompre leur tâche courante pour réaliser les croisements.

Les expérimentations ont été réalisées en simulation, mais également sur la plate-
forme réelle. Le simulateur a été réalisé sous Matlab, ce qui nous permet de réaliser une
analyse rapide des résultats. Le code source est composé de deux parties : un environnement
rectangulaire composé d’objets fixes et les agents mobiles. Les agents ne calculent jamais ni
Il était impossible de clôturer ce chapitre sans discuter d’un point clef de toute méthode
leur position courante, ni leur orientation dans l’environnement. La connaissance de ces
d’apprentissage : l’estimation de la performance. Appelée différemment selon les méthodes
variables n’est utilisée que pour l’affichage. Les capteurs sont simulés et offrent une
(la récompense pour le Q-Learning, l'aptitude pour les algorithmes génétiques ou encore
perception locale aux agents. Le modèle géométrique du robot Type 1 est implémenté dans le
l'erreur pour les réseaux de neurones artificiels) l'estimation de la performance est un
simulateur. Une capture d’écran du simulateur est montrée sur la Figure 41 (Les zones
paramètre essentiel de l'apprentissage. Le principal intérêt de l'apprentissage est de laisser
délimitées en pointillés montrent la distance de communication entre les agents.).
l'agent trouver par lui-même la meilleure stratégie pour maximiser la récompense. Si la
récompense est trop contrainte, l'apprentissage ne présente aucun avantage par rapport aux
méthodes traditionnelles. Prenons l'exemple extrême du Morpion (Tic-Tac-Toe en anglais) où
deux adversaires s’affrontent en disposant des croix et des cercles sur une grille carrée de 3
cases de côté. Le premier qui aligne trois symboles remporte la partie. Si le joueur est
récompensé de la façon suivante :

+1 si c'est un bon coup,

0 sinon.

la récompense suppose de connaître a priori les bons coups. De ce point de vue,

l'apprentissage n'a aucun lieu d'être utilisé, autant programmer tous les bons coups. En
revanche, si l'agent est récompensé de la manière suivante:
Figure 41 : Capture d’écran du simulateur avec des obstacles circulaires
+1 en cas de victoire,
-1 en cas de défaite, Les mêmes expériences ont été réalisées sur la plate-forme expérimentale (Figure 42).
0 en cas de match nul. Le site expérimental mesure 4.80 x 3.60 m. Quatre robots autonomes Type 1 ont été utilisés
pour l’expérience. Les obstacles peuvent être déplacés, ajoutés ou supprimés. La vitesse
Dans ce cas, l'agent devra trouver les meilleurs coups à jouer pour maximiser sa maximale des robots est de 1m/s, mais elle a été limitée à 0.3m/s pour protéger le matériel des
récompense qui ne lui sera accordée qu'à la fin de la partie. Ce petit exemple peut paraître collisions violentes. La portée des infra-rouges utilisés pour les capteurs et pour les

49 78
communications peut être ajustée. Une portée typique de 0.5m a été adoptée : ce qui permet 0 1 0 1 0 0 0 0 1 0 1 0 1 1
un compromis entre le besoin de réaliser des croisements et la sécurité quant à la distance de 25 - 24 + 30 * 7
détection des obstacles.
Individu géniteur 2
1 0 1 1 0 1 1 0 1 1 1 0 1 1
30 / 25 * 7 * 7

Individu de la génération suivante

0 0 0 1 0 1 1 0 1 1 1 0 1 1
24 - 25 * 7 * 7

Figure 22 : Exemple de croisement uniforme pour le problème du juste chiffre

Les mutations : Les mutations effectuent une modification à partir d’une seule chaîne
initiale. Les mutations consistent à complémenter l’un des bits de la chaîne initiale (Figure
23). Les mutations permettent notamment d’obtenir des individus avec de nouvelles
propriétés qui n’auraient pas été accessibles en ne réalisant que des croisements à partir de la
population initiale.
Figure 42 : Photo d’une expérimentation
11101111001 11101101001
Figure 23 : Exemple de mutation
Pendant un cycle sensori-moteur élémentaire, chaque agent met à jour son état courant
et continue de réaliser des mutations et des croisements (si cela est possible). Les simulations
ont été utilisées pour étudier l’influence de chaque paramètre sur le système, en commençant Comme pour l’opérateur de croisement, lorsque la chaîne représente des valeurs
par le délai de mutation. Si celui-ci est trop court, les mutations sont réalisées fréquemment, numériques, une mutation sur un bit de poids fort n’a pas la même influence que la même
l’espace d’état est rapidement exploré, mais les estimations sont erronées. Au contraire, opération sur un bit de poids faible. Des opérateurs de mutation numériques sont parfois
lorsque le délai est long, les estimations sont excellentes, mais l’exploration de l’espace d’état utilisés, le principe est de réaliser un tirage aléatoire centré sur la valeur numérique codée
est longue. Le délai entre deux croisements a également été étudié: les conclusions sont dans la chaîne initiale.
proches de celles des mutations. Si le délai est trop court, les agents vont constamment
réaliser des croisements avec le même congénère. Au contraire, si ce délai est long, Erreur
l’exploration de l’espace d’état est fastidieuse. La condition suivante a été choisi pour
déterminer le temps minimal entre deux croisements : deux agents qui viennent de réaliser des
croisements se sont suffisamment éloignés pour ne pas recommencer juste après. En
simulation, 300 cycles sont nécessaires. En considérant les valeurs numériques précédentes, le
temps minimum entre deux croisements successifs a été réglé à 3 secondes sur les robots pour
les mêmes raisons que précédemment.

La Figure 43 montre la fin d’une simulation. La première observation est que

l’ensemble de l’environnement est exploré (en blanc): c’est un comportement émergent dû à
la réactivité du système multi-agents.

1 : Pas d’obstacle 1 : Avancer

2 : Un obstacle à gauche 2 : Tourner à droite
3 : Un obstacle à droite 3 : Tourner à gauche Générations
4 : Un obstacle devant 2 ou 3 : Tourner à droite ou à gauche
Figure 24 : Evolution du meilleur individu au fil des générations
5 : Le robot est bloqué 4 : reculer
Tableau 6 : Séquence chromosomique optimale
Si l'on reprend l'exemple du juste chiffre présenté précédemment, un exemple de
croisement est présenté sur la Figure 22. L'apprentissage a été réalisé sur une population de 20
individus. L'évolution du meilleur individu est montré sur la Figure 24. On distingue que la

79 48
 Les croisements double points. Le principe est assez proche des croisements simple
point, à cette différence qu’il y a deux points de séparation des chaînes, la chaîne
initiale est divisée en 3 parties et la combinaison de ces 3 parties permet d’obtenir
deux nouvelles chaînes.

Les croisements uniformes. Le masque de croisement est choisi aléatoirement, chaque

bit peut être choisi indépendamment du reste de la chaîne.

Croisement simple point :

Individu 1 Individu 2 Figure 43 : Exploration de l’environnement
11001001010 11101111001
Masque La stratégie optimale est constamment atteinte quelques soient les conditions initiales
11111100000 du système. Un autre paramètre important est la taille de la population, c'est-à-dire le nombre
d’agents dans le système. Intuitivement, les temps de convergence semblent inversement
proportionnels au nombre d’agents. Les expériences ont été stoppées lorsque l’ensemble de la
11001011001 11101101010
population a trouvé la solution optimale, c'est-à-dire que tous les individus ont comme chaîne
chromosomique la séquence présentée sur le Tableau 6. Pour chaque taille de population, 20
Croisement double point : simulations ont été réalisées et le temps de convergence moyen a été enregistré. Les résultats
sont présentés sur la Figure 44.
Individu 1 Individu 2
11001001010 11101111001
Masque Temps de convergence
11110001111

11001111010 11101101010

Croisement uniforme :

Individu 1 Individu 2
11001001010 11101111001
Masque
10011010110
Nombre d’agents

11101101011 11001011000 Figure 44 : Temps de convergence en fonction de la taille de la population

Figure 21 : Opérateurs de croisement sur des chaînes binaires La Figure 44 montre qu’en dessous de 10 robots, le temps de convergence moyen
Il est assez courant d’utiliser la chaîne chromosomique pour y coder des valeurs décroît rapidement avec le nombre de robots. Au-delà de 10 robots, le temps de convergence
binaires, entières ou réelles. De ce fait, les bits de la chaîne n’ont pas tous la même devient constant. Ce phénomène est dû à la propagation de la solution optimale : lorsque la
importance ; un changement sur un bit de poids fort n’a pas la même influence qu’une population est grande, l’espace d’état est rapidement exploré et la solution optimale est vite
modification sur un bit de poids faible. Pour que le sens des croisements soit justifié, des trouvée. En revanche, il faut un temps non négligeable pour la propager à travers toute la
opérateurs numériques sont parfois utilisés : on réalise par exemple une moyenne pondérée population et il n’est pas possible de descendre en dessous de ce temps minimal avec un
des valeurs numériques des deux parents. protocole de communication locale.

Individu géniteur 1

47 80
L’évolution de la stratégie peut se décrire de la façon suivante : Prenons pour exemple le problème du juste chiffre : nous disposons de quatre nombres
et le but est de s’approcher le plus près possible d’un cinquième nombre en réalisant des
1. Au début, les agents tentent des stratégies aléatoires. Une collision intervient opérations arithmétiques avec les 4 premiers. Nous supposerons que les opérateurs sont :
rapidement et le robot est bloqué. La récompense courante décroît, permettant aux l’addition, la multiplication, la soustraction et la division. Nous émettrons également comme
mutations de se multiplier jusqu’à ce que l’état 5 (le robot est coincé) soit associé à hypothèse que l’opération arithmétique doit être constituée de trois opérateurs sans priorité (il
l’état 4 (Reculer). n’y a pas de parenthèse dans l’opération). Par exemple, si les chiffres sont : 24 25 30 et 7 et
2. Les agents évoluent dans l’environnement au gré des mutations et l’un d’eux finit par que le résultat doit être 142, une bonne solution sera : 24 * 25 = 600 / 30 = 20 * 7 = 140. Si un
associer l’état 1 (aucun obstacle) à l’action 1 (avancer). Il parcourt généralement de algorithme génétique est utilisé pour résoudre ce problème, la chaîne chromosomique pourra
longues distances dans l’environnement tout en propageant (par croisement) sa chaîne être constituée de 14 bits : 8 bits pour les 4 nombres (Tableau 1) et 6 bits pour les 3 opérateurs
chromosomique aux autres agents. (Tableau 2). Un exemple de chaîne chromosomique est donné sur le Tableau 3.
3. Comme les agents commencent à se déplacer avec fluidité dans l’environnement, les
rencontres se multiplient et davantage de croisements sont réalisés. La stratégie Codage Nombres
optimale est attribuée à un des agents, qui voit sa performance augmenter. 00 24
4. Dès qu’un agent réalise la stratégie optimale, il voyage à travers l’environnement sans 01 25
collision. Il rencontre et transmet sa chaîne chromosomique à d’autres agents, 10 30
propageant rapidement la stratégie à l’ensemble de la population. 11 7
Tableau 1 : Codage des chiffres dans la chaîne chromosomique

Codage Opérateurs
Ce chapitre a traité de l’apprentissage de comportements réactifs pour les systèmes 00 +
homogènes. L’hypothèse de départ est la suivante : les méthodes évolutionnistes sont les plus 01 -
à-même de traiter ce genre de problème. L’estimation de la performance étant la phase de 10 *
l’apprentissage la plus coûteuse, c’est cette phase qu’il nous est paru judicieux de distribuer. 11 /
Dans la première partie de ce chapitre, une expérience d’apprentissage évolutionniste mené à Tableau 2 : Codage des opérateurs dans la chaîne chromosomique
l’EPFL a été décrite.
0 1 0 1 0 0 0 0 1 0 1 0 1 1
L’objectif était de faire apprendre à un robot mobile une stratégie d’évitement
25 - 24 + 30 * 7
d’obstacles. Le contrôleur du robot est un réseau de neurones et l’apprentissage servait à
déterminer les poids synaptiques optimaux permettant une navigation fluide sans collision.
L’expérience a montré qu’après l’évolution de 100 générations de 80 individus une stratégie Tableau 3 : Exemple de chaîne chromosomique pour le problème du juste chiffre
optimale est effectivement trouvée. Cette évolution peut se découpler en paliers qui
correspondent chacun à une phase de l’apprentissage. Toutefois la méthode employée est de
type supervisée, c’est pour cette raison que nous avons proposé une méthode évolutionniste
distribuée.

Dans la deuxième partie de ce chapitre, une méthode totalement distribuée a été Les opérateurs génétiques sont utilisés pour générer la population suivante. On distingue deux
proposée. Les croisements et les communications ne se font plus sur l’ensemble de la types d’opérateurs : les opérateurs de croisement, qui réalisent une opération sur deux
population, mais sur un couple d’individus. Il a donc fallu redéfinir les opérateurs de individus et les opérateurs de mutation, qui n’opèrent que sur un seul individu.
croisements, de mutations, mais aussi un protocole de communication distribué et non
synchronisé entre les agents. Enfin, les expériences menées en simulation et sur la plate-forme Les croisements : L’opérateur de croisement produit deux nouvelles chaînes à partir de deux
robotisée ont montré l’efficacité et la convergence de la méthode. Ces expériences ont chaînes initiales. Le masque de croisement est un mot binaire de même longueur que les
notamment montré qu’il existe un nombre idéal de robots permettant d’optimiser les temps de chaînes génétiques. Ce masque contribue à déterminer lequel des deux parents sera géniteur
convergence. de chaque bit de la génération suivante. Trois grandes familles de croisements sont distingués
dans la littérature (voir Figure 21).

Les croisements simple point. Les deux chaînes initiales vont être divisées en deux. La
première partie de la première chaîne sera associée à la seconde partie de la seconde
chaîne et inversement, deux nouveaux individus sont ainsi obtenus résultant d’un
croisement entre les deux chaînes initiales.

81 46
l’architecture. En 2000, Maja Mataric et Dany Goldberg proposent une architecture multi-
agents basée sur le principe des AMMs (Augmented Markovians Models) [Goldberg 00]. Il
s’agit là d’une structure basée sur les processus markoviens, qui consiste à construire sa
propre bibliothèque d’états au fur et à mesure de l’apprentissage. La technique permet de
combiner deux états identiques et d’éviter de stocker des valeurs pour des états qui ne seront
jamais rencontrés.

Les algorithmes évolutionnistes sont inspirés de l’étude du vivant et plus précisément

de l’évolution darwinienne. Le principe général [Goldberg 89] consiste à disposer d’une
population d’individus possédant chacun une chaîne chromosomique dans laquelle est codé
son comportement. La méthode nécessite de connaître une estimation de la performance de
chaque agent (fitness). Dans la première génération, les chaînes chromosomiques sont
choisies aléatoirement. Les expériences sont divisées en générations, lorsque les performances
de tous les individus de la première génération sont connues des croisements sont réalisés
entre les individus afin de créer la génération suivante. Le principe général de la méthode est
décrit sur l’Algorithme 5 issus de [Mitchell 97].

Cette citation résume à elle seule le principe général de la méthode :

" J’ai donné le nom de sélection naturelle ou de persistance du plus apte à cette
conservation des différences et des variations individuelles favorables à cette élimination des
variations nuisibles "
Charles Darwin, L’origine des espèces

F (h )
i
Équation 13
Pr(hi) Nbindividus

F(h j)
j 1

Algorithme 5 : Principe général des algorithmes évolutionnistes (D'après [Mitchell 97])

45 82
 modifier la pente de ce gradient. Un coefficient de 1 attribue la récompense espérée maximale
à tous les états, alors qu’un coefficient de 0 attribue une récompense espérée de 0 à tous les
états sauf aux états finaux. Sur la Figure 20, le coefficient a été arbitrairement fixé à 0,9.

Il a été démontré que pour des systèmes déterministes le Q-Learning permet

d’atteindre la solution optimale après un temps d’apprentissage infini [Szepesvari 97]. Il a

6
d’ailleurs été démontré que la matrice Q converge vers l’espérance mathématique de la
somme de la récompense instantanée et de la récompense espérée du meilleur état suivant
possible (Équation 12). La même équation pouvant bien sûr s’écrire pour l’état suivant
(Q(St+1,a’)), on en déduit que remonter le gradient emmènera l’agent vers la solution
optimale.

Q(st,a) E[rinstantannée .max

a'
(Q(st 1,a')]
6. Méthodes d’apprentissage pour les Équation 12 : Espérance mathématique de la récompense espérée pour l’action a exécutée depuis l’état St

systèmes multi-robots hétérogènes

___________________________________________________________________________
Figure 20 : Matrice Q pour chacune des actions.

Dans le chapitre précédent, nous avons étudié et proposé des méthodes L’apprentissage par renforcement est un outil performant pour réaliser différents types
d’apprentissage basées sur les algorithmes évolutionnistes pour les systèmes multi-agents d’apprentissage. Il existe de nombreuses autres méthodes dérivées de la programmation
homogènes. Ce type d’apprentissage ne peut s’appliquer que sur un ensemble de robots dynamique et du Q-Learning, comme la différence temporelle (TD), Sarsa et Monte-Carlo.
identiques. Si les agents sont différents dans leur structure ou dans leur perception du monde, Toutes ces méthodes sont basées sur les processus markoviens et demandent de discrétiser
les chaînes chromosomiques n’auront pas le même sens d’un agent à l’autre. De ce fait, un l’environnement en états et les consignes sur les actionneurs en commandes échantillonnées.
comportement performant sur un agent ne sera pas nécessairement robuste sur un agent Pour parfaitement modéliser un problème réel appliqué à la robotique, la taille de la matrice V
différent. C’est pour ces raisons que les méthodes présentées précédemment ne peuvent être ou Q serait proportionnelle au nombre de combinaisons états/actions possibles. Il est évident
appliquées sur un système hétérogène. Or, pour bon nombre d’applications, l’utilisation d’un qu’il est impossible de stocker autant de données sur un système embarqué. De plus
système hétérogène peut être nécessaire. l’apprentissage serait extrêmement long, puisqu’il demanderait à l’agent de visiter au moins
une fois chaque combinaison état/action possible.
Dans le cas d’un système hétérogène, un apprentissage collectif n’est pas envisageable Même si ces méthodes semblent mal indiquées pour l’apprentissage de comportements
puisque chaque agent doit apprendre une stratégie qui lui est propre et dépend de sa structure. réactifs continus, elles peuvent être utilisées pour gérer les couches supérieures de

83 44
 Mais en robotique, ces hypothèses déterministes sont rarement réunies. Il existe une C’est pour ces raisons que nous allons nous intéresser maintenant à l’apprentissage de
autre méthode permettant de réaliser l'apprentissage avec une connaissance partielle du comportements réactifs sur un agent. Nous allons donc isoler un agent des autres et le laisser
modèle: le Q-learning. Cet apprentissage permet également d’être appliqué aux systèmes non évoluer seul dans l’environnement. Dans ce type de système, la coopération se fait dans une
déterministes. couche supérieure que nous ne traiterons pas ici, mais des architectures du type Alliance
[Parker 94] ou Satisfaction/Altruisme [Simonin 00b] sont parfaitement adaptées pour ce type
de coopération.

Proposé en 1989 par Watkins [Watkins 89], le Q-learning est probablement la méthode Précédemment, nous profitions de la taille de la population pour distribuer des solutions à
d'apprentissage par renforcement la plus étudiée actuellement. Les seules hypothèses de tester à chaque individu afin d’accélérer les temps d’apprentissage. Avec ces nouvelles
départ sont les suivantes : hypothèses, l’apprentissage ne peut plus être réparti sur une population d’individus. Pour les
raisons exposées précédemment, nous nous refusons à créer un modèle cognitif de
le système est modèlisable par une chaîne de Markov à états finis, l’environnement ou de l’agent. La seule solution envisageable pour l’apprentissage consiste à
l'agent dispose d'un jeu d'actions discret. tester successivement les comportements sur le même agent et de conserver les meilleurs. La
première méthode présentée dans ce chapitre consiste à apprendre les paramètres d’un
Il n'est pas nécessaire de connaître les transitions entre les états, c'est le grand intérêt du contrôleur neuronal en utilisant le recuit simulé. Des résultats utilisant la technique du recuit
Q-learning. Contrairement à la programmation dynamique, l'objectif n'est pas d'estimer la simulé classique sont présentés. Puis une version étendue de la méthode est décrite,
fonction d'évaluation de chaque état, mais celle de chaque action, en fonction de l'état courant. permettant notamment de s’adapter aux pannes et aux diverses perturbations de
l’environnement.

Nous allons ensuite présenter une seconde méthode utilisant l’apprentissage par
renforcement. Les modèles classiques d’apprentissage par renforcement sont basés sur les
processus markoviens. Les stratégies que nous avons à apprendre se placent dans le domaine
continu. Or les processus markoviens sont discrets, ils découpent le système en états, actions
et transitions. Nous avons alors deux stratégies :

Nous discrétisons les états et les actions continus afin de pouvoir disposer d’un
Q(s,a) Q(s,a) (r max(Q(s',a')) Q(s,a)) système discret, ce qui présente deux inconvénients : d'une part il n'est pas possible
Équation 10
a' d'obtenir des comportements fins puisque les actions sont discrétisées, d'autre part si
l’on veut un pas d’échantillonnage suffisamment précis, alors la taille des données
1 devient trop grande pour être stockée sur un système embarqué.
1 visit(s,a)
La seconde solution consiste à modéliser le système. Dans notre cas, ce n’est pas tout
à fait le processus markovien que nous allons modéliser mais la récompense associée à
chaque configuration du système et ceci par un réseau de neurones. Lorsque ce dernier
est entraîné, nous recherchons dans ce modèle continu l’action qui nous permet
visit(s,a) visit(s,a) 1 Équation 11 d’espérer la meilleure récompense.

Algorithme 4 : Algorithme du Q-Learning C’est cette seconde stratégie que nous allons étudier en présentant les différents points
clef de l’apprentissage : le choix d’un réseau de neurones pour la modélisation, les différentes
techniques de recherche du maximum et les résultats.
La description du Q-learning est montrée sur l’algorithme 4. Le Q-learning est basé
sur l'estimation de la matrice Q(s,a), qui représente la récompense espérée en exécutant
l'action a depuis l'état s. Le point 2 est volontairement resté imprécis. En effet, le Q-Learning
peut être utilisé comme une méthode " off-policy " ou " on-policy ". Dans le premier cas, il
faudra alors choisir une action aléatoirement. Dans le deuxième cas, il faudra choisir une
action en accord avec la stratégie apprise, c'est-à-dire l’action a qui maximise Q(s,a). L’idée générale de cette approche consiste à fixer la structure d’un contrôleur réactif
bas niveau et à optimiser ses paramètres afin de maximiser la récompense. Pour garantir la
Le coefficient représente le coefficient d’amortissement. A la fin de l’apprentissage, portabilité de la méthode, il est préférable de choisir un contrôleur générique. Le choix du
la matrice Q peut être assimilée à un gradient qu’il suffit de remonter pour maximiser la contrôleur sera présenté dans le paragraphe suivant. Reste à optimiser les paramètres de notre
récompense. La Figure 20 montre l’état de la matrice Q à la fin de l’apprentissage. On système pour maximiser la récompense. Ce problème peut se ramener à une recherche de
distingue clairement ce gradient pour chaque action. Le coefficient d’amortissement va maximum d’une fonction. Dans notre cas, nous considérons que cette fonction est inconnue et

43 84
par conséquent sa dérivée aussi. De plus, cette fonction inconnue peut présenter des maxima système, puis à choisir des actions qui permettent d'atteindre l'état ayant la meilleure
locaux. L’ensemble des méthodes dérivées de la dichotomie ou de la descente du gradient estimation. C'est un apprentissage "off policy", qui est détaillé sur l’Algorithme 3.
sont donc à exclure. Nous avons choisi d’utiliser le recuit simulé. Le recuit simulé est une
méthode de recherche du maximum inspirée du refroidissement d’un matériau en fusion.
Dans l’industrie, cette méthode permet d’obtenir l’orientation des cristaux désirée. Pendant le
refroidissement du matériau, l’orientation des cristaux est perturbée. Le principe consiste à
remonter la température de fusion si l’orientation est insatisfaisante. La méthode
mathématique du même nom permet notamment de trouver le maximum d’une fonction
présentant des maxima locaux. Cette méthode de recherche semble la mieux indiquée à notre
problème, puisque la connaissance de la fonction n’est pas nécessaire et que la convergence
vers le maximum global est assurée sous certaines conditions, relatives notamment à la vitesse
de la descente de la température.

Dans cette première partie liée au recuit simulé, nous allons nous focaliser sur une
tâche d’évitement d’obstacles. Les hypothèses sont les mêmes que celles présentées au
chapitre précédent et nous avons choisi comme récompense de maximiser la vitesse moyenne
signée du robot. La récompense instantanée est donc la moyenne des vitesses de rotation des
roues du robot.

Le contrôleur est une fonction mathématique, statistique ou logique qui lie les entrées
du système (les capteurs du robot) aux sorties (les actionneurs). Nous avons choisi d’utiliser Figure 19 : V* après cinq cycles d'apprentissage
un contrôleur neuronal car les réseaux de neurones peuvent modéliser la plupart des fonctions
de Rn dans Rm. Nous avons utilisé un réseau sans couche cachée, inspiré du véhicule de
Braitenberg [Brainteberg 84]. Ce réseau est constitué de deux perceptrons dont les entrées A la fin de la phase d'apprentissage, V* V. Si l'on considère par exemple le
sont les informations directement issues des capteurs et les sorties les consignes appliquées problème de la Figure 18, le résultat de l'apprentissage est représenté sur la Figure 19. On
aux moteurs. Le schéma du réseau est montré sur la Figure 45. Le réseau possède 8 entrées et distingue la valeur associée à chaque état du système. Par exemple de l'état S5, on peut
deux perceptrons, il y a aura donc 16 poids synaptiques, ce sont ces 16 paramètres que le atteindre quatre autres états : S1, S4, S9 et S6 (Figure 18). Les récompense espérée de chacun
recuit simulé permettra d’optimiser. Les travaux antérieurs (dont ceux de Braintenberg) ont de ses états sont respectivement 0.01, 0.01, 0.10 et 0.10. La phase d'application de la stratégie
montré qu’un réseau sans couche cachée permettait de résoudre ce problème d’évitement consiste à choisir l'action qui permet d'atteindre l'état ayant la meilleure fonction d'évaluation.
d’obstacles. Afin de ne pas allonger les temps d’apprentissage, nous avons choisi de Les deux états S9 et S6 correspondent donc aux deux meilleurs successeurs de l'état S5. Un
conserver cette structure, mais l’utilisation d’un réseau multi-couches est envisageable pour exemple de stratégie optimale est représenté en pointillés sur la figure. La programmation
des problèmes plus complexes. dynamique permet de trouver la stratégie optimale lorsque le modèle complet est connu et
déterministe. Ce type d’apprentissage est particulièrement bien indiqué pour l’apprentissage
de stratégies, par exemple dans des jeux de réflexion. J’ai programmé un joueur pour le jeu de
Nim1 en 2000. Il s’agit d’un problème déterministe puisqu’il n’y a aucun tirage au sort dans le
jeu. Le programme est constitué de deux phases : une phase d’apprentissage ou le joueur joue
contre lui-même, puis une phase de jeu ou l’on peut affronter l’algorithme. La méthode
utilisée est la programmation dynamique. A chaque configuration de jeu est associée la
probabilité de gagner et le joueur tente constamment d’amener le jeu dans la meilleure
configuration connue. La solution mathématique de ce jeu est connue et si deux joueurs
parfaits s’affrontent, le joueur qui ne joue pas le premier coup est sûr de remporter la partie.
Après quelques secondes d’apprentissage en jouant contre lui-même, le joueur joue les
meilleurs coups au sens de la solution mathématique connue.

Figure 45 : Le contrôleur neuronal 1

Le jeu de Nim consiste à disposer 4 lignes de 1, 3, 5 et 7 allumettes. Les joueurs enlèvent chacun leur tour
autant d’allumettes qu’ils le souhaitent sur la ligne de leur choix. Le joueur qui prend la dernière allumette perd
la partie. Ce type de jeu a été rendu célèbre par le film d'Alain Resnais : « L'Année dernière à Marienbad » en
1961.

85 42
 Pour homogénéiser l’ensemble du système, toutes les valeurs ont été ramenées à
l’échelle unitaire. Les informations des capteurs et les commandes appliquées aux moteurs
Environnement Processus Markovien
sont comprises entre 0 et 1, les valeurs des poids synaptiques sont bornées dans l’intervalle [-
1, 1]. La disposition des capteurs et actionneurs utilisés est représentée sur la Figure 46.
S

E
Actions

O E

Figure 46 : Disposition des capteurs et actionneurs

Récompense
S
Figure 18 : Exemple de processus markovien

Dans ce cas, le système est déterministe, lorsque l'agent se trouve dans un état donné
(Sn) et qu'il réalise une action donnée, l'état (Sn+1) suivant sera toujours le même. Dans un
système non déterministe, la même action réalisée depuis le même état (Sn) peut aboutir à des
états (Sn+1) différents. Dans ce cas, les transitions du processus markovien représentent la
probabilité pour chaque état d'être atteint en fonction de l'action réalisée. Le schéma général
de l'apprentissage par renforcement consiste à associer à chaque action une fonction de cette
probabilité et de la récompense associée à l’action. La récompense moyenne espérée pour
chaque action peut ainsi être déterminée. De cette façon, il ne reste plus qu’à exécuter l’action
possédant la meilleure récompense espérée dans la phase d’application de la stratégie.

V (s)  Actions
( rt 1
.V ( s t 1 )) Figure 47 : Recherche du maximum d’une fonction

Nous allons dans un premier temps appliquer la méthode du recuit simulé traditionnel
à notre problème. Le principe général est de tirer les valeurs des poids au hasard avec une
répartition proportionnelle à la température. Le tirage aléatoire est centré sur la meilleure
Algorithme 3 : Algorithme de la programmation dynamique valeur connue. Un exemple de recherche du maximum est montré sur la Figure 47. L’axe
vertical représente le nombre d’itérations pour l’intervalle [0, 100] et la valeur de la fonction à
La programmation dynamique s'applique pour les systèmes déterministes dont le maximiser pour l’intervalle [-100, 0]. L'objectif est de trouver le maximum de la fonction
modèle complet est connu, c'est-à-dire que tous les états et toutes les transitions sont connues. représentée par une surface. La fonction de décroissance de la température est linéaire. Les
La méthode consiste à estimer la fonction d'évaluation V* associée à chacun des états du premiers tirages sont répartis sur l’ensemble de l’espace de définition de la fonction. Le tracé
continu représente l’évolution du meilleur point connu. Cette figure montre que l’algorithme

41 86
se fait happer par les maxima locaux avant de converger vers le maximum global. Le système l’environnement, il a la possibilité d’agir sur ce dernier (at) et il reçoit une récompense (rt).
n’est jamais complètement gelé pour permettre la convergence vers la valeur exacte du L’objectif de l’apprentissage par renforcement est d’associer à chaque état du système une
maximum. L’algorithme est détaillé sur l’Algorithme 6. action qui permet de maximiser la récompense.

Figure 17 : Système d'apprentissage par renforcement.

Algorithme 6 : Algorithme utilisé pour entraîner le réseau On distingue deux types d'algorithmes; les stratégies "off policy" et les stratégies "on
policy". Dans le premier cas, l'apprentissage est divisé en deux phases :
une phase d’apprentissage, qui consiste à essayer des stratégies aléatoires afin de
modéliser le système,
une phase d'application où l’agent n’exécute que les meilleures actions apprises dans
la phase précédente.

Dans le cas des stratégies "on policy", l'agent applique la stratégie apprise au fur et à
mesure de sa progression et de son apprentissage.
Figure 48 : Evolution de la température en fonction du temps

La fonction de température utilisée est présentée sur la Figure 48. Nous avons
arbitrairement choisi une fonction linéaire mais d’autres fonctions auraient pu être testées, L'apprentissage par renforcement est basé sur l'apprentissage à temps discret des
toutefois les résultats n’auraient pas été pertinents dans le sens où ils auraient été spécifiques à paramètres d'une chaîne de Markov. Les chaînes de Markov sont composées d'états et de
cette application. Le point essentiel est de ne pas descendre la température trop vite pour transitions entre ces états. Prenons par exemple le cas d'un agent qui peut se déplacer dans un
permettre au système de s’extirper des minima locaux. Pour permettre à l'algorithme de environnement discrétisé (Figure 18). L'environnement est décomposé en 16 cases
glisser vers le maximum global, la température n'est jamais égale à 0. La valeur minimale Tmin représentant chacune un état du processus markovien. La position de départ est représentée
garantie de ne jamais figer les paramètres du système et de converger vers l'extremum, qu'il par la case S et l'objectif est d'atteindre la case E. L'agent dispose de 4 actions possibles : se
soit optimal ou global. déplacer vers le nord, l'est, le sud ou l'ouest.

Un inconvénient majeur à l’utilisation du recuit simulé réside dans le réglage des

paramètre: nous allons décrire comment nous avons choisi ceux utilisés dans ces travaux. La
fonction de la température est décroissante linéairement jusqu'à atteindre une valeur faible (
Tmin = 5.10-3). Cette valeur est suffisante pour verrouiller le système et permettre à
l’algorithme de glisser vers la valeur optimale absolue. La température initiale (Ti) est égale à
1. Durant les simulations sous Matlab, nous avons volontairement choisi une valeur négative
très faible pour a = -5.10-3. Diminuer lentement la température de cette façon garantit que
l’ensemble de l’espace d’état est exploré et que la solution optimale est trouvée. Pour les
expérimentations sur les robots réels, nous nous sommes basés sur l’autonomie qui est
d’approximativement 90 minutes. Ce temps a été découpé en deux parties : environ une heure

87 40
 pour l’apprentissage, puis 30 minutes pour la température minimale Tmin. Une évaluation de la
stratégie dure 23 secondes, pour atteindre Tmin en une heure, le paramètre a doit valoir -6.10-3.

Résultats de simulation : De nombreuses simulations ont été réalisées afin d'étudier

l'influence des paramètres. La première constatation est que la méthode converge toujours
vers la stratégie optimale à condition que la température décroisse lentement et que les temps
d'évaluation soient suffisamment longs pour garantir une estimation correcte de la
performance. La Figure 49 présente l'évolution typique de la meilleure stratégie connue au
cours du temps. Dans un premier temps, le robot tourne sur place, garantissant ainsi de ne pas
rencontrer d'obstacles. La trajectoire du robot décrit des cercles de plus en plus grands, pour
finir par parcourir des trajectoires rectilignes tout en évitant les obstacles. Le robot dispose
d'un capteur central C0; lorsqu'un obstacle est détecté par celui-ci, l'agent dispose de deux
stratégies: tourner à droite ou à gauche. Il existe donc deux stratégies optimales dans notre
système.

Figure 16 : Exemple de fonction radiale dans ²

Généralement, les centres sont fixés et seuls les wi sont modifiés. La règle de
rétropropagation du gradient est utilisée sur la seule couche de sortie. Comme le réseau ne
possède pas de couche cachée devant être mise à jour, la méthode présentée sur l’Algorithme
1 est parfaitement adaptée pour l’apprentissage. C’est pour ces mêmes raisons que la méthode
est simple et rapide à implémenter. Toutefois, le choix de la position des centres et le nombre
de neurones reste généralement arbitraire. Ils sont généralement répartis uniformément sur
l’intervalle de définition de la fonction f=s(e). Il existe des méthodes de positionnement
automatique des centres: ces méthodes consistent à déplacer les centres vers les points où
l’erreur de modélisation est grande. L’accumulation de fonctions autour des zones complexes
à modéliser améliorent l’approximation, car les fonctions radiales ont une influence limitée
autour de leurs centres.

Figure 49 : Evolution de la meilleure stratégie connue

Il existe un grand nombre de méthodes permettant de réaliser l'apprentissage neuronal.
De manière générale, ces méthodes sont supervisées, elles nécessitent des exemples pour Résultats expérimentaux : les résultats de simulations étant satisfaisants, des expérimentions
réaliser l'apprentissage et elles sont difficilement applicables dans les cas d'auto-apprentissage sur un robot mobile Type 1 ont donc été menées. Les résultats d’une expérience sont
et d’adaptation où aucun exemple de comportement n'est connu. présentés sur la Figure 50. En premier lieu, la convergence est atteinte et la récompense est
maximisée (Figure 50.b). Toutefois, l'analyse des résultats montre que le système ne converge
pas toujours vers la solution optimale. Le même comportement peut donner des performances
différentes avec un écart-type important. Si une évaluation donne une récompense importante
dès le début de l’apprentissage et que cette évaluation est erronée, alors aucune autre
expérience ne pourra écraser cette mauvaise évaluation. Prenons cet exemple critique :
l’agent réalise la stratégie suivante " aller tout droit quelque soient les obstacles détectés ". Si
L'apprentissage par renforcement a pour objectif de maximiser la performance du sa configuration initiale lui permet d’aller droit sans rencontrer d’obstacles, la récompense
système en renforçant les meilleures actions. L'agent obtient des informations de l'état de attribuée sera élevée. Et pourtant ce comportement est loin d’être optimal. Cette erreur est due
l’environnement (nous les appellerons les perceptions) et agit également sur l'environnement à la configuration de l’environnement, la position initiale du robot et le bruit. Pour contrer ce
puis reçoit une estimation de sa performance : la récompense. Dans les algorithmes problème, il faudrait augmenter la durée d'une période d'évaluation afin de diminuer l'écart-
d'apprentissage par renforcement, cette récompense peut être immédiate ou retardée. Le type autour de la valeur moyenne de la performance, mais les temps d'apprentissage seraient
schéma général est représenté sur la Figure 17. L’agent connaît son état (St) dans augmentés. De plus, la méthode n’est pas adaptative: une fois que la température a atteint son

39 88
minimum, plus aucune variation des poids n’est envisageable, donc le système est incapable de neurones RBF (dont la fonction de transfert est donnée par l’Équation 9) et une couche de
de s’adapter à une quelconque panne ou perturbation. L’approche adaptative proposée dans le sortie constituée de perceptrons.
paragraphe suivant va nous permettre de contrer ces deux problèmes en même temps.

RBF
c1 w1

c2 RBF w2
s
e c3
RBF
w3
c4 w4
RBF

Figure 14 : Exemple de réseau RBF

L’exemple de la Figure 14 montre un réseau permettant l’approximation d’une

fonction de  dans  (s=f(e)). Chaque fonction radiale possède un centre ci, la sortie globale
c'est la somme des sorties des neurones de la couche cachée. La Figure 15 montre la courbe à
Figure 50 : Résultats d'une expérimentation estimer en continu, ainsi que la sortie de chaque neurone de la couche cachée en pointillé.
Chaque neurone a une influence locale sur la courbe estimée.

Nous avons vu dans le chapitre précédent que le recuit simulé classique ne permet pas
d’adapter le contrôleur aux perturbations extérieures. Le seul moyen de détecter de tels
événements (sans considérer de représentations complexes ni de l’environnement ni de
l’agent) est d’exploiter l’information retournée par la récompense. Si un changement notable
survient, la récompense va diminuer, sinon c’est que ce changement n’altère pas les
performances du système, auquel cas il n’est pas nécessaire de modifier le contrôleur. L’idée
maîtresse de cette méthode adaptative est d’autoriser la remontée de la température quand la
récompense est faible. Cette méthode qui autorise la remontée de la température est plus
fidèle à l’inspiration initiale du recuit simulé, puisque dans le refroidissement d’un matériau
en fusion, les remontées de températures sont fréquentes. e
c1 c2 c3 c4
Mathématiquement, la température est une fonction de la récompense du meilleur Figure 15 : Fonction à estimer et sortie de chaque neurone de la couche cachée.
comportement connu. L’inconvénient majeur réside dans le fait que le système sera
probablement attrapé dans les maxima locaux. Cette nouvelle hypothèse annule les propriétés
de convergence globale du recuit simulé. Notre philosophie est la suivante : si la récompense Bien sûr, ce modèle peut être étendu à des fonctions de n dans m. La Figure 16
est correctement attribuée, que la solution trouvée soit un maxima local ou global n’a pas montre un exemple de fonction radiale dans 2. La fonction de base la plus couramment
d’importance, tant que la récompense est maximisée. La récompense du meilleur utilisée est donnée par l’Équation 9.
comportement Rmax connu est diminuée à chaque cycle de la boucle principale. Si la stratégie
est constamment performante, Rmax est constamment mis à jour et le contrôleur reste stable.
En revanche, si cette valeur diminue (ce qui signifie que la récompense attribuée n’est pas
(x ci)²
constante), la température sera augmentée. La méthode est détaillé sur l'Algorithme 7. f(x) e
Équation 9 : Fonction de transfert d’un neurone de type RBF

89 38
Réseaux avec couche cachée. La méthode la plus connue est basée sur la rétropropagation du
gradient. Cette méthode, dite supervisée, consiste à présenter des exemples au réseau
multicouches, puis à en propager l’erreur entre la sortie désirée et la sortie obtenue à travers le
réseau afin de corriger tous les poids, même ceux des couches cachées. Un exemple est
composé d'un vecteur d'entrées et de sorties désirées <x,d>. L'algorithme de rétropropagation
du gradient est décrit sur l’Algorithme 2.

k (d k ok ) ' ( xi ) Équation 5 Algorithme 7 : Algorithme adaptatif utilisé pour entraîner le réseau

Les paramètres du réseau sont identiques à ceux présentés précédemment. La nouvelle

N
fonction de la température est toujours linéaire. L’objectif est d’obtenir des températures
k w .
k 1
ki '(xi) Équation 6 faibles pour les grandes valeurs de la récompense et inversement. Comme la meilleure
récompense espérée est proche de 1, nous avons simplement choisi la fonction représentée sur
la Figure 51. Tmin=5.10-3 comme précédemment et a=-1 de façon à atteindre linéairement Tmin
quand Rmax est proche de 1. Un décrément de Rmax est égal à 7.10-2 , cette valeur garantie le
wij wij wij Équation 7 verrouillage du comportement quand la récompense est élevée. Ce paramètre représente la
faculté d’adaptation du système. Une grande valeur autorise le système à rapidement basculer
vers une autre stratégie, en revanche une stratégie prometteuse peut ne pas être complètement
explorée.
wij . j .xij Équation 8

Algorithme 2 : Algorithme de rétropropagation du gradient

La méthode présentée sur l’Algorithme 1 est en fait une version simplifiée de la
rétropropagation du gradient puisque cela est équivalent à appliquer l’Algorithme 2 sur un
système sans couche cachée. L’efficacité et la rapidité de convergence de cette méthode ne
Figure 51 : Evolution de la température en fonction de la récompense du meilleur comportement connu
sont plus à prouver, seulement deux problèmes persistent : lors de la mise à jour des poids de
la couche cachée, l’ensemble du réseau est modifié, c'est-à-dire que le comportement du
réseau sera modifié pour tous les exemples entrés, même s’il n’a été mis à jour que pour un
seul exemple. Dans l’espace des entrées, la modification n’est pas locale. Ensuite, il n’est pas Résultats de simulation : Les résultats de simulations et expérimentaux sont proches, nous
toujours aisé d’estimer le nombre de neurones dans la couche cachée. Ce deuxième problème ne présenterons que les seconds, réalisés sur un véritable robot.
est principalement dû à la difficulté de donner une signification physique à cette couche
cachée. Nous avons choisi de présenter ci-après une autre famille de réseaux de neurones qui Résultats expérimentaux : En premier lieu, la convergence est rapidement atteinte. Le
permet justement de s’affranchir des deux problèmes précédents. système est vite happé dans un maxima local. La Figure 52.a montre l’évolution des poids du
réseau. Après quelques minutes (environ 15 cycles) une stratégie acceptable est découverte.
La température décroît soudainement et verrouille le contrôleur autour de cette stratégie.
Comme la température n’est pas égale à 0, les valeurs des poids glissent lentement vers la
Les réseaux à fonctions radiales (RBF : Radial Basis Functions) permettent
meilleure solution locale. La Figure 53 représente l’influence de chaque capteur sur le
l’apprentissage de fonctions complexes; ils sont basés sur une structure différente des
comportement global (les flèches fines indiquent les obstacles). Les deux valeurs indiquent la
perceptrons. Ces réseaux sont généralement composés de deux couches : une couche cachée
commande appliquée aux moteurs. Il n’y a pas de couche cachée dans notre réseau, donc le

37 90
comportement global est une combinaison linéaire de chaque diagramme. Par exemple, la
Figure 53.a montre la direction courante du robot quand aucun obstacle n’est détecté : le robot
avance en ligne droite. Cette figure montre que la stratégie atteinte n’est pas la solution
optimale : sur la Figure 53.f si un obstacle est détecté par le capteur C6 (Voir la Figure 46
pour la disposition des capteurs), le robot continue de rouler en ligne droite au lieu de tourner
à droite comme le voudrait la solution optimale. Malgré cela, le robot est capable d’éviter les
obstacles et de maximiser sa récompense2.

wij (di oi)xi Équation 2

wij wij wij Équation 3

Algorithme 1 : Apprentissage neuronal d’un réseau sans couche cachée

Les réseaux de neurones sans couche cachée ne peuvent modéliser que des fonctions
linéaires. Pour illustrer ces propos, prenons l’exemple classique d’un réseau devant modéliser
une fonction logique : il possède deux entrées x1 et x2, un perceptron unique et une sortie s. La
fonction de transfert du réseau est donnée par l’Équation 4. Il s’agit là d’une fonction linéaire
et nous allons optimiser les paramètres de la droite w11 et w21.

s (x1.w11 x2.w21)
Figure 52 : Résultats d’une expérience Équation 4 : Fonction de transfert d’un réseau modélisant une fonction logique

Au 25ème cycle, le contrôleur est verrouillé sur la stratégie locale. 37 cycles après le x2
début de l’expérience, nous avons simulé une panne de capteur en obstruant le récepteur C1
afin de tester la robustesse de notre système. La Figure 52.b montre l’évolution de la P01 1 P11
récompense et de la température (ligne pointillée). On discerne sur ce graphique la chute de la
récompense. Comme une nouvelle solution est très proche dans l’espace des solutions,
l’algorithme renforce l’influence des capteurs les plus proches (C0 et C2) pour compenser -1 1 x1
l’absence de C1 et le système redevient stable à nouveau. D’autres pannes plus importantes -1
ont été testées et le système retourne dans une phase d’exploration comme dans les premiers P00 P10
cycles de l’expérience. Si la panne est trop importante, l’agent ne reçoit pas de récompense
suffisante. De fait, la température ne décroît pas, le système ne converge pas vers une Figure 13 : Représentation du réseau dans l’espace des entrées
solution, même locale.

Par exemple, pour modéliser une fonction logique ET, il existe une infinité de droite
permettant d’isoler le point P11 des points P00, P01 et P10 (Figure 13). En revanche, si l’objectif
est de modéliser une fonction " OU EXCLUSIF ", il n’existe aucune droite permettant d’isoler
les points P11 et P00 des points P01 et P10. Les réseaux sans couche cachée ne permettent pas de
modéliser toutes les fonctions. L’ajout d’une couche intermédiaire permet donc de découper
l’espace en zones. Si une fonction de sortie linéaire est conservée, alors les zones sont
séparées par des droites, mais il y a plusieurs droites, ce qui permet de dissocier des zones non
linéairement séparables. Les réseaux de neurones sont d’ailleurs fréquemment utilisés pour
résoudre des problèmes de classification.
2
L’influence importante du capteur C7 (Figure 53.e) compense le manque de réactivité du capteur C6.

91 36
Nous avons présenté ici deux fonctions fréquemment rencontrées, mais d’autres fonctions
orientées vers d’autres applications plus spécifiques existent aussi. Nous verrons notamment
la particularité des réseaux RBF (Radial Basis Functions) au chapitre 3.2.4.

(x)

x
-1

Figure 11 : Fonction de sortie de type seuil

(x)
Figure 53 : Influence de chaque capteur sur le comportement global
1

x Nous venons de présenter des résultats d’expériences basées sur le recuit simulé avec
-1
pour objectif d’apprendre des comportements réactifs. Nous avons présenté en premier lieu
une méthode permettant d’optimiser les paramètres d’un contrôleur neuronal. Dans un
Figure 12 : Fonction de sortie bornée environnement sain, la méthode permet à l’agent d’atteindre la solution optimale, mais les
temps d’apprentissage sont longs. De plus, la convergence n’est pas assurée quand le système
est perturbé par des éléments extérieurs. Le recuit simulé ne peut pas être appliqué
directement pour nos applications, ce qui a motivé l’implémentation d’une seconde méthode
permettant d’adapter le contrôleur aux perturbations et aux pannes. Cette méthode ne garantit
La structure d'un réseau de neurones est constituée de neurones reliés entre eux par des pas de pouvoir atteindre la solution globalement optimale et n’est pas capable de s’adapter
liaisons synaptiques. A chacune de ces liaisons est associé un poids synaptique et ce sont aux pannes importantes. Mais elle permet de trouver une solution acceptable rapidement et
précisément les modifications apportées à ces poids qui vont nous intéresser. De manière reste robuste face à certaines pannes en adaptant automatiquement les paramètres. Il ne faut
générale, l'apprentissage neuronal consiste à ajuster les valeurs des poids synaptiques du pas nier que le point critique de ces deux méthodes réside dans le réglage des paramètres. Ces
réseau pour que la réponse du réseau soit celle désirée. Dans un premier temps, nous allons paramètres peuvent, selon nous, difficilement être génériques à diverses tâches: ils doivent
présenter l’apprentissage des poids pour un réseau sans couche cachée. donc être adaptés en fonction de la nature de la mission à accomplir, de sa complexité, mais
aussi de la récompense attribuée. Cette méthode, présentée dans le cadre d’un apprentissage
Réseaux sans couche cachée. Dans ce type de réseau, il y a autant de neurones que de pour des systèmes multi-agents hétérogènes pourrait être appliquée à des systèmes
sorties. Les entrées sont directement reliées aux neurones par l’intermédiaire des liaisons homogènes. Il serait par exemple possible de combiner la méthode évolutionniste présentée
synaptiques. Le principe général consiste à calculer l’erreur de chaque sortie, en au chapitre précédent avec le recuit simulé. Toutes les méthodes présentées précédemment ont
différenciant la sortie désirée et la sortie obtenue (Équation 2), puis à ajuster les poids afin été comparées en simulation sur une recherche de maximum (Figure 54). Les algorithmes
de diminuer cette erreur (Équation 3). Le coefficient représente le coefficient génétiques (AG) présentent le temps de convergence le plus long et le plus grand écart-type.
d’apprentissage, plus sa valeur sera faible, plus l’apprentissage sera long et stable. L’emploi d’une méthode numérique pour les mutations et les croisements permet
d’augmenter significativement les performances. Le recuit simulé traditionnel permet une
convergence encore plus rapide. Ici l’écart-type est nul, puisque le temps de convergence est
fixé par la fonction de décroissance de la température. Enfin la combinaison du recuit simulé
et des algorithmes génétiques présente les meilleures performances, toutes méthodes
confondues.

35 92
 Temps de convergence

Nous rappelons brièvement le modèle général du neurone artificiel, qui est l'élément de
base de beaucoup de réseaux. Il est composé des éléments suivants :
une ou plusieurs entrées pondérées,
un sommateur,
une fonction de transfert,
une sortie.

La Figure 10 montre le schéma général du neurone artificiel

x1
w1j

Méthodes w2j
Figure 54 : Comparaison des différentes méthodes
x2 () s

wNj
xN

avec

Les méthodes d’apprentissage présentées précédemment ne sont pas basées sur la xi le stimulus d'entrée,
construction d’un modèle. Ces méthodes consistent à tester successivement (ou de façon wij la valeur du poids synaptique reliant le stimulus i au neurone j,
distribuée) des solutions choisies aléatoirement, pour ne conserver que la ou les meilleures. () la fonction de sortie du neurone,
Lorsque l’agent ne dispose d’aucune information ni modèle, comme c’est le cas pour l’auto- s la sortie du neurone.
apprentissage, l’apprentissage doit nécessairement commencer par une phase de recherche
aléatoire. La différence entre l’apprentissage par renforcement et les techniques présentées Figure 10 : Schéma général d'un neurone artificiel
jusqu’ici réside dans la construction d’un modèle. La phase initiale aléatoire va servir à
construire un modèle markovien de la tâche à apprendre. Une fois cette phase terminée, la
phase d’application de la politique consiste à exploiter ce modèle (qui peut continuer sa mise La fonction d'un neurone artificiel est donnée par l'équation suivante :
à jour). A complexité équivalente, ce type d’apprentissage est plus rapide que les méthodes
basées sur une recherche purement aléatoire. Comme nous l’avons expliqué au chapitre 3, ce
type de modèle nécessite de stocker un grand nombre de données. La taille de cette base de n
données augmente exponentiellement par rapport à la dimension du problème. De plus, les
processus markoviens sont discrets et nous préférons appliquer l’apprentissage sur des
s (x [Link])
j 1
structures continues.
Équation 1 : Equation de la fonction de transfert d’un neurone
Il existe pourtant une solution permettant de diminuer la taille des données : utiliser un
réseau de neurones3 pour approximer la matrice Q. Cette méthode a notamment été employée
Un réseau de neurones n’est finalement qu’une représentation conviviale de fonctions
pour programmer le joueur de Backgammon de Tésauro [Tésauro 94]. Le réseau utilisé était
mathématiques. En effet, chaque réseau peut s’écrire sous la forme d’une équation. La
un réseau multi couches classique, possédant 198 neurones d’entrées et entre 40 et 80 fonction de transfert de base des réseaux est donnée par l’Équation 1. La fonction de sortie
neurones dans la couche cachée selon les versions. Un autre exemple spectaculaire de cette
des neurones est principalement utilisée pour mettre en forme les signaux de sortie des
méthode est l’apprentissage de comportements réactifs pour des robots footballeurs. Il existe
neurones. Si par exemple le système est binaire, une fonction de type seuil pourra être utilisée
(Figure 11). Si le système est borné (par exemple un réseau dont la sortie est appliquée
3
Initialement, la méthode consistait à réaliser une approximation par la méthode des moindres carrés. directement sur un actionneur) alors la fonction de sortie peut aussi être bornée (Figure 12).

93 34
 dans la coupe du monde de robotique (Robocup) une catégorie simulée (Simulation League).
En dernier lieu, nous présenterons les algorithmes évolutionnistes. Inspirés de Dans cette catégorie, l’ensemble du terrain et des robots est simulé et les équipes s’affrontent
l’évolution darwinienne, le principe général consiste à attribuer à chaque individu une via le réseau (Figure 55). La méthode a été employée pour réaliser l’apprentissage de
séquence génétique correspondant à un comportement. Régulièrement, les individus sont comportements type défense / attaque. A notre connaissance, cette méthode appelée Neuro-Q
rassemblés pour pouvoir effectuer des croisements et des mutations sur leurs chaînes n’a jamais été appliquée sur un système réel. Et pour cause, dans les deux exemples
chromosomiques. L’apprentissage est donc découpé en générations successives et les précédents l’apprentissage est extrêmement long : plusieurs heures, voire plusieurs jours sur
performances de l’ensemble de la population sont ainsi accrues au fil de l’évolution. des systèmes simulés. Il est évidemment que les temps d’apprentissage seraient
disproportionnés sur un système réel.
Bien sûr, toutes ces techniques d’apprentissage nécessitent un critère à optimiser,
comment estimer la performance d’un individu au fil de l’évolution ? Ou encore comment
récompenser un agent dans le cadre de l’auto-apprentissage ? Avant de conclure ce chapitre,
nous présenterons et définirons les différents moyens d’estimer une performance.

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).
Figure 55 : Capture d’écran du simulateur utilisé pour la Robocup
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 ". Nous allons présenter dans la suite de ce chapitre une méthode inspirée du Neuro-Q.
Cette méthode consiste à utiliser un réseau de neurones pour modéliser la Q-fonction. Au lieu
En 1958, le psychologue Frank Rosenblatt, combinant les idées de ses prédécesseurs, d’utiliser une méthode de type global comme la rétropropagation du gradient, nous allons
propose le premier perceptron [Rosenblatt 58]. Ce réseau, capable d’apprendre à différencier utiliser une méthode d’approximation locale. Des travaux antérieurs ont déjà été réalisés dans
des formes simples et à calculer certaines fonctions logiques, est inspiré du système visuel. ce sens. Hormis les travaux cités précédemment, nous noterons principalement deux
méthodes : une approximation de la Q-fonction utilisant le CMAC [Miller 90] et une autre
Au début des années 60, les travaux de Rosenblatt suscitent un vif enthousiasme dans méthode basée sur les fonctions radiales [Anderson 93]. En 1997, C.W. Anderson et R.
le milieu scientifique. Mais en 1969, deux scientifiques américains de renom, Minsky et Kretchmar ont comparé les deux méthodes [Kretchmar 97]. Ils arrivent à la conclusion que la
Papert, publient un livre [Minsky 69] qui démontre les limites du perceptron proposé par méthode utilisant les fonctions radiales proposent une meilleure approximation de la Q-
Rosenblatt. En particulier, son incapacité à résoudre les problèmes non linéairement fonction. Nous allons dans la suite de ce chapitre utiliser ces résultats pour proposer une
séparables, dont la fonction logique XOR est un célèbre exemple. méthode d’apprentissage par renforcement pouvant s’appliquer au domaine d’états et
d’espaces continus.
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 La méthode d’approximation consiste donc à utiliser un réseau RBF (Radial Basis
couches cachées sera popularisé en 1986 dans un livre " Parallel Distributed Processing " par Functions) qui permet une modélisation locale. Nous allons nous placer dans un premier
Rumelhart et al [Rumelhart 86]. temps dans le cas d’un système déterministe. L’équation de la Q-fonction selon Watkins est
donné par l’Équation 31.
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 Q(s,a) r .max(Q(s',a'))
couches peut approximer n’importe quelle fonction de Rn dans Rm avec une précision avec : coefficient d’amortissement
arbitraire.
Équation 31 : Mise à jour de la Q-fonction dans le cas d’un système déterministe
Nous allons utiliser l’Équation 31 pour actualiser notre réseau de neurones (Figure 56).

33 94
 Une fois de plus, la source d’inspiration nous vient principalement du vivant. Chacun
de nous est un magnifique exemple de ce que la nature sait faire de mieux en matière
d’apprentissage et d’adaptation. Nous sommes capables de résoudre une grande diversité de
problèmes, de nous déplacer, de voir, d’analyser des situations inconnues etc. Pourtant, nous
RBF ne sommes pas obligés de calculer des changements de repères complexes pour nous
w1
déplacer. La nature a développé des stratégies alternatives afin de pouvoir analyser
rapidement une situation et en déduire les meilleures réactions. Bref, l’étude de l’homme et du
s RBF w2 milieu animal reste probablement une des sources d’inspiration les plus riches au monde. Que
o
ce soit pour l’homme ou pour l’animal, il n’y a que trois origines possibles à ces
a comportements :
RBF
w3

w4 Ils sont soit le résultat d’une imitation. Certains singes disposent de cette faculté à
RBF
transmettre par l’exemple certaines aptitudes à leur progéniture. Ils leurs montrent notamment
comment utiliser à bon escient un bâton ou une pierre pour ouvrir une noix de coco. Le jeune
singe, écarté de ses parents après la naissance, n’est pas capable d’acquérir par lui-même cette
Figure 56 : Architecture du réseau RBF utilisé
faculté. On parle dans ce cas de mimétisme.

Ils peuvent être le fruit d’un apprentissage individuel. Prenons l’exemple d’un
jongleur : si vous n’avez jamais appris à jongler et que vous essayez pour la première fois,
wi wi (r .max
a'
(O(s',a')) O(s,a))Oci(s,a) c’est l’échec assuré. Donc, la capacité de jongler n’est pas inhérente à notre patrimoine
Avec : génétique. Ce n’est pas non plus en regardant quelqu’un jongler pendant plusieurs heures que
Wi : poids mis à jour vous pourrez acquérir cette faculté. Le seul moyen d’apprendre à jongler est de s’entraîner.
O(s,a) : sortie du réseau soumis au couple d’entrée s,a C’est donc bien le fruit d’un auto-apprentissage.
Oci(s,a) : sortie du neurone de poids synaptique i soumis à l’entrée s,a
Enfin, ils peuvent être le fruit de l’évolution : un jeune poulain peut se lever et tenir
Équation 32 : Fonction de mise à jour des poids du réseau debout quelques heures seulement après sa naissance. Il est évident qu’il n’a pas appris en
quelques heures à se tenir debout, il transportait donc dans son patrimoine génétique cette
L’Équation 32 donne la fonction utilisée pour faire converger le réseau vers la Q- aptitude à se maintenir sur ses pattes.
fonction. Cette fonction de mise à jour peut aussi être utilisée dans le cas des systèmes non
déterministes. En effet, dans le cas d’un système non déterministe, l’équation de mise à jour Les principales techniques d’apprentissage en robotique peuvent être regroupées selon
de la Q-fonction consiste à calculer la moyenne des récompenses acquises au fur et à mesure les trois exemples ci-dessus : les méthodes évolutionnistes, l’apprentissage par l’exemple
des expériences. Dans le cas présent, l’apprentissage par réseau de neurones moyenne ces enfin l’apprentissage par renforcement. Mis à part ce dernier, basé sur un outil statistique, les
récompenses espérées automatiquement. De plus, contrairement au Q-learning, la méthode 2 autres sont directement inspirées de l’étude du vivant. Dans ce chapitre, nous allons
permet de réaliser une moyenne pondérée des récompenses : les coefficients des dernières présenter en détails les techniques d’apprentissage les plus utilisées.
expériences seront plus importants. La méthode permet un oubli des expériences anciennes au
profit des plus récentes. Ce qui signifie concrètement que la méthode sera adaptative en cas de En premier lieu, nous allons nous intéresser à une techniques d’apprentissage par
panne ou de changement dans l’environnement. Le facteur d’oubli sera dépendant de la valeur l’exemple, à savoir les réseaux de neurones. Comme son nom l’indique, cette technique est
du coefficient d’apprentissage . Il est également possible d’obtenir le même phénomène sur directement inspirée de l’étude du cerveau. L’objectif consiste à montrer une série
la version traditionnelle du Q-Learning en bornant la matrice Visit(s,a). d’exemples, chaque exemple étant associé à un stimulus d’entrée. Après cette phase
d’apprentissage, si le réseau est stimulé avec une configuration d'entrées, alors il saura
Un inconvénient de cette méthode est de déterminer le nombre et la position des automatiquement de quel exemple il s’agit. Les réseaux de neurones trouvent de nombreuses
centres. Il existe des méthodes adaptatives [Mulgrew 96][Burdsall 97] basées sur le principe applications dans de nombreux domaines, notamment en classification de données ou en
suivant : à chaque mise à jour du réseau, les centres sont rapprochés de ce point reconnaissance vocale.
proportionnellement à l’erreur de modélisation. La méthode consiste à concentrer les centres
aux environs des zones difficilement modélisables afin de minimiser l’erreur. Ensuite, nous présenterons les techniques d’auto-apprentissage. Ces méthodes, basées
sur les processus markoviens, permettent notamment de construire un modèle
L’Équation 32 demande de connaître la valeur de Q estimée maximale pour une entrée d’apprentissage. Une fois ce modèle construit, la technique consiste à déterminer quelles sont
donnée. Q étant estimé par le réseau, l’objectif est de trouver la valeur maximale du réseau les meilleures actions à réaliser. Lorsque ces actions permettent au système d’obtenir une
pour un état donné. récompense importante, leurs liens d’activation sont renforcés, on parle alors d’apprentissage
par renforcement.

95 32
 Dans les réseaux RBF, la fonction gaussienne la plus souvent utilisée est donnée par
l’Équation 33. Ce type de fonction est dérivable sur R. La première approche utilisée consiste
à calculer la fonction de transfert globale (Équation 34) du réseau (o=f(s,a)), la dériver par
rapport à la variable d’entrée a (Équation 35) et calculer les zéros de cette dérivée.

3
(x ci)²
f(x) e
Équation 33 : Fonction de transfert d’un neurone de type RBF

3. Les méthodes d'apprentissage

o f(s,a) w(e
i 0
i
(s csi)²
.e (a cai)²
)
avec :
Wi : poids synaptique,
Csi : position du centre dans l’espace d’entrée des états,
Cai : position du centre dans l’espace d’entrée des actions.
Équation 34 : Fonction de transfert du réseau pour un couple d’entrée à 1 dimension

n
do
da i 0
wi.e (s csi )²
.(a cai)e (a cai )²

Équation 35 : Dérivée de la fonction de transfert du réseau

Après calcul, il s’avère que ce type d’équation sous forme de somme d’exponentielles
ne présente pas de solution analytique. Pour nous affranchir de ce problème, nous avons
considéré une autre fonction de transfert pour les neurones de la couche cachée. Plutôt que
___________________________________________________________________________ d’utiliser une fonction exponentielle pour obtenir la gaussienne, nous avons utilisé un
polynôme du 4ème ordre borné sur l’intervalle [-1, 1]. La courbe montrée sur la Figure 57
représente le tracé de l’équation f(x)=x4-2.x2+1.

Depuis les débuts de la robotique, l’approche traditionnelle de programmation des

robots la plus utilisée est basée sur l’analyse et la géométrie. Cette approche a permis de
résoudre un grand nombre de problèmes, d’obtenir des preuves de convergence et de stabilité.
Un excellent exemple reste probablement la commande de bras manipulateurs, basée sur la
géométrie et la cinématique (modèle de Denavit et Artenberg), elle permet d’obtenir des
trajectoires rapides et précises. La stabilité de ces machines a pu être démontrée grâce
notamment au critère de Liapounov. Toutefois, il persiste de nombreux problèmes que cette
approche ne peut résoudre. Le principal étant qu'il faut d’envisager l’ensemble des cas
Figure 57 : Gaussienne obtenue en utilisant un polynôme d’ordre 4
possibles pendant la programmation. En effet, la réaction d’un système pré-programmé face à
une situation inconnue est incertaine. Il a donc fallu trouver des solutions alternatives à
l’approche mathématique pour permettre aux machines d’être plus autonomes. Le problème de cette fonction réside dans son espace de définition. En effet, cette
fonction n’est définie que sur l’intervalle [-1, 1]. Ici, la fonction de transfert globale sera
dérivable par intervalle et présentera une solution analytique sur chaque intervalle. Pour

31 96
trouver le maximum, il faudra calculer la solution analytique sur chaque intervalle, puis une démonstration de convergence ou une preuve d’optimalité permet de compléter ces
prendre le maximum des maxima. Nous avons estimé que cette solution était trop lourde à travaux. Dans notre cas, nous avons choisi de privilégier la robustesse au détriment de
implémenter, d’autant plus que l’algorithme est différent selon les positions des centres (selon l’optimalité. Nous préférons avoir un système moins efficace en terme de rendement, mais
le nombre de gaussiennes qui peuvent se chevaucher). plus performant en terme d’adaptation. Le but est de fabriquer des systèmes capables de
reconfigurer rapidement leur structure interne en cas de panne afin de pouvoir achever leur
Bien qu’une solution analytique aurait présenté de nombreux d’avantages, comme la mission. Les approches traditionnelles demanderaient de prévoir toutes les perturbations
simplicité de l’implémentation ou la rapidité des temps de calcul, nous avons dû renoncer à possibles afin de proposer une solution à chacune d’entre elles. Toutefois, pour des systèmes
cette approche. Nous nous sommes orientés vers une solution de recherche du maximum complexes devant évoluer en milieu inconnu, envisager l’ensemble des problèmes est
numérique. La fonction et sa dérivé sont parfaitement connues et la fonction peut présenter impossible, c’est pourquoi nous préférons utiliser une approche basée sur l’apprentissage, afin
des maxima locaux. Nous avons choisi de prendre l’hypothèse suivante afin d’accélérer les que les agents soient capables de s’adapter automatiquement aux changements. Le chapitre
temps d’apprentissage : nous estimons que le maximum se trouve à proximité de la suivant présente les techniques d’apprentissage les plus courantes.
gaussienne associée au plus grand poids synaptique. Bien que cette hypothèse ne puisse pas
être mathématiquement vérifiée, aucun contre-exemple n’a été rencontré pendant les
expérimentations. Dans les cas critiques ou l’hypothèse n’est pas vérifiée, la méthode prendra
un des maxima locaux (probablement le second, la statistique est inversement proportionnelle
au rang du maximum) donc l’erreur n’aura pas une grande influence sur l’approximation de la
Q-fonction.

Figure 58 : Modélisation de la Q-valeur

La suite de ces expérimentations a été réalisée par Bastien Jacquot, stagiaire de DEA.
Les expérimentations ont été réalisées sur BOP, le système de vision stéréoscopique présenté
précédemment. La première expérience, utilisée pour valider la méthode d’apprentissage a été

97 30
plusieurs agents n’ont pas de message à envoyer pendant plusieurs périodes, leur laps de réalisée sur un problème où les dimensions de l’espace d’état et d’action sont de un.
temps est quand même attribué et non utilisé. Ce type de communication demande de L’objectif de l’apprentissage est de centrer un point lumineux dans l’image d’une des deux
synchroniser parfaitement les agents et le nombre d’utilisateurs est limité par le découpage. caméras. La récompense est inversement proportionnelle à la distance entre la tâche
De plus l’allocation dynamique (ajout ou suppression d’un agent) est envisageable, mais lumineuse et le centre de l’image. Le problème revient à traquer la tâche lumineuse. Nous
complexe à mettre en œuvre. avons choisi ce type de marqueurs (lumineux) afin de pouvoir s’affranchir des problèmes de
traitement d’images.
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].
Figure 59 : Position des centres

La Figure 58 montre le résultat de la modélisation de la Q-fonction. L’état est donné

L’objectif de ce chapitre est de présenter les systèmes multi-agents. Les travaux et par la position du point traqué dans l’image et l’action correspond à un incrément de consigne
résultats antérieurs nous permettent de définir certains concepts comme l’opposition entre les sur le servomoteur. Sur cette figure quelques points représentatifs peuvent être remarqués
approches réactives et cognitives. L’approche réactive peut se présenter comme un comme le centre de coordonnées : état=0 et action=0, qui possède la valeur maximale de la Q-
complément ou une alternative aux architectures traditionnelles. Ou encore, cette même fonction. Cela vérifie bien que lorsque la tâche est centrée dans l’image (Etat=0) et que le
approche permet de résoudre des problèmes classiques de façon moins complexe et les servomoteur est immobile (Action=0), la récompense est maximale. L’allure générale de la
solutions proposées peuvent être plus facilement mises en œuvre sur des robots réels. Nous courbe vérifie bien les résultats escomptés : lorsque la tâche se trouve à gauche dans l’image
avons présenté et décrit trois agents réactifs : Silly Robot, Tom Thumb et Chain-Making (Etat < 0) il vaut mieux reculer le servomoteur (Action < 0) et inversement. Les meilleures
Robots. Ces trois exemples me semblent particulièrement pertinents et permettent de montrer récompenses se trouvent donc sur la diagonale. La méthode utilisée ici pour la modélisation
les faits suivants : est un réseau RBF avec une adaptation automatique de la position des centres. Cette dernière
Il est possible de décomposer un problème complexe en une succession est montrée sur la Figure 59. Les centres se trouvent plus concentrés au centre, là où la
d’actions/réactions basiques. modélisation est la plus importante.
Une modification (même minime) dans un comportement réactif permet d’augmenter
de façon significative les performances générales du système.
L’apport de communications (même indirectes) dans un système multi-agents permet L’exemple précédent a permis de montrer que la modélisation de la Q-fonction est
des modifications comportementales importantes, qui se traduisent par une possible et que les résultats permettent d’appliquer une politique maximisant la récompense.
amélioration des performances. Nous allons maintenant nous intéresser à l’apprentissage complet du problème. L’objectif est
de centrer la tâche dans les deux dimensions sur une caméra. Les espaces d’états et d’actions
A l’issue de ce chapitre, il me semble important de préciser la philosophie générale de ces comportent deux dimensions chacun.
travaux. Dans les recherches antérieures, quand les approches mathématiques le permettent,

29 98
 10

Figure 60 : Modélisation de l’Action 1 optimale en fonction de l’état de l’agent

Figure 9 : Les quatre robots IS Robotics R2e utilisés par D. Goldberg et M.J. Mataric (D'après [Goldberg
99])

Mais ce type d’approche supervisée est inadapté aux systèmes distribués pour deux
raisons principales. Afin de conserver les propriétés de robustesse et d’autonomie de ces
systèmes, il est préférable de ne jamais centraliser des informations essentielles sur un
système unique. De plus, il faut constamment garantir que chaque agent puisse rester en
contact avec la station ou le robot superviseur, ce qui n’est pas toujours possible, notamment
dans des tâches d’exploration.

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
10 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
Figure 61 : Modélisation de l’Action 2 optimale en fonction de l’état de l’agent
d’agents. De plus, l’utilisation de la bande passante est mauvaise, si par exemple un ou

99 28
 La conclusion de B. Jacquot est la suivante : " Si les résultats obtenus sont corrects
(Figure 60, Figure 61), il apparaît que la fonction Q-valeur est mal modélisée par le réseau
lorsque le temps d’apprentissage est restreint à des valeurs raisonnables. Cependant et malgré
cette mauvaise modélisation, le modèle obtenu pour les actions est très bon et notamment, le
Très tôt, les communications ont été l’un des principaux atouts des systèmes multi- découplage entre les servomoteurs se fait très rapidement, même s’il n’est pas parfait. En fait
agents. Il existe différents types de communications. Une des communications les plus et c’est à la fois un avantage et une difficulté d’interprétation, la fonction de Q-valeur n’est
simples est basée sur l’exemple du Petit Poucet [Drogoul 92]. Elle consiste à déposer sur le jamais entièrement explorée. De ce fait, la forme globale peut sembler non cohérente vue de
terrain des marques qui pourront être captées ou ramassées par d’autres agents. Ces marques l’extérieur, mais la fonction de Q-valeur peut localement être suffisamment bien modélisée
peuvent servir à définir un territoire qui a déjà été visité ou encore le chemin à suivre pour pour permettre à l’algorithme d’apprentissage de trouver un chemin optimal. "
atteindre une zone pertinente de l’environnement. On appelle ce type de communications : les
communications indirectes. Mais il en existe d’autres types : les communications directes.
Elles peuvent servir à transmettre des informations sur la position, l’environnement proche ou
encore l’état interne des agents. Par exemple, dans le modèle basé sur la satisfaction [Simonin
00] l’un des éléments principaux de la communication est la transmission d’un vecteur qui Ce chapitre traitait de l’apprentissage de comportements réactifs pour les systèmes
représente la satisfaction de l’agent. hétérogènes. Nous avons pris comme hypothèse de départ qu’un apprentissage collectif n’était
pas envisageable. L’apprentissage a donc été réalisé sur un agent isolé du reste du système.
Lorsque le nombre d’agents devient trop important, le problème des communications
se complexifie. En effet, faire communiquer entre eux plusieurs dizaines de robots pose un La première méthode d’apprentissage était basée sur le recuit simulé. Nous avons dans
certain nombre de problèmes. En premier lieu, lorsque le canal de communication est unique, un premier temps expérimenté la version traditionnelle du recuit simulé. L’objectif était de
les messages ne doivent pas entrer en collision. Un protocole de communication doit être faire apprendre une tâche d’évitement d’obstacles à un robot mobile. La première méthode
instauré afin de pouvoir adresser des messages individuels aux agents ou à l’ensemble du permet d'obtenir la convergence vers la solution optimale dans un environnement sain. Les
groupe. La similitude avec les réseaux informatiques est grande. D’ailleurs, un point commun résultats expérimentaux ont montré que la convergence n’était pas assurée dans des
entre les réseaux et les communications dans les systèmes multi-agents réside dans la environnements perturbés. Ces résultats justifient d’ailleurs les expérimentations sur plate-
dynamique du système, la perte ou l’ajout d’un agent ne doit pas empêcher le système de forme expérimentale, qui permettent de mettre en évidence certains phénomènes non
continuer à fonctionner. perceptibles en simulation.

Toutefois, une particularité des systèmes multi-agents réside dans le concept de Nous avons ensuite proposé une méthode d’apprentissage adaptative inspirée du recuit
proximité. Les communications peuvent être globales ou locales. Dans ce deuxième cas, seuls simulé. Cette méthode ne garantit pas la convergence vers la solution optimale, en revanche,
les agents qui se trouvent à proximité de l’agent émetteur peuvent recevoir le message. Ce elle permet d’accélérer les temps d’apprentissage et d’adapter le contrôleur en cas de panne
type de communication peut aussi être employé pour parvenir à une communication globale ou de changement extérieur. Il est important de préciser qu’à l’issue de ces travaux, les
grâce à la propagation des messages. Dans l’architecture satisfaction/altruisme [Simonin 00], méthodes inspirées du recuit simulé demande un réglage non trivial des paramètres. Ce
la satisfaction interactive des agents est constamment transmise et propagée au travers de réglage est crucial pour les temps d’apprentissage, les propriétés de convergence et les
l’environnement de façon implicite, par les agents. facultés d’adaptation du système.

Enfin, nous avons proposé une extension de l’apprentissage par renforcement aux
systèmes continus. La méthode consiste à modéliser la Q-fonction en utilisant un réseau de
neurones de type RBF. Ce type de réseau permet une modélisation locale de la Q-fonction. Il
Les premières méthodes permettant de faire communiquer des robots mobiles est donc possible d’accélérer les temps d’apprentissage en concentrant l’apprentissage sur des
consistaient à centraliser tous les échanges de messages. Ce type de protocole existe toujours zones de l’espace d’états présentant des récompenses importantes. Les expérimentations
dans divers système multi-robots. Comme par exemple dans le projet Martha ou l’objectif est menées sur notre système stéréoscopique ont montré une approximation suffisante de la Q-
de coordonner plusieurs dizaines de robots mobiles transportant des containers dans des fonction, permettant de déterminer les meilleures actions à exécuter depuis un état donné.
aéroports ou sur des quais [Alami 98]. Dans ce type de système, il y a un robot superviseur
qui centralise les décisions et les communications. De manière générale, les temps d’apprentissage évoluent exponentiellement avec la
complexité de la tâche. L’apprentissage de tâches réactives pour les systèmes hétérogènes
Il existe aussi des systèmes distribués utilisant un système de communication demande des temps d’apprentissage importants. Il nous apparaît essentiel de ne pas tenter
centralisé comme l'illustrent les agents de L. Parker [Parker 99] qui utilisent une machine d’apprendre directement une tâche complexe. Pour obtenir la convergence dans des temps
centrale qui supervise les messages, des communications par réseau central sans fil, comme raisonnables, la meilleure solution consiste à diviser la tâche en plusieurs tâches de bas
les robots fourrageurs (Figure 9) de D. Goldberg et M.J. Mataric [Goldberg 99]. Ce type de niveaux. Ces résultats confirment donc les hypothèses communément acquises dans les
système utilise un réseau TCP/IP avec des stations fixes. systèmes multi-agents distribués.

27 100
 Architecture à base de combinaisons vectorielles. Inhiber des comportements ne permet
pas toujours d’obtenir un résultat assez fin. Il existe ainsi des architectures basées sur une
combinaison vectorielle des sorties de chaque comportement. Un vecteur de sortie est
constitué de l’ensemble des consignes calculées par un module. La consigne appliquée aux

7
moteurs sera alors une combinaison vectorielle de l'ensemble des vecteurs de sortie. La Figure
7 montre un exemple d’architecture à base de combinaison vectorielle. Le vecteur de sortie est
constitué de deux consignes Mg et Md, le vecteur effectivement appliqué sur les actionneurs
sera une somme des vecteurs de sortie.

Mg
Comportement i
Entrées
Md Vi
7. Conclusion générale Mg Vecteur
appliqué aux
Mg Md actionneurs
Comportement i+1 Vi Vi 1
Entrées Md Vi 1

Figure 7 : Un exemple d’architecture à base de combinaison vectorielle

Sur l’exemple de la Figure 7, la combinaison vectorielle est une somme des vecteurs
de sorties, mais il existe aussi d’autres architectures basées sur des combinaisons vectorielles
plus complexes. Par exemple dans l’architecture satisfaction / altruisme proposée par J. Ferber
et O. Simonin [Simonin 00][Lucidarme 02], chaque agent dispose d’une satisfaction
personnelle et d’une satisfaction interactive qui est émise vers les autres agents. Ces deux
satisfactions seront prisent en compte dans la combinaison des actions. L’architecture d’un
agent est donnée sur la Figure 8.

___________________________________________________________________________ Agent k

Perceptions physiques Satisfaction

Les travaux présentés dans ce mémoire avaient pour but l’étude de techniques interactive
Sat. Ik émise
d’apprentissage appliquées aux systèmes multi-agents. Arrivé au terme de ces travaux, nous
nous proposons de faire un rapide bilan de chaque chapitre avant d’en évoquer les conclusions Sat. I reçue
Selection /
et les perspectives. Agents voisins combinaison
Sat. P d’actions
Le premier chapitre introductif, présente le contexte de ces travaux en insistant sur les
Environnement
futures tâches que ces recherches pourraient permettre d’accomplir. Ces travaux s’orientent Perceptions
vers des tâches d’exploration, de recherche, d’analyse et de sauvetage en milieu inconnu ou physiques

dangereux (milieu spatial, sous-marin ou encore nucléaire). Ces recherches s’inscrivent dans Actions
deux cadres principaux : les systèmes multi-agents et l’apprentissage. Les techniques
d’apprentissage actuelles ne permettent pas de résoudre des problèmes complexes. C’est
pourquoi ces travaux se focalisent sur l’apprentissage de comportements réactifs. Figure 8 : Architecture satisfaction / altruisme (D'après [Simonin 00])

Le deuxième chapitre présente les systèmes multi-agents. Après une introduction et

quelques définitions sur les systèmes multi-agents, les principales tâches génériques étudiées
dans les travaux antérieurs sont présentées. Ces travaux antérieurs montrent clairement

101 26
 En 1986, Rodney A. Brooks [Brooks 86] propose une approche différente qui reste l’intérêt de l’approche multi-agents, ils s’inscrivent notamment comme un complément aux
aujourd’hui encore une référence dans le domaine des systèmes multi-agents. Cette techniques de programmation dite traditionnelle. En s’appuyant sur les hypothèses émises par
architecture, appelée " subsomption ", consiste à paralléliser les tâches. La Figure 5 décrit les Rodney Brooks, il serait donc possible de construire de nouvelles architectures logicielles
différentes couches comportementales d’un agent. pour les systèmes multi-robots, basées sur des bibliothèques de comportements réactifs.
Enfin, les différents protocoles de communication employés dans les systèmes multi-agents
sont présentés.

Dans le troisième chapitre, les principales techniques d’apprentissage sont décrites. Le

parallèle avec le vivant est omniprésent et ces méthodes d’apprentissage sont généralement
inspirées du vivant à commencer par les réseaux de neurones. Seules les techniques les plus
courantes ont été décrites : les réseaux linéaires, la rétropropagation du gradient, et les réseaux
à fonctions radiales. Ces techniques nécessitent de fournir aux réseaux des bibliothèques
d’exemples, ce qui est mal indiqué pour nos problèmes d’auto-apprentissage. Une seconde
technique basée sur les processus markoviens est présentée : l’apprentissage par
renforcement. Là aussi, seules les méthodes les plus connues sont présentées : la
Figure 5 : Décomposition basée sur le comportement d'accomplissement de tâches (D'après [Brooks 86]) programmation dynamique et le Q-learning. Ces méthodes présentent l’avantage d’être
parfaitement appliquées aux problèmes d’auto-apprentissage, mais nécessitent de stocker des
bases de données importantes et surtout sont mal indiquées pour les applications aux
Chacune de ces couches relie les capteurs aux actionneurs et permet un comportement problèmes continus. Puis, est présentée une autre méthode d’apprentissage inspirée elle-aussi
particulier ou une compétence spécifique, comme la locomotion, l’évitement d’obstacles ou la du vivant : les algorithmes évolutionnistes. Ces méthodes, directement inspirées de
saisie d’objets. Ce type d’architecture permet notamment la décomposition d’une tâche l’évolution darwinienne, semblent parfaitement indiquées à nos problématiques, à un détail
complexe en plusieurs comportements réactifs. Ce type d’approche vise aussi à accroître la près : ce sont des méthodes supervisées et ces travaux s’inscrivent dans le tout-distribué.
fiabilité du système. Dans l’architecture traditionnelle, si une panne survient sur l’un des Avant de clôturer ce chapitre, un dernier paragraphe est consacré à l’estimation de la
modules, alors la panne se généralise à l’ensemble du système, chaque module étant essentiel performance, car la façon dont les agents sont récompensés peut influencer l’apprentissage et
au fonctionnement de l’ensemble. Dans l’architecture proposée par Rodney A. Brooks, même ce paragraphe synthétise les différentes façons d’estimer les performances d’un agent.
après la perte d’un module, le système peut continuer à fonctionner en mode dégradé, en
inhibant ce module par exemple. Afin de pouvoir expérimenter les méthodes et techniques proposées dans des
conditions réelles, une plate-forme expérimentale a été construite. Cette plate-forme est
L'architecture de forçage / inhibition et celle à base de combinaison vectorielle sont décrite en détails dans le quatrième chapitre. Elle est principalement constituée de cinq robots
deux exemples d’architectures réactives de type " subsomption " mobiles Type 1. Ces robots ont été construits dans le but d’évoluer ensemble dans le même
environnement. Ils peuvent se déplacer, détecter les obstacles, communiquer entre eux et sont
Architecture de forçage / inhibition. La Figure 6 représente un module d’une telle totalement autonomes en terme d’énergie et de puissance de calcul. L’un de ces robots a été
architecture. Ses entrées peuvent être forcées pendant une certaine durée, de même les sorties associé à un manipulateur miniature pour former M3 (Manipulateur Mobile Miniature). Ce
peuvent être inhibées pendant un laps de temps. Des comportements plus complexes peuvent manipulateur à la conception originale présente une dynamique particulièrement intéressante.
ainsi être construits en imbriquant les modules de base. La structure globale permettra En effet, aucun moteur ne doit supporter le poids des autres actionneurs, puisque tous les
d’inhiber les comportements non prioritaires et de forcer les fonctions vitales. Par exemple le moteurs sont fixés sur le châssis et que les mouvements sont transmis par des jeux de poulies
signal d’entrée du module dédié à la locomotion peut être forcé pour le remplacer par un et de courroies. Cette plate-forme expérimentale est également complétée d’un système de
signal d’évitement d’obstacle afin d’empêcher une collision. stéréovision BOP. Ce système, équipé de 2 caméras mobiles, peut acquérir plusieurs images
d’un même objet en multipliant les points de vue et ainsi estimer sa position dans l’espace
Inhibition avec une grande précision.

Le cinquième chapitre est consacré à l’apprentissage de comportements réactifs pour

Comportement i les systèmes multi-robots homogènes. Ce chapitre est uniquement basé sur une approche
Entrées Durée t1 Durée t2 Sorties évolutionniste, la première partie détaille une expérience menée à l’EPFL sur l’apprentissage
d’un comportement d’évitement d’obstacles grâce aux algorithmes génétiques. Cette
expérience montre notamment que de telles méthodes d’apprentissage permettent à une
population de robots d’améliorer ses propres performances aux fil des générations. Cette
Forçage expérience a été réalisée de manière supervisée. Afin de prouver qu’une telle méthode pouvait
être appliquée sur un système entièrement distribué, nous avons présenté une version
Figure 6 : Un module de l'architecture forçage / inhibition distribuée des algorithmes évolutionnistes. Les opérateurs de croisements et de mutations et

25 102
les communications ont été redéfinies afin de permettre aux agents de réaliser les croisements
par couple. La méthode a également été testée sur une tâche d’évitement d’obstacles en
simulation et sur les robots. L’étude des résultats a permis d’étudier l’influence des
paramètres et on distingue lors de l’apprentissage des paliers correspondant chacun à une
étape de l’évolution.

Le sixième chapitre est consacré à l’apprentissage de comportements réactifs appliqué

aux systèmes hétérogènes. L’hypothèse de départ est ici que l’apprentissage collectif n’est pas
envisageable et les méthodes sont appliquées sur un agent isolé de la population. La première
méthode utilisée est basée sur l’application du recuit simulé, deux versions sont présentées :
une première version traditionnelle et une seconde version améliorée permettant
principalement d’accélérer les temps d’apprentissage et de s’adapter aux pannes et
modifications de l’environnement. Les méthodes basées sur le recuit simulé, permettent
d’obtenir une convergence rapide, mais ne garantissent pas la convergence vers la solution
optimale. Les risques d’être happé dans un maxima local sont grands. La deuxième partie de
ce chapitre est consacrée à l’apprentissage par renforcement. Afin de diminuer les durées
d’apprentissage et de minimiser la taille des données mémorisées, la matrice Q est
approximée par un réseau de neurones de type RBF. Les expérimentations menées sur le Figure 3 : Diagramme des Chain-Making (D'après [Drogoul 92])
système de stéréovision BOP ont montré l’exactitude de l’approximation réalisée par le réseau
ce qui permet au Q-learning de déterminer la meilleure action à réaliser dans chaque La méthode des chain-making donne de meilleurs résultats que les deux précédentes
configuration. quel que soit le nombre de robots. De plus, dans la simulation réalisée par A. Drogoul et J.
Ferber, même pour un nombre élevé de robots, le phénomène d’embouteillage n’apparaît plus
Les méthodes étant assez éloignées les unes des autres, il était assez difficile de les et la stabilité est atteinte. De manière générale, un minimum de modifications au niveau
comparer de façon quantitative. C'est pourquoi les résultats sont synthétisés selon cinq comportemental permet un accroissement des performances globales.
critères:
La rapidité de convergence, relative aux durées d'apprentissage.
L'application au domaine continu, la méthode est-elle plutôt indiquée pour les
problèmes discrets ou continus ? Depuis le début de la robotique et ce jusqu’aux années 90, la majeure partie des
Les capacité d'adaptation, le contrôleur appris est-il dédié à des circonstances précises systèmes robotisés étaient basée sur la même architecture (Figure 4). Les informations sur
ou peut-il évoluer en cas de changement ? l’environnement sont stockées, analysées et modélisées avant que l’agent puisse prendre une
décision. Ce type d’architecture est dit cognitif.
L'optimalité de la solution, le résultat est-il un maxima absolu ou local ?
La taille des données mémorisées.

La Figure 62 montre les performances des méthodes évolutionnistes. On distingue que les
algorithmes génétiques proposent des performances moyennes sur l'ensemble des critères
avec toutefois un point faible : la lenteur de convergence et un point fort: la faible taille des
données mémorisées. La version distribuée proposée dans ce manuscrit ne modifie pas ces
performances, elle évite de centraliser l'ensemble des données.

La Figure 63 montre les performances du recuit simulé dans deux versions : le recuit
simulé traditionnel (en continu) et la version proposée (en pointillés). La version
traditionnelle dispose de performance correctes sur l'ensemble des critères, à l'exception des
capacités d'adaptation. En effet, lorsque la température est faible, le système ne peut plus
évoluer. Il produit donc un contrôleur dédié. A l'inverse, la version proposée dispose d'une
grande capacité d'adaptation, mais cette amélioration se fait au détriment de l'optimalité et le
système se fait happer dans les minimums locaux.

Figure 4 : Architecture traditionnelle de décomposition du programme de contrôle du robot en différents

modules de fonctionnement (D'après [Brooks 86])

103 24
 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 Figure 62 : Performance des méthodes évolutionnistes
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.

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. Le diagramme
de ce type de comportement est présenté figure 3.

Figure 63 : Performance du recuit simulé

23 104
 Les systèmes réactifs et cognitifs sont deux familles opposées de systèmes multi-
agents. Dans un système réactif, l’agent perçoit localement son environnement (et
éventuellement son état interne) et déduit immédiatement les actions à réaliser en se basant
uniquement sur cette source d’information. Ce principe se base sur l’action réflexe [Zapata
92]. Les trois exemples qui suivent (Silly Robot, Tom Thumb et Chain-Making Robot) sont
tous basés sur des architectures réactives. Ces trois exemples ont été volontairement décrits et
explicités afin de montrer qu’un système multi-agents réactif peut avoir des performances très
honorables et que des modifications mineures (ajout de communications par exemple)
peuvent augmenter de façon significative les performances du système.

Dans un article relatif à la coopération [Steels 89], Steels décrit des robots ramassant des
échantillons en milieu inconnu. La structure décrite ci-après a été conçue afin de réaliser une
tâche de type " la mine ". Les robots peuvent détecter la base grâce à un signal émis par celle-
ci. A condition d’être suffisamment près, il est possible de sentir les mines (les attracteurs)
grâce aux stimuli. Les robots peuvent également ramasser les échantillons et les déposer.

Figure 64 : Performance de l'apprentissage par renforcement

La Figure 64 compare les performances du Q-Learning à l'extension proposée dans ce

manuscrit. La courbe continue montre les performances d'un Q-Learning classique, et la
courbe en pointillés les performances modifiées grâce à l'apport d'un réseau de neurones
modélisant la matrice Q. On constate que le Q-Learning dispose de caractéristiques
relativement mauvaises sur l'ensemble des critères à l'exception l'optimalité. En effet, la
convergence a été prouvée pour les systèmes déterministes. L'ajout d'un réseau de neurones
augmente globalement les performances : la méthode s'applique dorénavant au domaine
continu. La convergence est plus rapide car le réseau interpole les points non visités. La taille
des données est diminuée car il ne reste que les poids synaptiques à mémoriser. Mais la
modélisation n'est pas parfaite, et la méthode perd donc ses propriétés d'optimalité.

Les recherches à venir s’orienteront vers l’étude de l’apprentissage d’autres

comportements réactifs, comme par exemple, du suivi et ralliement de cibles, de la saisie
d’objet ou des tâches de navigation plus complexes. Ces expériences pourront être menées sur
la plate-forme expérimentale et permettront de disposer de bibliothèques de comportements Figure 2 : Diagramme des " Silly Robot " (D'après [Drogoul 92])
réactifs associés aux robots.
Le plus simple des comportements est décrit sur le diagramme de la Figure 2. Le robot se
Les futures recherches pourront s’orienter vers l’étude de la combinaison de plusieurs déplace de façon aléatoire jusqu'à ce qu’il sente une mine. Il se dirige vers celle-ci afin d’y
méthodes d’apprentissage: par exemple, la combinaison du recuit simulé et des méthodes ramasser un échantillon, puis il retourne à la base pour le déposer avant de revenir dans une
évolutionnistes pour des populations homogènes. Le recuit simulé permet une convergence phase de déplacement aléatoire. Malgré leur manque d’organisation sociale, ces robots à
rapide vers les maxima locaux ou globaux, alors que les méthodes évolutionnistes permettent l’efficacité réduite vont servir de base aux prochaines générations d’agents. Et nous allons
une convergence vers l’optimum absolu. L’idée est donc de disposer d’une population voir que des modifications mineures à l’échelle du comportement individuel peuvent
d’individus capables d’atteindre rapidement des solutions locales et la sélection naturelle bouleverser l’organisation globale.
permettra de ne conserver que les meilleurs. De même, un agent isolé du groupe pourra

105 22
 évoluer seul, mais les échanges avec le reste de la population permettra d’accélérer
l’apprentissage.
Les premières recherches sur la coopération multi-agents portaient sur l’étude du
Nous nous sommes concentrés dans ces travaux sur l’apprentissage de comportements
milieu animal, notamment celui des insectes. Ces études ont rapidement montré que chaque réactifs. Les futures recherches devront s’orienter vers l’apprentissage de comportements et
insecte n’avait pas ou peu conscience de son rôle dans la tâche globale réalisée par l’ensemble
de stratégies plus complexes. Non pas en complexifiant les tâches à apprendre, mais en
de l’essaim. Ces actions étaient uniquement guidées par des changements de comportement. synthétisant les comportements réactifs au sein d’une architecture d’apprentissage de plus
Ce phénomène a rapidement intéressé les roboticiens qui se sont inspirés de ce milieu afin de
haut niveau permettant un séquencement ou un mixage de ces comportements. Des
réaliser des flottes de robots coopérants. Les premiers articles concernant les systèmes multi- architectures du type Satisfaction/Altruisme ou ALLIANCE semblent être bien appropriées
agents remontent au début des années 80 pour la robotique. Les premiers objectifs furent de
aux contraintes de robustesse et d’adaptation nécessaires à de telles tâches.
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

Figure 1 : Simulation pour chacune des tâches (D'après [Arkin 92])

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.

21 106
 contraire, avec une flotte de robots, il est envisageable d’envoyer plusieurs agents, plus
simples, plus légers et redondants. La flotte peut en effet disposer de plusieurs systèmes de
vision et d’action sur l’environnement. En cas de panne totale ou partielle d’un agent, le
système peut alors continuer à fonctionner en mode dégradé. Il faut bien sûr pour cela que le
système ait été conçu de façon à pouvoir s’adapter aux pannes. De plus, pour certaines tâches,
notamment dans la recherche de survivants, les zones à explorer sont parfois tellement vastes
que l’emploi d’une flotte de robots est imposé par la nature même de la mission.

" Celui qui agit, produit un effet " est la définition de l’agent selon le dictionnaire Larousse.
Cette définition, même si elle correspond partiellement au sens des multi-agents reste
incomplète. Elle a été reformulée par J. Ferber [Ferber 95].

On appelle agent, une entité physique ou virtuelle

qui est capable d’agir dans un environnement,
qui peut communiquer directement avec d’autres agents,
qui est mue par un ensemble de tendances (sous la forme d’objectifs individuels ou
d’une fonction de satisfaction, voire de survie, qu’elle cherche à optimiser),
qui possède des ressources propres,
qui est capable de percevoir son environnement,
qui ne dispose que d’une représentation partielle de cet environnement (et
éventuellement aucune),
qui possède des compétences et offre des services,
qui peut éventuellement se reproduire,
dont le comportement tend à satisfaire ses propres objectifs, en tenant compte des
ressources et des compétences dont elle dispose et en fonction de sa perception de ses
représentations et des communications qu’elle reçoit.

Pour illustrer cette définition, donnons ici quelques exemples. Peut-être considéré comme
un agent : un robot, une partie d’un robot (le robot pourrait alors être vu comme un système
multi-agents), un programme informatique ou une partie d’un programme etc. Dans la suite
du document, nous considèrerons notre robot comme un agent et nous étudierons donc
l’évolution et la coopération au sein d’un système multi-robots.

On distingue les systèmes homogènes des systèmes hétérogènes. La différence réside

dans la structure des agents : dans un système homogène, les agents sont tous identiques et
disposent, par conséquent, des mêmes moyens de perception et d’action sur l’environnement.
Dans un système hétérogène, les agents sont différents et parfois spécialisés dans certaines
tâches. La réalisation de certains objectifs peut nécessiter la collaboration d’agents aux
compétences différentes et spécifiques. Par exemple, pour une tâche d’exploration de
l’environnement, une grande population d’agents explorateurs identiques permettrait de
diminuer le temps nécessaire à la visite complète de l’environnement. Il s’agit là d’un système
homogène. Pour une tâche de collecte d’échantillons en milieu inconnu, une population
composée d’agents explorateurs, d’agents manipulateurs et d’agents transporteurs serait bien
approprié. Il suffit de regarder un chantier moderne pour s’apercevoir que tout est régi comme
un système multi-agents hétérogène. Chaque engin a sa propre tâche et ses propres
spécifications.

107 20
 2
2. Les systèmes multi-agents

___________________________________________________________________________

Dans ce document, nous allons nous préoccuper d’un type de comportements

particuliers: la coopération. Un exemple classique est celui d’une population de fourmis.
L’une de ces dernières, prise seule, dispose d’une " intelligence réduite ". Mais l’ensemble de
la population est capable de collaborer afin de réaliser des tâches complexes. Il semble
toutefois important de préciser que notre but n’est pas de copier le plus fidèlement possible le
milieu animal, mais d’en tirer une source d’inspiration.

Cette inspiration animale pourrait bien être appliquée à un grand nombre de tâches, en
milieu hostile par exemple. Les principales recherches sur les systèmes multi-agents
s’orientent vers des travaux dans l’aérospatiale, le milieu sous-marin, le nucléaire ou encore
pour des tâches de sauvetage en milieu hostile. L’approche multi-agents présente plusieurs
avantages pour ce type de tâches. Si une panne survient sur un robot ne disposant que d’un
seul système de commande, de vision et de préhension, c’est toute la mission qui échoue. Au

19 108
 une mission complexe en plusieurs missions ou tâches de plus bas niveaux s’exécutant en
parallèle. Ces travaux s’intéressent à l’apprentissage d’actions réflexes ou encore de
Bibliographie comportements réactifs où les réactions sont les effets immédiats d’une perception. Ces
comportements ne sont jamais le résultat d’un raisonnement de haut niveau mettant en jeu des
données complexes du type carte de l’environnement ou représentation interne des agents.

La structure de ce manuscrit est la suivante :

Le deuxième chapitre se concentre sur la présentation des systèmes multi-agents. Les

___________________________________________________________________________
travaux antérieurs les plus pertinents sont décrits, justifiant l’utilisation d’architectures
distribuées dans des situations où les systèmes supervisés serait inefficaces.

Le troisième chapitre s'intéresse aux méthodes d’apprentissage. Les principales techniques

[Alami 98] R. Alami, S. Fleury, M. Herrb, F. Ingrand and F. Robert "Multi-robot
sont présentées et détaillées : réseaux de neurones, apprentissage par renforcement et
cooperation in the Martha project", IEEE Robotics and Automation
algorithmes évolutionnistes.
Magazine, 5(1), p.36-47, 1998.
Le quatrième chapitre est consacré à la description de notre plate-forme expérimentale.
Afin de valider les méthodes proposées dans des circonstances réelles, nous avons construit
[Anderson 93] C. Anderson, "Q-Learning with Hidden-Unit Restarting" Advances in
une plate-forme composée de quatre robots mobiles, un manipulateur mobile et un système de
Neural Information Processing Systems, volume 5, S. J. Hanson, J. D.
vision stéréoscopique.
Cowan, and C. L. Giles, eds., Morgan Kaufmann Publishers, San Mateo,
CA, p. 81–88, 1993.
Le cinquième chapitre est dédié à l’étude de l’apprentissage de comportements réactifs sur
des populations de robots identiques. Cette étude s’oriente vers l’application des algorithmes
[Arkin 92] R.C. Arkin, " Cooperation without Communication : Multiagent Schema-
évolutionnistes aux systèmes multi-agents. Des travaux antérieurs sont présentés et nous
Based Robot Navigation ", Journal of Robotic Systems, Vol. 9 (3), p.
décrirons une évolution distribuée de ces méthodes.
351-364, avril 1992.
Le sixième chapitre traite de l’apprentissage de systèmes hétérogènes, c'est-à-dire dans le
[Balch 94] T. Balch and R.C. Arkin, " Communication in Reactive Multiagent
cas de robots disposant de capacités différentes. Ce chapitre est composé de deux parties : une
Robotic Systems ", Autonomous Robots, 1, p 27-52, 1994.
méthode d’apprentissage basée sur le recuit simulé et une seconde partie basée sur
l’apprentissage par renforcement.
[Brainteberg 84] V. Braitenberg, "Vehicule experiments in synthetic psychology", MIT
Press, Cambridge, MA, 1984.
Enfin, nous conclurons sur l’ensemble de ces travaux dans le dernier chapitre.
[Brooks 86] R. A. Brooks, "A robust layered control system for a mobile robot", IEEE
Journal of Robotics and Automation, p. 14-23, 1986.

[Burdsall 97] B. Burdsall, C. Giraud-Carrier, "GA-RBF: A Self-optimising RBF

Network", Third International Conference on Artificial Neural Networks
and Genetic Algorithms, Norwich, UK, p. 346-349, 1997

[Cullogh 43] W.S. Mc Cullogh and W. Pitts , " A logical calculus of the ideas
immanent in nervous activity ", Bulletin of Mathematical Biophysics 5,
p. 115-133, 1943.

[Drogoul 92] A. Drogoul and J. Ferber, " From Tom Thumb to the Dockers : Some
Experiments with Foraging Robots ", 2nd International Conference on
Simulation of Adaptative Behaviour, Honolulu, p 451-459, 1992.

[Ferber 95] J. Ferber, "Les systèmes multi-agents, vers une intelligence collective",
Livre InterEdition, 1995.

109 18
 Parmi toutes les applications de la robotique, chacun s’accorde à dire que l’accent doit [Floreano 94] D. Floreano et F. Mondada, " Autonomic creation of an autonomous
être mis sur le respect de la vie humaine et la préservation de l’environnement. Par exemple, agent : Genetic evolution of a neural-network driven robot ", Simulation
si des machines avaient remplacé les hommes lors de la catastrophe de Tchernobyl, bon of Adaptive Behavior, from animals to animats 3, 1994.
nombre de vies auraient été épargnées. Suite à un attentat ou un tremblement de terre, les
recherches de survivants seraient accélérées si des flottes de robots pouvaient être envoyées [Golberg 89] D. E. Goldberg, "Genetic Algorithms in Search, Optimization and
dans les décombres. L’exploration des coques de pétroliers et le pompage sous-marin des Machine Learning", Addison-Wesley, 1989.
cuves permettrait d’éviter les marées noires, nocives pour la santé et l’environnement. Ces
quelques exemples n’ont pas été pris au hasard, ils se situent tous en milieu hostile : c'est-à- [Goldberg 99] D. Goldberg et M.J. Mataric, "Coordinating mobile robot group behavior
dire des zones difficilement accessibles voire dangereuses pour l’homme. C’est pourquoi y using a model of interaction dynamics", Proceedings, Autonomous
envoyer des robots afin d’y réaliser une mission permettrait d’épargner des vies. Seulement, il agents Seattle, WA, p. 100-107, 1999.
n’est pas toujours possible de téléopérer ces machines. Par exemple pour l’exploration
martienne, les transmissions mettent environ 30 minutes pour atteindre la planète rouge. De [Goldberg 00] D. Goldberg and M.J. Mataric, "Robust Behavior-Based Control for
plus, le retour d’information, souvent incomplet, ne permet pas à l’opérateur de disposer de Distributed Multi-Robot Collection Tasks," USC Institute for Robotics
toutes les informations nécessaires à la prise de décision. C’est pourquoi ces machines doivent and Intelligent Systems Technical Report IRIS-00-387, 2000.
disposer d’un maximum d’autonomie. Elles doivent être capables de s’adapter à des
environnements inconnus, des situations imprévues et des pannes. [Hebb 49] D.O. Hebb, " The Organisation of Behaviour", Wiley, New York, 1949

Les techniques de programmation des robots les plus répandues sont basées sur le tout- [Hopfield 82] J.J. Hopfield, "Neural Networks and Physical Systems with Emergent
programmé. C’est-à-dire que l’ensemble des situations envisageables a été programmé, soit Collective Computational Abilities", Proceedings of the National
de manière discrète, soit de manière continue, soit de manière mixte. Mais il est évident que Academy of Sciences, p. 460-464, 1982.
ces méthodes ne permettent pas de résoudre tous les problèmes. Pour des missions complexes
d’exploration ou de sauvetage, l’ensemble des cas ne peut être envisagé et programmé. De [Kane 86] T.R. Kane et D.A. Levinson, "The use of Kane’s dynamical equations in
nouvelles méthodes qui se présentent comme complémentaires au tout-programmé sont robotics", The International Journal of Robotics Research 2, No. 3, 1986,
apparues depuis une vingtaine d’années. Nos travaux vont s’intéresser principalement à deux pp. 3-21, 1986.
d’entre elles : les systèmes multi-agents et l’apprentissage.
[Kretchmar 97] R. Kretchmar et C. Anderson, "Comparison of CMAC’s and radial basis
Dans ce manuscrit, nous allons nous intéresser à l’auto-apprentissage. Au lieu de functions for local function approximators in reinforcement learning", In
programmer un robot pour qu'il effectue une mission, nous allons le laisser apprendre seul sa proceedings od the IEEE international Conference on Neural Networks,
propre stratégie. Dès lors qu’il apparaît concevable qu’une machine soit capable de modifier Houston, TX, p. 834-837, 1997.
son propre comportement, son propre programme, il ne semble plus y a voir de limite à son
développement. Pourtant, voici les deux principaux freins : [Lucidarme 02] P. Lucidarme, O. Simonin et A. Liégeois, "Implementation and
Evaluation of a Satisfaction/Altruisme-Based Architecture for Multi-
Les données mémorisées sont trop importantes. En effet, toute méthode d’apprentissage Robot Systems", proc. ICRA’02, Washington D.C., p. 1007-1012, 2002.
nécessite d’enregistrer des données. Malgré l’accroissement des mémoires informatiques,
certains problèmes ne sont pas solvables, faute de place. Il existe des méthodes, [Luh 80] J.Y.S. Luh, M.W. Walker et R.C.P. Paul, "On line computational scheme
notamment le Q-learning, qui permettent de trouver la solution optimale pour un problème for mechanical manipulators" Trans. Of the ASME Journal of Dynamic
déterministe. Mais ces méthodes demandent d’enregistrer des données statistiques Systems, Measurement and Control, Vol. 102, p69-76, 1980.
importantes et ne peuvent pas toujours résoudre ce type de problème.
[Madani 02] T. Madani, A. Benallegue and N.K. M'SIRDI, " Apprentissage par
Les temps d’apprentissage reste le frein principal à l’émancipation des machines. La renforcement pour la Navigation d'un Robot Mobile dans des
relation liant les temps d’apprentissage à la complexité du problème sont exponentiels. La Environnements Inconnus ", Journée des Jeunes Chercheurs en
convergence du Q-learning a été prouvée pour un temps d’apprentissage infini. C’est Robotique, 2002.
pourquoi il est inconcevable de faire apprendre à une machine en 10 ans ce que l’humanité
à appris durant des millions d’années. [Miller 90] Miller, W. T., F. H. Glanz et L. G. Kraft. "CMAC:An associative neural
network alternative to backpropagation" Proceedings of IEEE, 78, p.
Ces deux limites nous montrent qu’il n’est pas envisageable de tenter de procéder 1561–1567, 1990.
directement à la résolution de problèmes complexes en appliquant les méthodes
d’apprentissage tel quel. C’est pour cette raison que l’apprentissage doit être découpé et [Minsky 69] M. Minsky and S. Papert, " Perceptron ", The MIT Press, Cambridge,
progressif. L’approche envisagée dans ces travaux est basée sur l’approche dite 1969.
" subsomption " présentée dans le deuxième chapitre. Cette méthode consiste à décomposer

17 110
[Mitchell 97] T. M. Mitchell, "Machine learning", Livre, Mc Graw-Hill International Même s’ils se sont discrètement intégrés dans nos vie, une grande partie du défi n’est
Editions, 1997. pas encore relevée. Ces machines, qui existent depuis plusieurs années maintenant, ne
disposent que d’un très faible pouvoir décisionnel. Elles sont programmées pour réaliser la
[Mitiguy 96] P.C. Mitiguy and T.R. Kane, "Motion Variables Leading to Efficient même tâche successivement sans pouvoir s’adapter aux événements pour lesquels elles n’ont
Equations of Motion", The International Journal of Robotics Research, pas été programmées. Des problèmes, insoupçonnés à l’époque, sont apparus au cours des
Vol. 15, No. 15, pp. 522-532, October 1996. années et des avancées technologiques. Par exemple, localiser un robot dans un
environnement inconnu, reconnaître des objets caractéristiques dans une image, piloter des
[Mulgrew 96] B. Mulgrew, "Appling Radial Basis Functions," IEEE Signal Processing processus régis par des systèmes d’équations complexes restent des problèmes ouverts.
Magazine, vol. 13, p. 50–65, Mars 1996.
J’ai le sentiment que le changement de millénaire a été une période cruciale pour la
[Mondada 89] D. Mondada, E. fanzi et P. Ienne, " Mobile robot miniaturization: A tool robotique. Plusieurs événements spectaculaires et médiatisés nous donnent un avant-goût de
for investigation in control algorithms " In proceedings of the third l’avenir :
International Symposium on experimental Robotics, Kyoto, Japan, 1993.
Le 4 juillet 1997, le robot Pathfinder de la NASA, pose ses roues là où aucun homme
[Parker 94] L. Parker, "An architecture for fault tolerant, cooperative control of n’a jamais mis le pied. Ce robot réalisera avec brio une mission de trois mois sur
heterogeneous mobile robots", Proc. Of the 1994 International Mars. Pathfinder reste aujourd’hui encore un des robots mobiles les plus célèbres au
Conference on Intelligent Robots and Systems, Munich, Germany, p. monde.
776-783, 1994. Après l’effroyable catastrophe du 11 septembre 2001, des robots téléopérés se sont
engouffrés dans les décombres du World Trade Center avec l’espoir de retrouver des
[Parker 99] L. Parker, "Adaptative heterogeneous multi-robot teams", survivants.
Neurocomputing, special issue of NEURAP’98: Neural networks and Le 7 septembre 2001, une opération chirurgicale consistant à enlever une vésicule
their applications, 28, p.75-92, 1999. biliaire a été réalisée. Le chirurgien se trouvait à New-York et le patient à Paris. Cette
opération a été possible grâce à un robot qui a pu être téléopéré à travers l’atlantique.
[Rongier 01] P. Rongier et P. Lucidarme, "A Sizing Method for a Multi-Robot Voilà précisément un magnifique exemple où la machine assiste le geste humain, mais
System", International Conference On Intelligent Robotic Systems, Maui, où en aucun cas elle ne remplace les décisions du chirurgien.
Hawaii, p 387-392, 2001. En mai 1997, l’ordinateur Deep-Blue remporte un match contre l’un des meilleurs
joueurs d’échecs que l’humanité ait connu : Garri Kasparov. Cette expérience montre
[Rosenblatt 58] F. Rosenblatt, "The Perceptron : a Probabilistic Model for Information les capacités de la machine à dépasser les facultés de ses créateurs et de l’homme sur
Storage and Organisation in the Brain", Psychological Review, p. 386- un problème qui est souvent considéré comme l’incarnation même du jeu intelligent.
408, 1958. Le robot chien AIBO a été vendu à plus de 100 000 exemplaires à travers le monde
par la société Sony. L’engouement mondial et commercial pour la robotique ne cesse
[Rumelhart 86] D.E. Rumelhart and J.L. Mc Clelland, "Parallel Distributed Processing", de croître: de plus en plus de robots sont disponibles dans le commerce comme par
The MIT Press, vol. 1 et 2, Cambridge, 1986. exemple pour tondre la pelouse ou encore nettoyer le sol.
D’un aspect plus ludique, depuis quelques années, les concours de robotique se
[Simonin 00a] O. Simonin, A. Liégeois and P. Rongier, " An Architecture for Reactive multiplient avec comme principal événement la coupe du monde de robotique
Cooperation of Mobile Distributed Robots ", 5th International RoboCup qui déchaîne les passions.
Symposium on Distributed Autonomous Robotic Systems 4 ,Knoxville,
Enfin, un privilège qui était jusqu’alors réservé aux dieux est en passe de devenir
TN Springer, USA, p. 35-44, 2000. accessible : créer une créature à son image. Les sociétés Sony, Honda et l’AIST ont
présenté leurs robots humanoïdes respectivement appelés SDR, ASIMO et HRP-2.
[Simonin 00b] O. Simonin et J. Ferber " Modeling self satisfaction and altruism to
handle action selection and reactive cooperation ", 6th international Tous ces événements, pris séparément, restent des faits divers, qui feront au mieux la
Conference on the Simulation of Adaptive Behavior, volume2, p. 314- première page du journal. Mais pris dans leur globalité, ils montrent bien que la robotique
323, 2000.
traverse une période charnière pour entamer une nouvelle ère.
La robotique est une matière pluridisciplinaire au carrefour de la mécanique, de
[Simonin 01] O. Simonin, "Le modèle satisfaction-altruisme : coopération et résolution l’électronique, de l’informatique, des mathématiques mais aussi d’autres disciplines comme
de conflits entre agents situés réactifs, application à la robotique" , Thèse les neurosciences ou la psychologie, sans parler du domaine d’application qui s'étend de la
de Doctorat en Informatique , LIRMM UM2, soutenue le 20 décembre microchirurgie à l’exploration spatiale. Les avancées technologiques dans toutes ces
2001.
disciplines ouvrent aujourd’hui aux chercheurs de nouvelles perspectives et des centaines de
voies de recherche à explorer.

111 16
 [Steels 89] L. Steels, " Cooperation between distributed agents Through Self-
organisation ", Journal on robotics and autonomous systems, North
Holland, Amsterdam. 1989.

1
[Steels 91] L. Steels, " Towards a Theory of Emergent Functionnality ", From
animal to animats, MIT Press, p. 451, 1991.

[Szepesvari 97] C. Szepsvari, "The assymptotic convergence-Rate of Q-learning", in

Proc. Neural Information Processing Systems, 1997.

[Astrom 95] K J. Astrom et B. Wittenmark, "Adaptive Control ", Addison-Wesley,

Deuxième Édition,1995.
1. Introduction générale [Tesauro 94] G.J. Tesauro, " TD-Gammon, a self-teaching backgammon program,
achieves master-level play", Neural computation, 6(2), p.215-219.

[Watkins 89] C.J.C.H Watkins, "Learning from delayed rewards", thèse de doctorat,
Cambridge University, 1989.

[Winfield 00] A. Winfield et O. Holland "The application of wireless local area

network technology to the control of mobile robots", Microprocessors
and Microsystems, 23/10, p 597-607, 2000.

___________________________________________________________________________ [Zapata 92] R. Zapata, P. Lepinay, C. Novalés and P. Déplanques, "Reactive

behaviors of fast mobile robots in unstructured environments : sensored
Quand j’avais une dizaine d’années et que cette perpétuelle question m’était adressée, based control and neural networks." SAB, December 1992.
un dialogue similaire s’instaurait à chaque fois :

- "Qu’est ce que tu veux faire plus tard ?

- Des robots.
- Ca c’est l’avenir …"

Mais ces robots, qui semblait présager tant de bonnes choses pour l’avenir, font-ils
partie de notre quotidien ? Nous soulagent-ils des tâches fastidieuses et répétitives ? Sont-ils
nos fidèles compagnons prêts à se donner corps et âmes (si tant est qu'ils en aient une) afin
d’achever la mission pour laquelle ils ont été programmés ?

Même si je ne croise pas encore de robots humanoïdes dans les rues quand je fais mes
courses, je dirais que la robotique a réussi une partie du défi qui lui était lancé au milieu du
siècle passé. En premier lieu dans l’industrie : les machines automatisées, omniprésentes sur
les chaînes de fabrication, assistent (selon le patron), remplacent (selon les délégués
syndicaux) les ouvriers dans des tâches répétitives et fastidieuses. Plus important encore, le
personnel a été partiellement écarté de certaines tâches pouvant nuire à la santé, comme par
exemple la manipulation de produits toxiques.

Les robots se sont également immiscés dans la vie de tous les jours: ils n’ont pas la
forme que leur avaient prêté les auteurs de sciences-fiction quelques années auparavant, mais
ils remplissent fidèlement la tâche pour laquelle ils ont été conçus. Les lave-vaisselles, les
lave-linge et d’autre machines nous assistent fidèlement dans les tâches répétitives de notre
quotidien.

15 112
Annexe A : Dynamique du manipulateur
M3

___________________________________________________________________________

Le vecteur vitesse angulaire i d'un corps i peut être déterminé simplement grâce à la
structure plan du bras et des poulies :

0  q i S1  0 
1 0 i  q i C1  i q  i 2,3,4 (A. 1)
repère fixe   repère fixe  repère ( i )  i 
q1   q1   q1 

En utilisant la formule itérative du calcul du modèle dynamique direct on en déduit les

vitesses:


O 
O i li (A. 2)
i 1 i

Ou représente le produit en croix des vecteurs.

Les équations de la dynamique donne la relation entre les positions, les vitesses, les
accélérations, les forces et les couples d'un mécanisme comportant plusieurs corps. D'un point
de vue purement automatique, les équations de Lagrange ou de Kane serait suffisante pour
déterminer le meilleur couple moteur à appliquer afin de réaliser un mouvement donné.
Malgré cela, nous nous sommes également intéressé à la marge de stabilité du manipulateur et
au condition de glissement, c'est-à-dire à l'ensemble des phénomènes qui mettent en jeu les
forces interne et les réactions du sol sur le robot. Pour cette raison, nous nous sommes basés
sur le formalisme de Newton-Euler. Contrairement à la cinématique, la dynamique demande
d'utiliser la formule itérative du calcul dynamique inverse, en allant de l'organe terminal
jusqu'à la base. Nous allons maintenant montrer mathématiquement ce qui peut être deviné
intuitivement grâce aux particularités de ce mécanisme : Un corps i est uniquement chargé par
les masses des corps qui lui succèdent, du point de vue Oi+1.

113 14
Figure 38 : Evolution de chacun des paramètres de la récompense au fil des générations
(D'après [Floreano 94]) ................................................................................................ 73 Les paramètres du corps i sont :
Figure 39 : Un exemple de chaîne chromosomique .............................................................. 75
Figure 40 : Détail du protocole de communication. .............................................................. 77 Sa masse mi
Figure 41 : Capture d’écran du simulateur avec des obstacles circulaires.............................. 78 Le vecteur di situé au centre de gravité Gi: d i Oi G i
Figure 42 : Photo d’une expérimentation.............................................................................. 79
Figure 43 : Exploration de l’environnement ......................................................................... 80 La matrice d'inertie Ii. Ses composantes dans le repère local sont notées (Ii)x, (Ii)y, (Ii)z,
Figure 44 : Temps de convergence en fonction de la taille de la population.......................... 80 (Ii)xy etc.
Figure 45 : Le contrôleur neuronal ....................................................................................... 85
Figure 46 : Disposition des capteurs et actionneurs .............................................................. 86 La gravité (g) sera considérée comme verticale (le long de l'axe z). Bien sur, les trois
Figure 47 : Recherche du maximum d’une fonction ............................................................. 86 composantes doivent être considérées pour des application en terrain accidenté.
Figure 48 : Evolution de la température en fonction du temps .............................................. 87
Figure 49 : Evolution de la meilleure stratégie connue ......................................................... 88 Les équations de la dynamiques sont obtenues de façon itératives, en commençant depuis
Figure 50 : Résultats d'une expérimentation ......................................................................... 89 l'organe terminal (body 4) jusqu'à la base (body 1), selon [Luh 80].
Figure 51 : Evolution de la température en fonction de la récompense du meilleur
comportement connu .................................................................................................... 90 Fi 
mi (O 
 i di  i ( i d i )) (A. 3)
i
Figure 52 : Résultats d’une expérience ................................................................................. 91
Figure 53 : Influence de chaque capteur sur le comportement global .................................... 92 Mi Ii 
i 
 i (I i  i ) mi d i O (A. 4)
i
Figure 54 : Comparaison des différentes méthodes............................................................... 93
Figure 55 : Capture d’écran du simulateur utilisé pour la Robocup....................................... 94
Figure 56 : Architecture du réseau RBF utilisé ..................................................................... 95 Le vecteur Fi est la somme des forces agissant sur le corps i comme s'il était isolé. Mi
Figure 57 : Gaussienne obtenue en utilisant un polynôme d’ordre 4 ..................................... 96 est le couple résultant sur le corps i, calculé en Oi. Le point représente le produit de
Figure 58 : Modélisation de la Q-valeur ............................................................................... 97 matrice. La première équation calculée au centre de gravité Gi peut remplacer l'équation A.3 :
Figure 59 : Position des centres............................................................................................ 98
Figure 60 : Modélisation de l’Action 1 optimale en fonction de l’état de l’agent .................. 99 FGi 
mi G (A. 5)
i
Figure 61 : Modélisation de l’Action 2 optimale en fonction de l’état de l’agent .................. 99
Figure 62 : Performance des méthodes évolutionnistes....................................................... 104
Figure 63 : Performance du recuit simulé ........................................................................... 104 Les équations détaillées seront développées afin de démontrer que ce robot M3 facilite
Figure 64 : Performance de l'apprentissage par renforcement ............................................. 105 les calcul du modèle dynamique, l'asservissement et les tests de stabilité. Les équation A.3 et
Figure 65 : Paramètres et forces externes relative au corps 4 .............................................. 115 A.4 sont exprimées dans le repère local (Oi, xi, yi, zi).
Figure 66 : Paramètres et forces relatifs au corps 3............................................................. 117
Figure 67 : Compensation du poids du corps 3 ................................................................... 118
Figure 68 : Paramètres et forces relatifs au corps 2............................................................. 118
Figure 69 : Repères et paramètre de la base mobile. ........................................................... 120

Tableau 1 : Codage des chiffres dans la chaîne chromosomique ........................................... 46 Considérons que l'organe terminal puisse être sujet à une force Fe et un couple
Tableau 2 : Codage des opérateurs dans la chaîne chromosomique....................................... 46 extérieurs Me au point de référence O5. Tous les composants des vecteurs et matrices sont
Tableau 3 : Exemple de chaîne chromosomique pour le problème du juste chiffre................ 46 exprimés dans le repère local (O4, x4, y4, z4) car les actions externes sont généralement liées
Tableau 4 : Différents états du système ................................................................................ 75 soit à la gravité, soit à une source externe solidaire du sol. La force F34 et le moment M34
Tableau 5 : Jeu d’actions possibles....................................................................................... 75 exercés par le corps 3 sur le corps 4 sont schématisés sur la Figure 65. Le couple M14 agit
Tableau 6 : Séquence chromosomique optimale ................................................................... 79 directement sur le corps au niveau de l'axe de rotation O4y4.

Algorithme 1 : Apprentissage neuronal d’un réseau sans couche cachée............................... 36 F34 Fe 

m4 ((O g) 
 4 d4  4 ( 4 d 4 )) (A. 6)
4
Algorithme 2 : Algorithme de rétropropagation du gradient ................................................. 37
Algorithme 3 : Algorithme de la programmation dynamique ................................................ 41 M 34 M 14 Me Fe l 4 
m4 d 4 (O 4 g) I 4 
4  4 (I 4  4 ) (A. 7)
Algorithme 4 : Algorithme du Q-Learning ........................................................................... 43
Algorithme 5 : Principe général des algorithmes évolutionnistes (D'après [Mitchell 97])...... 45
Algorithme 6 : Algorithme utilisé pour entraîner le réseau ................................................... 87
Algorithme 7 : Algorithme adaptatif utilisé pour entraîner le réseau ..................................... 90

13 114
 ___________________________________________________________________________

Figure 1 : Simulation pour chacune des tâches (D'après [Arkin 92])..................................... 21

Figure 2 : Diagramme des " Silly Robot " (D'après [Drogoul 92]) ....................................... 22
Figure 3 : Diagramme des Chain-Making (D'après [Drogoul 92])........................................ 24
Figure 4 : Architecture traditionnelle de décomposition du programme de contrôle du robot en
différents modules de fonctionnement (D'après [Brooks 86])........................................ 24
Figure 5 : Décomposition basée sur le comportement d'accomplissement de tâches (D'après
[Brooks 86])................................................................................................................. 25
Figure 6 : Un module de l'architecture forçage / inhibition ................................................... 25
Figure 65 : Paramètres et forces externes relative au corps 4
Figure 7 : Un exemple d’architecture à base de combinaison vectorielle............................... 26
Figure 8 : Architecture satisfaction / altruisme (D'après [Simonin 00]) ................................. 26
L'équation du vecteur force (A.6) donne en premier lieu : Figure 9 : Les quatre robots IS Robotics R2e utilisés par D. Goldberg et M.J. Mataric (D'après
[Goldberg 99]) ............................................................................................................. 28
Figure 10 : Schéma général d'un neurone artificiel ............................................................... 34
( F34 ) x ( Fe ) x m4 ( xO4 q4 ( ( d 4 ) x S 4 ( d 4 ) z C 4 ) (q12 q 42 )((d 4 ) x C 4 (d 4 ) z S 4 )) Figure 11 : Fonction de sortie de type seuil .......................................................................... 35
 Figure 12 : Fonction de sortie bornée ................................................................................... 35
( F34 ) y ( Fe ) y m 4 ( yO4 q1 ((d 4 ) x C 4 (d 4 ) z S 4 ) q1 q 4 ( (d 4 ) x S 4 ( d 4 ) z C 4 )) (A. 8)
 Figure 13 : Représentation du réseau dans l’espace des entrées ............................................ 36
( F34 ) z ( Fe ) z m4 ( zO4 g q4 ((d 4 ) x C 4 ( d 4 ) z S 4 ) q 42 ( ( d 4 ) x S 4 (d 4 ) z C 4 )) Figure 14 : Exemple de réseau RBF ..................................................................................... 38
Figure 15 : Fonction à estimer et sortie de chaque neurone de la couche cachée. .................. 38
Remarquons que les mouvements des segments 2 et 3 n'induisent pas de force Figure 16 : Exemple de fonction radiale dans ²................................................................. 39
centrifuge sur le corps 4 grâce aux mécanisme de poulies remplaçant un double Figure 17 : Système d'apprentissage par renforcement.......................................................... 40
parallélogramme. Comme les équations sont écrites dans le repère de référence (O4, x4, y4, z4), Figure 18 : Exemple de processus markovien....................................................................... 41
la matrice d'inertie du corps 4 doit être calculée dans ce repère. Figure 19 : V* après cinq cycles d'apprentissage................................................................... 42
Considérons Figure 20 : Matrice Q pour chacune des actions. .................................................................. 44
Figure 21 : Opérateurs de croisement sur des chaînes binaires.............................................. 47
 I x4 0 I xz 4  Figure 22 : Exemple de croisement uniforme pour le problème du juste chiffre .................... 48
(I 4 ) 4  0 I y4 0  (A. 9) Figure 23 : Exemple de mutation.......................................................................................... 48

 I xz 4 Figure 24 : Evolution du meilleur individu au fil des générations ......................................... 48
0 I 4 z 
Figure 25 : Détails du robot Type 1 ...................................................................................... 55
Figure 26 : Réponse des capteurs en fonction de la structure de l’obstacle............................ 56
la matrice d'inertie quand q4=0. Cela devient Figure 27 : Notre manipulateur mobile miniature M3 ........................................................... 58
Figure 28 : La cinématique du bras ...................................................................................... 59
 C 42 ( I x 4 ( I xload ) 4 ) C 4 S 4 (I z 4 ( I xload ) 4 ) 
( I zload ) 4 ) I x 4 Figure 29 : Disposition des différents repères....................................................................... 60
 0 2 2  Figure 30 : Le système de vision stéréoscopique BOP.......................................................... 63
 S 42 ( I z 4 ( I zload ) 4 ) (C 4 S )( I xz 4 ( I xzload ) 4 )
4  Figure 31 : Organe terminal ................................................................................................. 64
I4  0 I y4 ( I yload ) 4 0  Figure 32 : Schéma global de notre système de vision BOP.................................................. 64
C S ( I ( I ) ) I ( I ) ) C 4 ( I z 4 ( I zload ) 4 ) S 4 ( I x 4 ( I xload ) 4 ) 
2 2
Figure 33 : Exemple de positions d’acquisition .................................................................... 65
 4 4 z4 zload 4 x4 xload 4
0 Figure 34 : Disposition des différents points et repères......................................................... 66
 (C 4 S 4 )( I xz 4 ( I xzload ) 4 ) 
2 2
2C 4 S 4 ( I xz 4 ( I xzload ) 4 )
Figure 35 : Le robot mobile Khepera.................................................................................... 71
Figure 36 : L’environnement de l’expérience (D'après [Floreano 94]) .................................. 71
Figure 37 : Performance moyenne de la population et du meilleur individu en fonction des
quand le moment dû à la charge, le produit d'inertie et la rotation q4 ont été ajoutées générations (D'après [Floreano 94]).............................................................................. 72

115 12
 Pour simplifier, nous noterons :

 (I 4 ) x 0 ( I 4 ) xz 
I4  0 (I 4 ) y 0  (A. 10)

( I 4 ) xz 0 ( I 4 ) z 

L'équation A.6 donne :

( M 34 ) x ( M e ) x ( S 4 (l 4 ) z C 4 (l 4 ) z )( Fe ) y m4 yO4 ( S 4 (d 4 ) z C 4 (d 4 ) z )

 ( I 4 ) xz q1 (( I 4 ) xz ( I 4 ) x ) q1 q 4

( M 34 ) y 0

( M 14 ) y (M e ) y ( S 4 (l 4 ) z C 4 (l 4 ) z )( Fe ) x ( S 4 (l 4 ) z C 4 (l 4 ) z )( Fe ) z
 (A. 11)
 m 4 ( x O4 ( ( d 4 ) x S 4 ( d 4 ' ) z C 4 )

 ( z g )(( d 4 ) x C 4 ( d 4 ) z S 4 )) ( I 4 ) y q4 ( I 4 ) xz q12
 O4

( M 34 ) z ( M e ) z (C 4 (l 4 ) x S 4 (l 4 ) z )( Fe ) y m4 yO4 ((d 4 ) x C 4 ( d 4 ) z S 4 )

 ( I 4 ) zz q1 ( I 4 ) xz q1 q 4

Aucune composante du couple (M34)y n'est transmise du corps 3 vers le corps 4, mais
le mécanisme de poulies et de courroies transmettent (M14)y depuis l'actionneur fixé sur la
base.

Les équations A.3 et A.4 donnent :

F23 
m3 (O g 
 3 d3  3 ( 3 d 3 )) F34 Fspring ( 3) (A. 12)
3

M 23 I3 
3 
 3 ( I 3  3 ) m 3 d 3 (O g ) l 3 F34 M 34
3
(A. 13)
l spring (3 ) Fspring ( 3 )

On en déduit les composantes suivantes, qui peuvent être facilement calculées puisque
tous les repères mobiles sont parallèles :

( F23 ) x m3 ( xO3 q3 d 3 S 3 (q12 q 32 )d 3 S 3 ) ( F34 ) x ( Fspring ( 3) ) x


( F23 ) y m3 ( yO3 q1 d 3C 3 q1 q 3 d 3 S 3 ) ( F34 ) y (A. 14)
 2
( F23 ) z m3 ( zO3 g q3 d 3 C3 q d 3 S 3 ) ( F34 ) z
3 ( Fspring ( 3) ) z

11 116
 5.3.2 Description de la tâche ............................................................................................ 74
5.3.3 Les opérateurs ......................................................................................................... 75
( M 23 ) x ( I 3 ) xz q1 ((I 3 ) z ( I 3 ) x )q1 q 3 m3 d 3 S 3 yO3 l 3 S 3 ( F34 ) y ( M 34 ) x 5.3.4 Protocole de communication.................................................................................... 77

( M 23 ) y 0 5.3.5 Résultats.................................................................................................................. 78
( M ) 2
 13 y ( I 3 ) y q3 ( I 3 ) xz q1 m3 d 3 ( S 3 xO3 C 3 ( zO3 g )) 5.4 Conclusion .................................................................................................................... 81
 (A. 15)
 l 3 ( S 3 ( F34 ) x C3 ( F34 ) y ) ( M 34 ) y ( (l spring ( 3) ) x S 3 (l spring ( 3) ) z C 3 )( Fspring (3) ) x
 ((l
spring ( 3 ) ) x C 3 (l spring ( 3) ) z S 3 )( Fspring (3) ) z

( M 23 ) z ( I 3 ) z q1 ( I 3 ) xz q1q 3 m3 d 3 C3 yO l3 C 3 ( F34 ) y ( M 34 ) z
 3

6.1 Introduction.................................................................................................................. 83
où les inerties sont : 6.2 Recuit simulé ................................................................................................................ 84
6.2.1 Introduction............................................................................................................. 84
 C32 I x 3 S 32 I z 3 6.2.1 Structure du contrôleur ............................................................................................ 85
 (I 3 ) x 0 ( I 3 ) xz  0 S 3 C3 ( I z 3 I x 3 )
 0   6.2.2 Approche classique.................................................................................................. 86
I3  (I 3 ) y 0   0 I y3 0  (A. 16) 6.2.3 Résultats expérimentaux I........................................................................................ 88
( I 3 ) xz 0 ( I 3 ) z   S 3 C3 ( I z 3 I x 3 ) 0 S 32 I x 3 C 3 I z 3 
2
6.2.4 Approche adaptative................................................................................................ 89

6.2.5 Résultats expérimentaux II ...................................................................................... 90
6.2.6 Conclusion .............................................................................................................. 92

6.3 Extension de l’apprentissage par renforcement au domaine continu ........................ 93

6.3.1 Introduction............................................................................................................. 93
6.3.2 Approximation de la Q-fonction .............................................................................. 94
6.3.3 Recherche du maximum .......................................................................................... 96
6.3.4 Résultats expérimentaux 1 ....................................................................................... 97
6.3.4 Résultats expérimentaux 2 ....................................................................................... 98
6.4 Conclusion ............................................................................................................... 100

Figure 66 : Paramètres et forces relatifs au corps 3

A.1. Vitesses angulaire ..................................................................................................... 113

A.2. Equations de la dynamique ...................................................................................... 113

A.2.1. Corps 4 (l'organe terminal et la charge)................................................................ 114
A.2.2. Corps 3 (l'avant bras) et 2 (le bras)....................................................................... 116
A.3.3. Corps 1 (la base mobile) ...................................................................................... 119

117 10
 3.2.5 Conclusion .............................................................................................................. 39 La raideur et les points de fixations du ressort "spring(3)" ont été calculé de façon à
compenser au maximum le poids du corps 3 (à G3) et du corps 4 (à O4). La Figure 67 montre
3.3 L'apprentissage par renforcement .............................................................................. 39 les couples relatifs à q3.
3.3.1 Introduction............................................................................................................. 39
3.3.2 Les processus markoviens ....................................................................................... 40
3.3.3 La programmation dynamique ................................................................................. 41
3.3.4 Le Q-learning .......................................................................................................... 43
3.3.5 Conclusion .............................................................................................................. 44

3.4 Les algorithmes évolutionnistes ................................................................................... 45

3.4.1 Introduction............................................................................................................. 45
3.4.2 Les opérateurs génétiques........................................................................................ 46
3.4.4 Conclusion .............................................................................................................. 49

3.5 L'estimation de la performance ................................................................................... 49

3.6 Conclusion .................................................................................................................... 51

4.1 Introduction.................................................................................................................. 53

4.2 Le robot Type 1 ............................................................................................................ 54

Figure 67 : Compensation du poids du corps 3
4.2.2 Description matérielle.............................................................................................. 55
4.2.3 Description du logiciel............................................................................................. 57

4.3 Le manipulateur mobile miniature(M3) ...................................................................... 58

4.3.1 Introduction............................................................................................................. 58
4.3.2 Repères de référence................................................................................................ 59 Les forces et les couples appliqués sur le corps 2 sont définis sur la Figure 68.
4.3.4 Positions et orientations........................................................................................... 60

4.4 Bird Of Prey (BOP)...................................................................................................... 62

4.4.1 Introduction............................................................................................................. 62
4.4.2 Description générale................................................................................................ 63
4.4.3 Positions et orientations........................................................................................... 65

4.5 Conclusion .................................................................................................................... 67

5.1 Introduction.................................................................................................................. 69

5.2 Un algorithme évolutionniste supervisé....................................................................... 70

5.2.1 Introduction............................................................................................................. 70
Figure 68 : Paramètres et forces relatifs au corps 2
5.2.2 Description de la tâche ............................................................................................ 70
5.2.3 Résultats.................................................................................................................. 72
5.2.4 Conclusion .............................................................................................................. 73

5.3 Un algorithme évolutionniste distribué ....................................................................... 74

5.3.1 Introduction............................................................................................................. 74

9 118
Les équations A.3 et A.4 donnent :

F12 
m 2 (O g 
 2 d2  2 ( 2 d 2 )) F23 Fspring ( 2 ) (A. 17)
2

M12 I2 
2 
 2 (I 2  2 ) m2 d 2 (O g) l 2 F23 M 23
2
(A. 18)
l spring ( 2 ) Fspring ( 2 )

On en déduit les composantes suivantes :

( F12 ) x m2 ( xO3 q2 d 2 S 2 (q12 q 22 ) d 2 S 2 ) ( F23 ) x ( Fspring ( 2 ) ) x


( F12 ) y m2 ( yO3 q1 d 2 C 2 q1 q 2 d 2 S 2 ) ( F23 ) y (A. 19)
Remerciements................................................................................................................... 5
 2
( F12 ) z m 2 ( zO3 g q2 d 2 C 2 q d 2 S 2 ) ( F23 ) z
2 ( Fspring ( 2 ) ) z Table des matières.............................................................................................................. 8
Table des figures, tableaux et algorithmes ........................................................................ 12

( M 12 ) x ( I 2 ) xz q1 (( I 2 ) z ( I 2 ) x )q1 q 2 m2 d 2 S 2 yO3 l 2 S 2 ( F23 ) y (M 23 ) x


( M 23 ) y 0
( M ) 2
 12 y ( I 2 ) y q2 ( I 2 ) xz q1 m2 d 2 ( S 2 xO3 C 2 ( zO3 g ))
 (A. 20) 2.1 Introduction.................................................................................................................. 19
 l 2 ( S 2 ( F23 ) x C2 ( F23 ) y ) ( M 23 ) y ( (l spring ( 2 ) ) x S 2 (l spring ( 2) ) z C 2 )( Fspring ( 2) ) x
 ((l 2.2 Définition ...................................................................................................................... 20
spring ( 2 ) ) x C 2 (l spring ( 2 ) ) z S 2 )( Fspring ( 2) ) z

( M 12 ) z ( I 2 ) z q1 ( I 2 ) xz q1 q 2 m 2 d 2 C 2 yO l 2 C 2 ( F23 ) y ( M 23 ) z
 3 2.3 Les tâches génériques................................................................................................... 21

2.4 L’approche réactive ..................................................................................................... 22

où les inertie sont :
2.4.1 Introduction............................................................................................................. 22
 (I 2 ) x 0 ( I 2 ) xz   C 22 I x 2 S 22 I z 2 0 S 2 C3 ( I z 2 I x 2 ) 2.4.2 Silly Robot .............................................................................................................. 22
 0  
0 
2.4.3 Tom Thumb ............................................................................................................ 23
I2  (I 2 ) y  0 I 0  (A. 21)
y2
2.4.4 Chain-Making Robot ............................................................................................... 23
( I 2 ) xz 0 ( I 2 ) z  S 2C 2 ( I z 2 I x 2 ) 0 S 22 I x 2 C 2 I z 2 
2
2.4.5 Systèmes réactifs et cognitifs................................................................................... 24


2.5 Les communications dans les systèmes multi-agents .................................................. 27

2.5.1 Introduction............................................................................................................. 27
Comme pour le corps 3, la raideur et la fixation du ressort "spring(2)" ont été calculer 2.5.2 Les protocoles de communication supervisé ............................................................ 27
de façon à compenser le poids du corps 2 (à G2) et des corps 3 et 4 (à O3). Les résultats sont 2.5.3 Les protocoles de communication distribué ............................................................. 28
proches de ceux de l'avant bras.
2.6 Conclusion .................................................................................................................... 29

3.1 Introduction.................................................................................................................. 31

Les différentes forces qui sont appliquées sur la base sont isolées : force inertiel, 3.2 Les réseaux neuronaux................................................................................................. 33
moment d'inertie, poids, interactions depuis le manipulateur, force de traction et réaction du 3.2.1 Introduction et historique......................................................................................... 33
sol. L'influence gyroscopique des moteurs est négligée. La géométrie et les forces sont 3.2.2 Notation .................................................................................................................. 34
illustrées sur la Figure 69. 3.2.3 La rétropropagation du gradient............................................................................... 35
3.2.4 Les réseaux à fonctions radiales............................................................................... 37

119 8
 Figure 69 : Repères et paramètre de la base mobile.

Les équations sont données par :

  1
m1 X G1 (( F21 ) x R ( M r M l ))C1

m Y 1
 1 G1 (( F21 ) y ( M r M l )) S1
 R (A. 22)
 r l d
( I ) z q1 R ( M 21 ) z (M r M l )
 2 d R
 ( F21 ) x ((l1 ) y (d 1 ) y ) ( F21 ) y ((l1 ) x ( d1 ) x )

120
 Je remercie Philippe Rongier pour m'avoir initié au monde de la recherche et à celui des
systèmes multi-agents. Egalement Geovani Borges, auteur du célèbre "Pourquoi manger, pourquoi
Annexe B : Schéma électronique du robot dormir".

Type 1 C'est parce que la coutume m'y oblige sinon je m'en serais passé : je remercie l'ensemble des
thésards que j'ai du supporter pendant ces quatre longues années. Je commencerais par le trio des cinq
mousquetaires de l'amour : Sébastien, Benoit, Micaël et Fabien pour avoir partagé tant de moments
intenses, qu'ils aient été festifs, drôles, culinaires, romantiques ou … surtout festifs ! Mais aussi tous
les autres, dans le désordre : Gilles (pour ta bonne humeur et ta gentillesse), Pierre ( … qui roule
n'amasse pas mousse, moi aussi j'ai mangé un clown à midi  ), Mezziane (bijour jy sui li nouvo
pilote di l'avion), les Wany-roboticiens (pour le matériel et les conseils ) et bien sûr tout ceux que
j'oublie, si vous n'êtes pas dans cette liste, mettez votre nom ici avec un commentaire :
___________________________________________________________________________
Mon nom : _______________________

Le commentaire : _________________________________________________________

Bien sur, il me reste à remercier toute la bande de l'ancr et des Porteurs-Libres. Tout cela est
de votre faute : si un beau jour d'hiver 1999, vous ne m'aviez pas suivi dans cette folle aventure qu'est
la coupe de France de robotique, je n'en serai pas là aujourd'hui. Même si nous ne sommes jamais
rentrés vainqueur de la Ferté-Bernard, notre victoire est ailleurs.

Comment pourrais-je oublier celle qui a accompagné mon cœur ces huit derniers mois, celle
qui a supporté la rédaction, la soutenance, le départ au Japon, qui sait me réconforter quand rien ne va
plus. Celle qui me fait dire que les neurosciences sont passionnantes et qui m’accorde des cours
particuliers de biologie … Mille baisés, Laëtitia, pour tous ces merveilleux moments que tu m’as
offerts pendant cette période parfois difficile.

Lasts but not least … Pour terminer ces remerciements, il reste deux personnes que je souhaite
remercier avec une très grande sincérité : mes parents.

Maman : même si la vie n'a pas toujours été facile dans le foyer familial, tu as su parfois te
sacrifier pour nous offrir une vie meilleure. Et grâce à toi, je profite aujourd'hui du meilleur de la vie.
J'aimerais pouvoir te rendre tout l'amour et la dévotion que tu nous as offert, mais une vie entière n'y
suffirait pas. J'espère au moins que cette thèse y contribuera en partie.

Papa : pour avoir écrit une thèse traitant de l'apprentissage, je suis en mesure de vous
expliquer une de mes convictions : chacun de nous naît avec un patrimoine génétique qui va
partiellement régir notre apparence physique mais aussi une partie de notre caractère et de notre
comportement. Mais cette structure de base est plastique, c'est à dire qu'elle va évoluer au fils du
temps. Cette évolution va dépendre de stimulations extérieures et de leurs associations à des
récompenses ou à des expériences traumatisantes. Pour résumer, rien n'est joué à la naissance et
chacun dispose de sa vie. Un vrai père doit offrir à la fois le patrimoine génétique et l'éducation qui va
avec. Mais vous, Guy, vous avez fait encore mieux : vous avez accepté le rôle ingrat de l'éducateur
sans pour autant pouvoir revendiquer une quelconque paternité, d'autant plus que le patrimoine de base
n'était pas merveilleux. Alors sachez Guy, que je vous ai toujours considéré comme mon père et qu'il
vous revient tous les honneurs et la fierté qu'un père peut avoir quand il voit sont fils devenir docteur.

121
 Je voudrais, avant toute chose, exprimer ma plus grande reconnaissance à Alain Liégeois, qui
était l'encadrant initial de cette thèse et qui nous a malheureusement quitté en mars 2003. Il a su diriger
cette thèse avec diplomatie efficacité et rigueur tout en me laissant libre dans mes choix.

Les travaux présentés dans ce mémoire ont été effectués au sein du département de robotique
du Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier (LIRMM). Aussi,
je tiens à remercier tout d'abord Messieurs Gaston Cambon et Michel Habib, directeurs successifs du
LIRMM, pour m'avoir accueilli au sein du laboratoire durant ma thèse et mon DEA.

Je tiens aussi à remercier Jacques Ferber pour avoir accepté de présider mon jury de thèse,
mais également pour avoir suivi mes travaux depuis leurs débuts. Les discussions que nous avons eu
m'ont permis d'améliorer l'ensemble de mon travail et surtout de diriger mes recherches vers de
meilleures voies.

Je tiens également à exprimer ma gratitude à Dominique Duhaut pour avoir accepter d'être
rapporteur de ce travail. L'intérêt qu'il a porté à la lecture du manuscrit me touche particulièrement. Et
même si les circonstances ne s'y prêtent pas actuellement, je ne perd pas espoir de pouvoir un jour
collaborer avec lui.

Je remercie Rachid Alami d'avoir accepté de m'accorder une partie de son temps précieux pour
être rapporteur de cette thèse. Ses questions et remarques ont été pour moi une grande source de
réflexion. J'ai grandement apprécié sa gentillesse au cours de nos différentes rencontres, mais aussi le
jour de ma soutenance.

Je voudrais aussi remercier Jean-Louis Vercher pour la collaboration que nous avons menée
depuis quelques années. Il a su répondre avec pédagogie à mes nombreuses questions sur le vivant.
J'espère que l'absence d'Alain n'entravera en rien la collaboration entre neuro-scientifiques et
roboticiens, et qu'il restera toujours aussi généreux en explications et anecdotes sur ses connaissances
du vivant.

Je voudrais remercier René Zapata pour avoir accepté de prendre la direction de cette thèse
après la mort d'Alain. Il a su me conseiller et me guider avec sérieux, efficacité et humour.

Que Etienne Dombre reçoive toute ma reconnaissance pour ses remarques pertinentes et
constructives, ses conseils avisés et son soutien. Il m'a fallu du temps pour découvrir que derrière ces
moustaches et ce visage rigoureux, parfois sévère, il y a un homme au grand cœur.

J'adresse toute ma sympathie aux permanents du département robotique, avec une mention
particulière à certain d'entre eux : François Pierrot (qui a réussit à nous convaincre de partir de l'autre
côté de la terre), André Crosnier (pour sa bonne humeur contagieuse), Philippe Poignet (pour la balade
en voilier …) et Oliver Strauss (pour les bonnes adresses de petits restaurants romantiques).

122
123
à Alain …

124
125
 ACADEMIE DE MONTPELLIER

UNIVERSITE MONTPELLIER II
- SCIENCES ET TECHNIQUES DU LANGUEDOC -

THESE

Pour obtenir le grade de

DOCTEUR DE L’UNIVERSITE MONTPELLIER II

Discipline : Génie Informatique, Automatique et Traitement du Signal

Formation Doctorale : Systèmes Automatiques et Microélectroniques

Ecole Doctorale : Information, Structures et Systèmes

Présentée et soutenue publiquement

par

Philippe LUCIDARME
Le 7 novembre 2003

Titre :

Apprentissage et adaptation
pour des ensembles de robots
réactifs coopérants

JURY
Rachid ALAMI Directeur de recherche LASS-CNRS Rapporteur
Dominique DUHAUT Professeur à l'Université de Lorient Rapporteur
Jacques FERBER Professeur à l'Université Montpellier II Examinateur
Jean-Louis VERCHER Directeur de recherche CNRS Aix-Marseille Examinateur
René ZAPATA Maître de conférence à l'Université Montpellier II Directeur de thèse
Philippe LUCIDARME

APPRENTISSAGE ET ADAPTATION POUR DES ENSEMBLES DE ROBOTS

REACTIFS COOPERANTS

Résumé : Ces travaux de thèse se placent dans le contexte des systèmes multi-agents
distribués. L'objectif est l'étude de méthodes d'auto-apprentissage appliquées à des ensembles
de robots réactifs. Ces travaux se focalisent sur l'apprentissage de comportements sensori-
moteurs de bas niveaux.
Il nous semble important que les méthodes proposées puissent être appliquées sur des
systèmes réels, dont les contraintes sont parfois loin de celles de la simulation. C'est pour
cette raison que nous avons imaginé et conçu une plate-forme expérimentale composée de 4
robots mobiles, un manipulateur mobile miniature et un système de vision stéréoscopique.
Cette étude se décompose en deux parties. La première, appliquée aux systèmes
homogènes, présente l'étude de méthodes évolutionnistes appliquées aux systèmes multi-
robots. La seconde, appliquée aux systèmes hétérogènes, s'intéresse à la possibilité d'utiliser la
technique du recuit simulé pour optimiser les poids d'un contrôleur neuronal. Toujours dans
ce contexte d'hétérogénéité, une seconde méthode basée sur l'apprentissage par renforcement
est expérimentée.

Mots-clefs : Systèmes multi-robots, apprentissage, réseaux de neurones artificielles,

algorithmes évolutionnistes, apprentissage par renforcement, recuit simulé, manipulateur
mobile miniature.

LEARNING AND ADAPTATION FOR GROUPS OF REACTIVE AND

COOPERANT ROBOTS

Abstract : The aim of this work is to build fault tolerant cooperative multi-robots systems.
Our approach uses self-learning techniques to control groups of reactive robots. This work
focuses on learning low level sensory-motor behaviors.
It seems important that the proposed methods may be implemented on real robots. The
constraint of such real systems is sometime far from simulated worlds. This is why we
imagined, designed and build an experimental platform composed of four mobile robots, one
miniature mobile manipulator and one stereoscopic vision system.
This study is composed of two parts. The first one is applied to homogeneous systems.
Evolutionist techniques are studied.
The second one, applied to heterogeneous systems, focuses on using simulated
annealing procedure to optimize the synaptic weights of a neuro-controller. Another method
is also experimented, based on reinforcement learning.

Keywords : Multi-robot systems, learning, artificial neural networks, evolutionist algorithms,

reinforcement learning, simulated annealing, miniature mobile manipulator.

Université Montpellier II