Karel Capek, he author of the play "Rossum's Universal Robots" did not, in fact, invent the word robot; he merely ushered it into existence. It was like this: the idea for the play came to said author in a single, unguarded moment. And while it was still warm he rushed immediately to his brother Josef, the painter, who was standing before an easel and painting away at a canvas till it rustled.
"Listen, Josef," the author began, "I think I have an idea for a play." "What kind," the painter mumbled (he really did mumble, because at the moment he was holding a brush in his mouth). The author told him as briefly as he could. "Then write it," the painter remarked, without taking the brush from his mouth or halting work on the canvas. The indifference was quite insulting. "But," the author said, "I don't know what to call these artificial workers. I could call them Labori, but that strikes me as a bit bookish." "Then call them Robots," the painter muttered, brush in mouth, and went on painting. And that's how it was. Thus was the word Robot born; let this acknowledge its true creator.
Lidove Noviny, 24.12.1933
De robots sophistiqués tel l'Aibo de Sony (a gauche), à l'humble Khepera de Cyberbotics (a droite), les robots représentent une plateforme de choix - et fascinante - pour les chercheurs en intelligence artificielle. Nous verrons tout d'abord ce qu'est l'apprentissage en robotique, puis l'origine des agents. Les domaines d'application des systèmes multi-agents seront ensuite abordés, puis une définition de l'autonomie sera vue et deux types différents d'apprentissage seront vus;On verra ce que sont les algorithmes génétiques et l'apprentissage par renforcement et enfin les réseaux de neurones et la coévolution.
L'apprentissage
L'apprentissage en robotique est un sous domaine de la recherche en intelligence artificielle dont le but est de développer des contrôleurs de robots capables d'apprendre un nouveau comportement ou d'améliorer un comportement pré-programmé en se basant sur leurs expériences passées. De nombreuses techniques existent (voir la partie commune).
Les systemes d'IAD, et notamment les systèmes multi-agents (SMA), ont
d'abord integr´ des techniques d'apprentissage issues de l'IA. Ces
systèmes présentant cependant des caractéristiques inconnues de l'IA,
l'apprentissage a peu à peu evolué pour devenir un cas particulier dans sa
forme et ses objectifs quand il est appliqué dans un SMA.
L'origine des agents
Elle provient d'une part, de l'intelligence artificielle distribuée
(IAD), et d'autre part de la vie artificielle. Les premières applications
de la vie artificielle sont apparues quasiment en même temps que
l'informatique, avec Von Neumann et ses automates cellulaires, ou encore Mc
Culloch et ses neurones formels.
L'IAD est apparue vers la fin des années 1970. Hewitt confronté à un
problème de résolution de théorèmes proposa une solution en 1977 avec des
entités actives appelées acteurs et considéra la résolution comme une
confrontation de points de vue.
D'un autre côté, [Erman & al, 1980]
élabora l'idée du tableau noir
("blackboard") avec le projet HERSAY II. Le tableau noir utilisé est
un emplacement réservé pour la transition des informations entre les
différents agents. Chaque agent peut venir lire ou écrire sur le tableau noir.
Cette métaphore provient de la situation où plusieurs personnes
transitent par le même bureau mais n'y demeurent généralement pas.
Si, par exemple, le téléphone sonne, la personne qui repond
inscrira sur le tableau noir "Untel voudrait qu'Unetelle le rappelle".
Unetelle prendra connaissance du message lors de son passage
suivant dans ce bureau.
Ce sont donc à partir de ces premières réalisations que nous avons vu
apparaître l'idée de système multi-agents.
L'apprentissage peut être particulièrement utile:
Nouvelles tendances:
La vie artificielle est l'expression la plus récente d'une tradition
relativement longue d'un courant de pensée qui cherche le coeur des
capacités cognitives et de l'intelligence. Ce courant de pensée peut voir, de
façon métaphorique, un meilleur prototype de l'intelligence dans un
modeste insecte plutôt que dans les capacités symboliques d'un expert.
Non pas qu'ils considèrent l'insecte plus intelligent que l'humain, mais
face aux limitations des systèmes experts les adeptes de l'approche
"vie artificielle" préconisent une approche graduelle de l'intelligence.
En ce sens, les insectes sont de meilleurs modèles puisque, justement,
ils sont moins inteligents que les humains et devraient donc être
des modèles plus faciles à émuler
[Floreano, Nicoud & Mondada, 1999].
Dans le prolongement de la cognition située, il est intéressant
de connaitre l'intelligence collective. Les colonies d'insectes ont des
comportements intelligents, sociaux, qui sont dus à l'interaction entre
chaque insecte. L'intelligence collective est alors supérieure à la
somme des intelligences individuelles, c'est ce qu'on appelle une
"propriété émergente". En robotique, l'un des comportements
émergents les plus simples a réaliser est un comportement
"amical". Si on met dans une arène deux kheperas qui ont chacun
appris à en suivre les murs, l'un en gardant le mur à sa gauche et
l'autre en gardant le mur à sa droite, ils vont, dès qu'ils se rencontreront,
partir ensemble pour une traversée de l'arène.
Démonstration réalisée au LRI à partir du
simulateur WoB de Jérémie Mary.
L'impression eprouvée
par un observateur naif est que les deux robots sont copains. En
réalité, bien sur, ce comportement émergent de copinage vient seulement
du fait que les kheperas ne distinguent pas un mur d'un autre khepera:
ils se suivent l'un l'autre comme ils suivraient un mur, et, comme ils
vont à la meme vitesse, ils traversent l'arene côte à côte.
Les pionniers de la vie artificielle, comme Grey Walter et W. Ross Ashby
ne reçurent pas
toute l'attention qu'ils auraient mérité.
Actuellement, la validité de cette approche a acquis une large
reconnaissance (voir par exemple les recherches menées
par l'AnimatLab).
Autonomie et fermeture opérationnelle:
Si un système est considéré comme autonome, l'attention est centrée sur
les comportements émergents et les processus internes de réorganisation
qui définissent ce qui compte comme interactions appropriées, et sur le
fait qu'il puisse "décider" quoi faire en fonction des informations
contenues dans sa mémoire et de celles fournies par ses capteurs.
[Varela, 1979] a proposé la définition suivante : tout système autonome est
fermé opérationnellement. La notion de fermeture doit être entendue au
sens algébrique : un domaine K a une fermeture si toutes les opérations
qui y sont définies restent dans le même domaine. Le point d intérêt
principal est la nature des dynamiques internes des systèmes.
La fermeture opérationnelle du système nerveux met donc en avant un
mode spécifique de cohérence, qui est embarqué dans l'organisme
Deux diff&eacite types d'apprentissage:
Apprentissage distribué
Le système distribué ne présente pas de
point de vue global: les robots peuvent disposer chacun
d'un contrôleur embarqué capable d'apprendre de facon indépendante.
Les algorithmes utilisés le plus fréquement dans ce cas sont les
methodes d'apprentissage par renforcement, par exemple les reseaux neuronaux.
Apprentissage centralisé
Un point de vue centralisé permet de comparer tous les individus et de
sélectionner les meilleurs comportements.
C'est entre autres l'approche des algorithmes génétiques où une
population d'individus est triée à chaque génération par l'algorithme
dans le but de sélectionner les meilleurs pour la reproduction
(voir l'explication de ce mechanisme donnée dans
la partie commune).
L'inconvénient de l'apprentissage centralisé est qu'une base centrale
doit être présente dans cette configuration afin de recueillir les
informations venant des robots (grands nombre de communications,
et coût élev&eacue; en terme de temps de calcul); l'avantage est
qu'on peut suivre l'évolution du processus d'ensemble.
Algorithmes génétiques
L'évolution du comportement peut être directement liée au nombre et aux
capacités des "espèces" de robots. Dans le cas d'une seule espèce (groupe de robots
similaires ayant un but commun) le mode
d'évolution le plus simple est directement inspiré du monde
animal : l'évolution par la sélection des plus aptes et l'élimination des
plus faibles (Darwin) qui inspira la programmation genetique
[Koza, 1992]. Ces évolutions ont généralement lieu en simulation, car
le temps d'évaluation d'un individu multiplieé par le nombre d'individus
multiplié par le nombre de générations rendrait une évolution directement
implementée sur le hardware tres longue. Parfois les premières générations
sont évoluées en simulation et les dernières mettent en jeu des robots
physiques.
Ceci soulève divers problèmes pratiques, comme la nécessite de bruiter les
capteurs dans le simulateur, car sans cela un contrôleur qui fonctionne
tres bien en simulation peut échouer lamentablement dès qu'il est
implémenté sur un robot réel. Ce phénomène rejoint le problème du
pas de discrétisation des simulateurs: au début de l'application des algorithmes
génétiques aux contrôleurs de robots évolués en simulation, ils évoluaient dans
des "univers" dont la surface était "dallée" (par exemple composée d'une
grille de 10 X10 carrés). Le robot n'avait donc que 100 positions possibles et
le problème qu'il avait a résoudre était simplifié au point où les contrôleurs
résultants ne pouvaient pas être transférés avec succès dans des robots réels.
Ces univers ont par la suite été qualifiés dérogativement d'univers-jouets.
Apprentissage par renforcement:
L'apprentissage par renforcement tente de maximiser
les récompenses et de minimiser les punitions au cours du temps
[Sandip & Sekaran, 1996].
L'utilisation du
Q-learning par des agents
[Sandholm & Crites, 1996]
conduit au choix préférentiel des
meilleures actions et à l'abandon des actions dont la perspective de
succès est plus faible par l'application de l'algorithme "Automatic Concept Extraction"
(ACE).
Les méthodes de renforcement par apprentissage obtiennent de bons
résultats dans le cas d'un but unique [Mataric, 1995].
Par contre, les résultats s'avèrent
médiocres lorsque celles-ci sont appliquées à des situations où coexistent
plusieurs objectifs. En ce sens, il est proposé une méthodologie qui
prend en compte les propriétés et les connaissances implicites du
domaine, dans le but d'accélérer le processus d'apprentissage et de le rendre
possible dans des systèmes complexes et dynamiques. Cette méthodologie
est constituée par un algorithme capable de traiter de multiples
sous-objectifs concernant le même agent, à l'aide d'une fonction de
renforcement hétérogène. Cette méthode utilise des estimateurs de progrès, ce
qui permet au renforcement d'être en accord avec l'évolution du processus
de résolution des sous-objectifs, au cours de la résolution d'un
problème. D'autres apprentissages distribués empruntés aux SMA sont
directement appliquables en robotique : citons le système d'apprentissage
mutuellement supérvisé
[Goldman & Rosenschein, 1995].Dans ce cas la
connaissance passe par les communications, si un agent sait faire quelque chose
il l'apprend aux autres. Une autre voie et l'apprentissage par imitation
(appliquable pour la manipulation d'objets).
Les réseaux de neurones:
Historiquement la première méthode d'apprentissage, la programmation
neuronale est nspirée du fonctionnement du
cerveau, elle est donc symboliquement très liée à la notion d'intelligence,
et d'apprentissage.
Les réseaux de neurones sont utilisés aussi bien seuls, ce qui est une
forme d'apprentissage par renforcement, que dans le cadre des
algorithmes génétiques. Dans ce dernier cas, un individu est souvent
un vecteur de poids (nombres réels) représentant les poids des
connexions du réseau.
Parfois aussi, la structure même du réseau de neurones évolue en meme temps que les poids (une mutation peut par exemple résulter en un neurone supplémentaire) ou, dans des expériences récentes, les neurones sont répartis en modules ayant des fonctionalités diverses et ces modules sont suceptibles d'évoluer à la fois en termes de structure et en termes de fonctionalité [Godzik, Schoenauer & Sebag, 2004].
Coévolution :
Certaines expériences en robotique autonome mettent en compétition
ou en partenariat plusieurs "espèces" de robots. Par exemple
une proie et un prédateur dont les buts sont bien évidemment opposés:
Le but du prédateur est de manger la proie, le but de la proie est de ne pas
se faire manger.
[Floreano, Nicoud & Mondada, 1999] ont démontré que ce type
de co-évolution pouvait aboutir à des évolutions cycliques: le prédateur
s'adapte au comportement de la proie, qui change alors de comportement
pour lui échapper. Ensuite, le prédateur s'adapte au nouveau comportement
de la proie qui revient alors à son comportement précédent pour lequel
le prédateur n'est plus adapté. Au bout du compte, les meilleurs
individus sont ceux qui savent rapidement s'adapter au changement
mais aucun progrès global dans les stratégies n'émerge.
Les comportements issus de ces processus d'évolution, observables sur
les populations de robots sont variés :
[Li, Martinoli & Abu-Mostafa, 2004] ont construit une métrique de mesure
de similarité et une métrique de mesure de spécialisation des agents faisant partie d'un
essaim, qui au départ de l'expérience sont identiques.
Ils ont montré que suivant la tâche assignée à l'essaim différents
agents se spécialisaient pour différentes sous-tâches (les agents
communiquent et recoivent à la fois un renforcement global dépendant des
performances de l'essaim et un renforcement individuel).
La tâche (illustrée ci-dessous) s'y pretait bien: il s'agit de retirer du sol de l'arène un baton qui ne
peut être retiré que si deux robots kheperas collaborent: L'un des robots
doit soulever le baton pour qu'un autre puisse le prendre par le bas. Si un
seul khepera tire dessus il ne peut soit pas le soulever assez haut pour le
sortir, soit il tire de côte et le baton se coince dans son trou. Une généralisation
de cette expérience est le cas où chaque robot ne peut que soulever le
baton de 1/k de la longueur du baton et il faut donc une collaboration entre k kheperas pour
sortir le baton du sol. Ceci est réalisé en pratique en prenant des batons plus
long plantés dans des trous plus profonds.
L'expérience de
[Li, Martinoli & Abu-Mostafa, 2004] est également un tres bon exemple d'
apprentissage des interactions et d'apprentissage de la communication
car elle illustre
Comment des
agents peuvent apprendre des comportements coopératifs dans le but de partager des ressources de façon optimale et de
maximiser le renforcement positif (apprentissage des interactions) et comment ils apprenent à
coordonner leurs efforts (apprentissage de la communication).
Conception méthodologique d'un systeme multi-agent capable d'apprendre:
[Drogoul & Zucker, 1998] se sont pencheés sur le problème de savoir à quel niveau, et comment, intégrer les
méthodes d'apprentissage dans les systèmes multi-agents.
Dans ce but, ils ont défini la méthode de conception orientée-agent Cassiopée, car,
disent-ils, "Methodologies in computer science are what recipes are for cooking:
they replace neither the intuition nor the coding, but provide a framework for unifying these two
activities". Mais nous nous rapprochons là du meta-learning, qui est une autre histoire.
References:
[Erman & al, 1980]
L. D. Erman, F. Hayes-Roth, V. R> Lesser et D.R. Reddy,
"The Hearsay II speech understanding system; Integrating knowledge to resolve
uncertainty", ACM Computing Survey 12, pp 213-253, 1980.
[Ferber, 1995] J. Ferber, "Les systemes multi-agents, InterEditions, 1995.
[Varela, 1979] F. J. Varela, "Principles of biological autonomy", New York, North-Holland, 1979.