|
L'architecture de subsomption
Avant la découverte de l'architecture de subsomption par [Brooks 1986], les contrôleurs de robots étaient généralement décomposés en modules successifs. Un système de contrôle centralisé exécutait l'un après l'autre les processus requis par chaque module et transmettait les résultats du processus d'un module au module suivant. Par exemple, les senseurs percevaient ce qu'ils pouvaient du monde; ces perceptions étaient transmises à un module de modélisation qui les transformait en une représentation interne du monde; puis cette représentation était transmise au module de planification des actions; et finalement les actions souhaitées étaient transmises au module de contrôle des moteurs. Seul le module d'entrée et le module de sortie étaient en contact avec le monde, et le système global ne fonctionnait que si chacun des modules fonctionnait correctement.
Par opposition, dans une architecture de subsomption, chaque module à la fois est en contact avec les entrées et peut agir sur les sorties du système: un module est un comportement. Ceci n'est pas juste une différence d'implémentation mais reflète la philosophie entière de Rodney Brooks et, au-delà, celle l'école de pensée qui a inspiré ce qui a été appelé "la nouvelle intelligence artificielle" [Brooks 1990]. Face au plafond de verre atteint par les systèmes experts et
autre techniques d'intelligence artificielle issues de tentatives d'émulation directe
de l'intelligence et des capacités de
raisonnement abstrait humains, cette nouvelle intelligence artificielle insiste sur la nécessité d'une approche progressive (bottom up), souvent inspirée des processus naturels. Mettre les modules du contrôleur en contact direct avec
l'environnement du robot c'est le "situer", l'enraciner dans cet environnement.
Rodney Brooks n'essaye pas de faire construire à ses robots une représentation interne du monde, il déclare que "the world is its own best model".
Formellement, un comportement est une fonction Ci:
Ci: Ei -> Ai
Où Ei est un sous ensemble de l'ensemble E des états (ou entrées sensorielles) possibles et Ai est un sous ensemble de l'ensemble A des actions possibles (généralement restreint à une seule action par comportement).
Une architecture de subsomption est un sous ensemble de l'ensemble des comportements possibles et une relation d'ordre stricte sur ce sous ensemble. En cas de conflit, les modules supérieurs bénéficient d'une priorité absolue.
Exemple: Un robot forageur
Une expérience classique en robotique est de placer de la "nourriture" dans une arène et d'assigner au robot (qu'on appelle alors "forageur") la tâche de trouver cette nourriture et de la "manger". Un robot qui aurait pour contrôleur l'architecture de subsomption ci-dessus serait capable d'effectuer cette tâche.
Tant que rien ne vient activer les comportements supérieurs, c'est le module le plus bas qui agit (par défaut). Le robot va donc tout droit. S'il voit un mur devant lui (et pas de mur à gauche) le module 2 est activé. Ce module prend le pas sur le module inférieur par rapport auquel il est prioritaire, et le robot tourne à gauche. Etc.
Cette architecture peut s'exprimer sous formes de règles de décision ordonnées (ce qui est important pour l'apprentissage). L'exemple ci-dessus deviendrait:
SI (Je suis juste à coté de nourriture) ALORS je mange
SINON {
SI (Je vois de la nourriture) ALORS je vais vers la nourriture
}
SINON {
SI (J'ai un mur devant moi et à gauche) ALORS je tourne à droite
}
SINON {
SI (J'ai un mur devant moi) ALORS je tourne à gauche
}
SINON je vais tout droit
Il n'est pas nécessaire que l'architecture soit complète pour que le robot ait déjà un comportement "intelligent": si les trois modules du bas sont en place le robot aura un comportement de "balayeur", c'est-à-dire qu'il sera capable d'explorer son environnement. Toutefois, cette exploration sera sans but puisque le robot ne saura pas encore reconnaître/trouver/manger sa "nourriture". De même, tourner systématiquement à gauche lorsqu'il y a un mur devant peut permettre au robot de ne pas heurter les obstacles: à force de tourner à gauche il finira par se retrouver dans une position où il n'y aura plus d'obstache devant lui. Les deux modules du bas associés au module supérieur permettraient au robot de manger, à condition que durant son errance exploratoire il se soit par hasard retrouvé juste à coté de "nourriture".
L'architecture de subsomption est donc plus robuste que l'architecture en série, car il est souvent possible qu'un ou plusieurs des modules ne fonctionne pas de manière optimale sans que le robot ne devienne totalement inopérant pour autant. L'idéal est que la perte successive de plusieurs modules entraîne une dégradation en pente douce des performances du robot.
Un autre avantage de cette architecture est qu'elle est plus facile à débugger.
Du fait de l'ancrage dans le monde des différents modules, si un disfonctionnement
survient identifier le module responsable est généralement d'emblée évident. Cette facilité accrue d'utilisation laisse présager un
passage à l'échelle couronné de succès. "At least if our strategy does not convince the arm chair philosophers, our engineering approach will have radically changed the world we live in"
[Brooks 1990].
[Koza, 1993] a utilisé les algorithmes génétiques, et plus précisément la prommation génétique, pour faire évoluer le contrôleur d'un robot muni d'une architecture de subsomption.
La programmation génétique diffère du reste des algorithmes génétiques en ce que les individus évoluants sont des structures en forme d'arbre (voir les arbres de décision) pour un exemple simple d'une telle structure et les opérateurs de croisements et de mutation pour un exemple illustrant comment la programmation génétique peut générer des individus de taille variable.
Le problème consistant à apprendre à un robot à suivre un mur dans une pièce de forme irrégulière a été décrit par [Mataric, 1990]. Il s'agit d'un robot à 12 senseurs équirépartis sur sa circonférence qui lui communiquent la distance approximative des murs:
Le robot peut aller tout droit, reculer, tourner à droite, tourner à gauche ou s'arrêter. [Mataric, 1990] avait résolu le problème en programmant manuellement 4 comportements d'une architecture de subsomption. Mais l'apprentissage offre des perspectives d'avenir bien plus larges que la programmation manuelle, car la programmation manuelle ne passe pas à l'échelle: en effet, s'il est relativement simple, et parfoir même trivial, de programmer des comportements de base dans un environnement simple et statique, il devient très rapidement d'une complexité effroyable de faire la même chose dans un environnement complexe, non markovien, et succeptible d'évoluer dans le temps. En revanche, un algorithme d'apprentissage permettant à un robot de mettre lui-même au point son contrôleur, peut permettre à ce robot d'affronter des environnements complexes.
[Koza, 1993] a utilisé comme entrées les valeurs des 12 senseurs du robot, une valeur spécifique indiquant quel senseur a la valeur la plus basse (= de quel côté le robot est le plus proche d'un mur) ainsi que 2 constantes: la distance du mur souhaitée et la distance de sécurité minimale (les robots réels, contrairement aux robots simulés, peuvent s'abîmer s'ils foncent dans un mur). Les fonctions étaient des règles de décision du type
SI (Valeur1 < Valeur2) ALORS Action A SINON Action B
ou l'une de 4 actions (Koza n'a pas retenu le "STOP"), ou la fonction de priorité:
SI (Priorité Action A, Action B) ALORS Action B qui permet d'implémenter une architecture de subsomption.
La fitnesse (mesure permettant d'évaluer les individus pour répartir les chances de reproductions, voir le shéma des algorithmes génétiques) consistait à récompenser les robots qui passaient durant le temps qui leur était imparti sur un nombre maximal de tuiles, les tuiles étant placées à la distance souhaitée du mur. Les paramètres précis de l'expérience sont données dans [Koza, 1993]. A la 57ème génération le meilleur individu est passé sur toutes les tuiles, ce qui signifie qu'il a effectué un tour complet de la pièce en se maintenant à la distance requise des murs.
Quelques années plus tard
Nous sommes loin de l'époque où Rodney Brooks devait défendre
son architecture à coups de formules percutantes et un peu fanfaronnes, si loin
qu'elle semble avoir rejoint la préhistoire.
"Hierarchical approaches and
methodologies are commonly used for control system design and synthesis" est la
toute première phrase de [Tunstel, Oliveira & Berman, 2002] qui étudient les architectures
de subsomption floues.
Déjà en 1991
[Mahadevan & Connell, 1991] commencait son introduction par "Behavior-based robots, such as those using the subsumption architecture, are a promising and demonstrably successful approach to building intellignet autonomous agents"; mais à l'époque il fallait encore le prouver:
C'est ce que ces auteurs s'emploient à faire dans un article de 49 pages qui ressemble à un rapport technique. Voila ce qu'ils obtiennent avec un robot réel
(nomé Obélix) dont la tâche est de pousser des boites dans
une pièce (ce qui veut dire distinguer ce qui est une boite de ce qui n'en est
pas une, pousser droit car sinon la boite part de coté et n'avance guère,
et se sortir des situations gênantes qui se produisent lorsque, par exemple,
une boite à été poussée dans un coin).
Le détail des algorithmes utilisés dépasse le cadre de cette partie, mais il est fascinant de noter la convergence de l'architecture de subsomption apprise grace au "Q-learning with statistical clustering" et de celle programmée à la main.
Les modules appris peuvent à présent prendre des architectures très diverses: ensemble de classeurs, réseaux neuronaux, arbres de décision, etc. Le champs d'action des méthodes d'apprentissage s'est lui-même élargi: [Olmer, Nordin & Banzhaf, 1996] utilisent les algorithmes génétiques pour faire évoluer à la fois l'intérieur des modules et l'architecture globale. Leur plateforme de tests est un robot khepera, une petite "boite de thon" de 6 centimètres de diamètre:
Et dans quelques annés?
Nous pourrions pour finir nous demander si [Brooks 1990] a tenu sa promesse:
"At least if our strategy does not convince the arm chair philosophers,
our engineering approach will have radically changed the world we live in".
Quoique puissent à présent penser les "philosophes en fauteuil",
Brooks a certainement convaincu les chercheurs.
En plus de son poste en tant que directeur du Labo d'Intelligence Artificielle
du MIT, nous le retrouvons actuellement
co-fondateur et ingénieur en chef chez iRobot, compagnie qui commercialise
des robots utilisants son architecture, entre autres des aspirateurs robots. J'en ai
un. Je n'irais pas jusqu'à dire que ça a "radicallement changé le
monde dans lequel je vis", mais c'est si pratique de pouvoir brancher l'aspirateur
avant de partir le matin et de retrouver une moquette propre le soir que j'ai choisi
ce sujet par reconnaissance.