Programme de pilotage évolutif pour Robby le robot
Ici, je vais exposer en détail un exemple d'algorithme génétique simple de contrôle d'un robot virtuel.
Notre robot virutel s'appelle Robby.
C'est un robot très simple évoluant dans un monde simulé.
Je l'ai décrit en premier dans mon livre "Complexité. Une promenade accompagnée"
et son travail est de ramasser les boîtes de sodas vides.
Robby est inspiré d'un robot réel nommé Robot
qui fonctionnait en 1988 dans le laboratoire d'intelligence artificielle du MIT
et se déplaçait sur ses roues de bureau en bureau
en collectant les boîtes de soda vides puis il les déposait à la poubelle.
Robot est le résultat du travail de Jonathan Connell, étudiant au MIT, et de Rodney Brooks et Peter Ning
C'est un robot très impressionnant utilisant seulement des algorithmes très simples
pour contrôler son comportement.
Notre robot s'appelle Robby, c'est un robot virtuel
qui évolue dans un environnement simulé constitué d'une grille de 10 carrés par 10 de côté
chaque carré représentant un bureau.
Chaque bureau est soit vide soit contenant une boîte de soda vide.
Voici par exemple une boîte de soda vide.
Le travail de Robby sera de se déplacer dans cet environnement et de ramasser les boîtes de soda vides.
Donc, il faut que l'on donne à Robby un programme lui disant quoi faire à chaque étape.
Je peux programmer cela moi-même mais au lieu de cela je vais utiliser un algorithme génétique
pour faire évoluer les programmes pour effectuer cette tâche.
En premier lieu laissez moi vous décrire ce que Robby peut voir et ce qu'il peut faire.
C'est un robot très simple qui a une très mauvaise vision
et la seule chose qu'il puisse voir est le contenu de son propre carré ainsi
que de ceux situés au Nord, au Sud, à à l'Est et à l'Ouest.
Dans son état actuel, son bureau ou local est vide
au Nord il y a un mur, à l'ouest il y a un mur
au sud il y a un carré vide et à l'est une boîte.
C'est tout ce qu'il peut voir.
Il utilise ce qu'il peut voir pour décider quelle action entreprendre à chaque pas de temps.
Il a 7 actions possibles
Il peut se déplacer vers le nord, se déplacer vers le sud
se déplacer vers l'est, se déplacer vers l'ouest
correspondant à un déplacement d'un carré
il peut effectuer un déplacement aléatoire dans une direction au hasard
il peut rester sur place et ne rien faire
ou il peut essayer de prendre une boîte.
S'il essaye de prendre une boîte alors qu'il y en a une, c'est un succès.
Ou il peut essayer de prendre une boîte dans un carré vide et c'est un echec.
Il obtient certaines récompenses ou pénalités
selon l'action effectuée.
S'il prend une boîte il obtient 10 points en récompense de son action
s'il essaye de prendre une boîte dans un emplacement vide, il obtient -1 point
et s'il se cogne à un mur il obtient -5 points.
La performance globale de ses déplacements est la somme des récompenses et des pénalités obtenues.
L'objectif est d'utiliser un algorithme génétique pour faire évoluer un programme de contôle
c'est à dire une stratégie pour Robby.
Voyons ce que signifie le terme "stratégie" ?
la définition que je vais utiliser est :
Un ensemble de règles spécifiant une action pour chacune des situations possibles.
Les situations possibles sont les entrées de Robby, ce qu'il peut voir.
Etablissons une liste de ces situations possibles que Robby peut rencontrer
Ces situations peuvent être
que voit-il au nord, au sud à l'est et à l'ouest ?
l'état de sa position actuelle ?
Et la stratégie pour chaque situation possible sera l'action à entreprendre
Voici une sitation possible, peut-être la plus simple
tout est vide, dans toutes les directions
c'est une situation possible
Voici une autre situation possible
tout est vide sauf dans la cellule courante où il y a une boîte
et l'on peut continuer ainsi d'énumérer toutes les sitautions possibles
et se demander combien y-a-t'il des possiblités
mais simplement pour être sûre que vous suivez passons à un "quizz" rapide
Ce quizz contient deux questions
pour la première, examinez cette situation et supposez que Robby ait un score de 0
puis qu'il entrepenne cette suite d'actions
déplacement est, déplacement est,
ramassage d'une boîte, déplacement est,
ramassage d'une boîte, déplacement sud
il effectue ces 6 actions
et vous devez répondre à la question :
quelle est la situation après ces 6 actions
puis quel est le score obtenu ?
Et voici un récapitulatif de la manière de calculer le score