Approche Évolutionniste de la Robotique - Master … · Observation pendant la durée de vie Condensation des observations en un ou plusieurs critères ... La selection est basée

Principes des AE Évaluation et pression sélective Simulation vs réalité Que faire évoluer ? Outils Problèmes ouverts

Approche Évolutionniste de la Robotique

Stéphane Doncieux1

ISIR - Université Paris 6http://animatlab.lip6.fr http://www.isir.fr

http://animatlab.lip6.fr

http://www.isir.fr


1 Principes des AE

2 Évaluation et pression sélective

3 Simulation vs réalité

4 Que faire évoluer ?

5 Outils

6 Problèmes ouverts


Principes des AlgorithmesÉvolutionnistes

Principes, définitions et exemples


Principe

1 Génération aléatoire d’unensemble de solutionspotentielles

2 Évaluation des solutions3 Sélection des meilleurs.

Arrêt si critères de finatteints

4 Génération de nouveauxindividus

5 Retour en 2


Définitions (1)

Génotypedescription d’une solution

Ex : liste de paramètres

Phénotypesolutions que l’on souhaite

optimiserEx : forme d’un profil d’aile

d’avion


Définitions (2)

Fonction de Fitness : critère à maximiser (ou minimiser)spécifié par l’utilisateur

Ex : Maximisation de la portance

Algorithme de sélection : choix des individus conservés à partirde la fitness : conservation des X% des meilleurs, choix avec

une probabilité proportionnelle au rang...


Génotype & opérateurs génétiques

L’opérateur de mutation modifiealéatoirement une partie du

génotype.L’opérateur de croisementéchange des morceaux degenotype entre individus.


Ce que la robotique change à l’AE

Le génotype sert à décrire unepartie du robot.L’évaluation est plus complexe :

observation ducomportement du robotcalcul non instantanné !note unique (ou presque) àdéterminer à partir d’uneséquence d’observations


Quelques exemples

Évitement d’obstacles(Braitenberg)

Marche d’un robot hexapode

Contrôle des battements d’un robot à ailes battantes


Hypothèse fondamentale

La pression sélective a un pouvoir structurant suffisant pourfaire émerger des comportements adaptés à l’environnementdu robot et à ses moyens d’interaction avec celui-ci.


Motivations

de la biologie et de la vieartificielle ...

comprendre le vivant, lespressions qui l’ont mené àsa forme actuelleconcevoir desécosystèmes peuplés decréatures capables des’adapter à leurenvironnement

à l’ingénierie

reproduire les mécanismesadaptatifs qui ont conduit àl’apparition de créaturesvivantes adaptées à quasimenttous les milieux et les adapter àla robotique.


Motivations

Approche animat :émergence de comportements efficacesexploitation de caractéristiques propres à la dynamiqued’un robot particulier.

→ le robot doit apprendre par lui-même comment remplir satâche au travers de ses interactions avec l’environnement...


Intérêt des algorithmes évolutionnistes

Bonnes performances moyennesNe nécessite pas de propriétés mathématiquesparticulièresPeu de contraintes sur le système à concevoir


Principales problématiques

Contexte :ressources computationnelles limitées : populations detaille réduite par rapport à un équivalent quelconque enbiologie et temps d’évaluation limitéquantité de robots très faible, robustesse mécaniquelimitée !

Problématiques :Comment réaliser la pression sélective et, question liée,quel retour du comportement du robot ? Probleme dubootstrapLiens simulation-réalite (pbe d’experimentation sur ledispositif reel)Quel espace de recherche et comment l’explorer ?


Évaluation et pression sélective


Évaluation

Métaphore de la théorie Darwinienne de la sélection desespèces, mais dans la nature, il n’y a pas vraiment de fonctionà maximiser...

Fitness implicite Pas decomportement imposé.

Exemple : maximisation de ladurée de vie, reproduction par

rencontre des individus.→ le comportement généré

dépend de l’environnement...

vs

Fitness explicite On cherche uncomportement précis.

Exemple : avancer le plus vite,éviter les obstacles...

→ le comportement global estimposé, pas les commandes

motrices précises (ce n’est pas dusupervisé)


Fitness implicite

Approche de type "écosystème virtuel" : un monde virtuel estpeuplé de différentes entités :

inanimées : obstacles, sources de nourritureanimées : animats de différents types

Les interactions entre les différentes entités créent unedynamique qui, bien qu’elle soit très simplifiée, peut rappelercelle d’écosystèmes naturels.

Motivation : vie artificielle


Fitness implicite

La pression sélective repose sur la définition de la notion desurvie dans l’environnement, survie souvent liée à l’accès auxressources.

Exemple [Pichler et Canamero 2007] : définition d’un "budgeténergétique"


Fitness implicite

Quelques résultats :


Fitness explicite

Approche "ingénieur" : la pression sélective est exercéedirectement à partir de critères intéressant l’expérimentateur.

L’influence de l’environnement est amoindrie :les individus sont observés dans un contexte similaire(conditions initiales identiques)une note ou un ensemble de notes sont tirées del’observation du comportement de l’animatune sélection est opérée sur la base de ces notes,indépendamment de l’environnement


Fitness explicite

Définition de la fitness :Description qualitative du comportementChoix des observablesObservation pendant la durée de vieCondensation des observations en un ou plusieurs critères(selon AE mono- ou multi-objectifs)


Fitness explicite

Quelques problèmes classiques :

condenser des observations en un ou plusieurs critères aune grande influence sur les résultats. Ex : suivi detrajectoiredéfinition des critères. Ex : éviter des obstaclessystème adaptatif = système opportuniste. Ex : marcher leplus loin en simulation


Fitness explicite

Ne pas prendre en compte un état à un instant donné, maisune observation sur la durée.Observer et analyser les solutions générées.


Fitness explicite

Ne pas prendre en compte un état à un instant donné, maisune observation sur la durée.Observer et analyser les solutions générées.


Fitness explicite

Être incrémental dans la façon de noter un individu : lespremiers individus feront de toute façon n’importe quoi...

Parmi les ”mauvais individus”, la fitness doit pouvoir discriminerceux qui sont sur la ”bonne voie” des autres.

Exemple : suivi de trajectoirepoints de passageécart moyen à des vecteurs vitesse relative instantannés


Pression sélective

Comment exercer la pression pour que l’évolution puisse suivreun chemin continu depuis un individu généré aléatoirementvers la solution au problème complet ?


Multi-critère : définitions

Définitionsx1 domine x2 si :

1 x1 est aussi bon que x2sur tous les objectifs

2 x1 est strictementmeilleur que x2 sur aumoins un objectif

l’ensemble des solutionsdominantes est appelé lefront de Pareto.


Multi-objectifs & Algorithmes Évolutionnistes

Exemple : MOGA algorithm (Fonseca 1993)

La selection est basée sur le rang des individus.rank(i) = 1 + nbdomine(i)


Multi-objectifs & Algorithmes Évolutionnistes

Le rang est modulé par un sharing factor pour assurer unebonne couverture du front de pareto.

f (i) = rank(i) + σshare(i) 0 < σshare(i) < 1

f1

f2

do share


Exemple : contrôle d’un pendule inversé (1)

Objectif : contrôler x et θ

θ

x

F



Génération 120

Approche mono-objectif

100.2

100.4

100.6

100.8

101

101.2

100.2 100.4 100.6 100.8 101 101.2

populationpareto front

Approche multi-objectifs

100.2

100.4

100.6

100.8

101

101.2

100.2 100.4 100.6 100.8 101 101.2


x : performance sur x , y : performance sur θvaleur maximum : 101



Génération 220


100.2

100.4

100.6

100.8

101

101.2

100.2 100.4 100.6 100.8 101 101.2



100.2

100.4

100.6

100.8

101

101.2

100.2 100.4 100.6 100.8 101 101.2





Génération 320


100.2

100.4

100.6

100.8

101

101.2

100.2 100.4 100.6 100.8 101 101.2



100.2

100.4

100.6

100.8

101

101.2

100.2 100.4 100.6 100.8 101 101.2





Génération 420


100.2

100.4

100.6

100.8

101

101.2

100.2 100.4 100.6 100.8 101 101.2



100.2

100.4

100.6

100.8

101

101.2

100.2 100.4 100.6 100.8 101 101.2





Génération 520


100.2

100.4

100.6

100.8

101

101.2

100.2 100.4 100.6 100.8 101 101.2



100.2

100.4

100.6

100.8

101

101.2

100.2 100.4 100.6 100.8 101 101.2





Génération 620


100.2

100.4

100.6

100.8

101

101.2

100.2 100.4 100.6 100.8 101 101.2



100.2

100.4

100.6

100.8

101

101.2

100.2 100.4 100.6 100.8 101 101.2





Génération 720


100.2

100.4

100.6

100.8

101

101.2

100.2 100.4 100.6 100.8 101 101.2



100.2

100.4

100.6

100.8

101

101.2

100.2 100.4 100.6 100.8 101 101.2





Génération 820


100.2

100.4

100.6

100.8

101

101.2

100.2 100.4 100.6 100.8 101 101.2



100.2

100.4

100.6

100.8

101

101.2

100.2 100.4 100.6 100.8 101 101.2





Génération 920


100.2

100.4

100.6

100.8

101

101.2

100.2 100.4 100.6 100.8 101 101.2



100.2

100.4

100.6

100.8

101

101.2

100.2 100.4 100.6 100.8 101 101.2




Multi-critères et pression sélective

Intérêts du multi-critères :Obtention simultanée de l’ensemble des meilleurscompromisFacilite le maintien de diversitéPression adaptative



Intérêts du multi-critères :Obtention simultanée de l’ensemble des meilleurscompromisFacilite le maintien de diversitéPression adaptative



Pression adaptative : contexte d’une tâche "composite"









Pression adaptative : contexte d’une tâche "composite" [Mouret& Doncieux 2008]


Simulation vs réalité



Approche robotique réelle

Tout faire sur le robot réel :expériences de Floreano àl’EPFL→ Les caractéristiques durobot et de son environnementpeuvent être exploitées.Limitations : dispositifexpérimental, solutions initialesau comportementpotentiellement dangereuxpour le robot.



Approche robotique réelleEmbodied Evolution [Watson etal. 2002] :

population de robots réelsévaluation ducomportement enconditions réellessi efficace : envoi dugénotype aux robotsavoisinants



Principe de Miglino, Lund et Nolfi (1995)

Construction du modèle à partir de perceptions réellesAjout de différents types de bruits (gaussien, “conservatif”)Si différence entre les comportements simulation/réalité :réaliser quelques générations supplémentaires sur le robotréel...



Exemple : évitement d’obstacles sur un robot Khépéra

Mesure des perceptions réelles du Khépéra pour 180orientations et 20 distances différentes par rapports auxdeux types d’objets de l’environnement (murs et obstaclescirculaires)Si plusieurs obstacles : sommation des perceptions3 conditions :

Pas de bruitbruit blancbruit “conservatif” : on considère les perceptions en unpoint x + δx , y + δy



Exemple : évitement d’obstacles sur un robot KhépéraRésultat (par ordre décroissant des meilleures fitness) :

1 Sans bruit : baisse des performances lors du passage auréel

2 Avec bruit blanc : baisse faible des performancesmoyennes, très faible pour le meilleur contrôleur

3 Avec buit conservatif : aucune différence (voire meilleuresperformances)

Problème : mesures des perceptions réelles du robot pourconstruire le modèle très fastidieuses...



Principe de Jakobi et de la simulation minimale (1997)

Définition d’un ensemble d’interactions de base et d’unensemble d’aspects liés à l’implémentationRéalisation de la simulation :

interactions de base : modélisées depuis des mesuresréelles et ajout d’un bruit faibleaspects liés à l’implémentation : implémentation variabled’un test à l’autre

Force l’évolution à ne pas exploiter de caractéristiques peurobustesLimitation implicite : seuls les phénomènes physiquesprécisément simulés pourront être exploités...



Exemple : Choix d’une direction en fonction d’une lumière









Approche mixte Simulation/Réalité.Commencer en simulation et finir en réalité :

Recherche initiale rapideAjustement final sur le système réel

→ pose moins de problèmes car les comportements évaluéssur le système réel sont, a priori, plus proches de celui attenduet donc moins dangereux...



Dans les approches précédentes, frontière nette entre lasimulation et la réalité : principes généraux de conception de lasimulation

Pas d’exploitation des capacités adaptatives de l’évolution !Ce que l’on pourrait espérer :

passage automatique simulation-réalitéadaptation automatique du modèleadaptation en ligne du comportement à des changementsde contexte


















Passage automatique simulation réalité

Évaluation mixte en simulation et sur le systeme réel



Anytime Learning [Schultz et Grefenstette 2003]









Adaptation automatique du modèle

La différence entre l’évaluation en simulation et sur le systèmeréel peut guider l’adaptation du modèle : erreur à minimiser,approche "Back to reality" [Zagal et al. 2004]



Adaptation automatique du modèle

Co-évolution système-test (Estimation-Exploration Algorithm :EEA) [Bongard et Lipson 2005]



Robots résilients [Bongard etal. 2006] :

contruction d’un modèleinterne par AE : applicationau robot réel des actionsles plus discriminantesoptimisation ducomportement sur lemodèle obtenuapplication au robot réelretour à la phase demodélisation



L’avenir est à la co-évolution modèle-comportement !

Mais il reste du travail :problème des capteurs : quel retour d’information du réel ?problème de la représentation de l’environnement


Que faire évoluer ?



À définir pour concevoir un système à l’aide algorithmeévolutionniste :

Fitness et évaluationCodage génétiqueOpérateur de mutationOpérateur de croisement



Paramètres du robotContrôleCapteursMorphologie complète


Que faire évoluer ?Paramètres


Évolution de paramètres

Approche AE classique (algorithmes génétiques, stratégiesévolutionnistes).

Optimisation du Black Widow[Grasmeyer 2001]

Évolution des paramètres ducontrôleur de l’Aibo [Hornby2000]


Que faire évoluer ?Contrôle


Évolution du contrôle

Principe : obtenir un programme capable de faire exhiber uncomportement désiré à un robot.Paradigmes exploitables :

“Programmes”Systèmes à base de règlesRéseaux de neuronesContrôleurs adhoc


Évolution du contrôle : programmes (sous formed’arbres)

Programmation génétique : principe



Programmation génétique : croisement



Programmation génétique : mutation

Mutation paramétriqueMutation structurelle :

pas systématiquement utilisée...consiste à remplacer un sous-arbre par un autre généréaléatoirementsouvent couplé à une grammaire permettant de restreindreet d’orienter la recherche vers des solutions pertinentes



Programmation génétique : exemplesÉvolution d’un contrôleur debattement d’ailes [Augustssonet al 2002] Évolution d’un programme

assembleur pour un Khépera[Nordin & Banzhaf 1997 ]


Évolution du contrôle : systèmes à base de règles

Principe : ensemble de règles “Conditions→ actions”

Les conditions portent sur les valeurs de capteurs ou surun état interneLes actions sont envoyées aux effecteurs ou modifientl’état interne

Systèmes à base de règles floues & systèmes de classeurs



Systèmes à base de règles floues.La logique floue est utilisée sur les parties :

condition et action (règles de Mamdani)condition seulement, action = fonction linéaire des entrées(règles Takagi-Sugeno-Kang ou TSK)

0

1Loin

3m2,50m



Qu’est-ce qui évolue là-dedans ?Le découpage en ensembles flous de l’espace desconditionsLes paramètres des actions (ensembles flous oucoefficients)



Comparé à des approches classiques du contrôle sur unhélicoptère :

contrôle linéaire robuste multi-variablenonlinear tracking controllogique floue avec réglage par évolution

Rôle de l’AE : optimiser les paramètres de règles flouesdéfinies manuellement.

[Shim & al 1998]



Résultats :performances très bonnes pour un vol quasi stationnaire(logique floue + évolution équivalent à contrôle linéairerobuste multi-variable)perturbations et incertitudes sont bien géréesle contrôle non linéaire est plus efficace sur un domaineplus large (mais nécessite une connaissance très précisedu système...).

Conclusion : Solution compétitive. Cependant l’évolution n’avaitqu’un rôle très faible, que se passe-t-il si on lui laisse plus delatitude ?



Principe des systèmes de classeurs.règles du type : 010#1#→ 110Actions : valeurs binaires envoyées aux actuateursConditions : valeurs issues des capteurs, langage ternaire

0 : capteur inactif1 : capteur actif# : valeur indifférente

La condition est un ET logique entre toutes les valeurs descapteurs.Exemple : 010#1#→ règle active lorsque :

capteurs 0 et 2 inactifs

capteurs 1 et 4 actifs

capteurs 3 et 5 non prises en compte



Qu’est-ce qui évolue là-dedans ?→ chaînes binaires ou ternaires (taille fixe imposée), nombrede règles.2 familles principales de contrôleurs basées sur des systèmesde classeurs : approches Michigan et Pittsburgh

Approche Pittsburgh : la population est un ensemble decontrôleurs, qui sont eux-mêmes des ensembles de règlesApproche Michigan : la population est un ensemble derègles, les contrôleurs sont donc constitués de plusieursindividus.

Expériences de F. Flacher


Évolution du contrôle : réseaux de neurones

Σ

Fonction Entrées Sortied’activation

Calculdu potentiel

Réseau de neurones

Neurones d’entrée

Neuronesde sortie

Neurone

Définitions :Potentiel : potentiel demembraneActivation : valeur de sortiedu neurone


Évolution du contrôle : réseaux de neurones

Évolution d’un réseau de neurones :

structure fixe : évolution de paramètresstructure générée par l’AE :

permet de trouver des structures adaptées à un problèmeProblème : quelle représentation génétique pour unestructure de type graphe ? Enjeux :

quel espace de recherche ?comment l’explorer ?

→ objet du prochain cours !


Que faire évoluer ?Capteurs


Influence des capteurs sur le contrôle

Expérience des Didabots. Objectif : ranger l’arène, i.e.regrouper les cubes par tas.

[Maris & te Boekhorst 1996]



Première configuration

[Maris & te Boekhorst 1996] [Pfeifer 2000]



Seconde configuration

[Maris & te Boekhorst 1996] [Pfeifer 2000]


Évolution de capteurs

Objectifs : exploiter les caractéristiques des capteurs pourrésoudre une tâche a priori complexe avec un contrôleursimple.

Très efficace, mais plus difficile à mettre en oeuvre que del’évolution de contrôleur...


Évolution de capteurs

Évolution de la position de capteurs de lumière à donner enentrée de capteurs élémentaires de mouvement.

[Lichtensteiger & Eggenberger 1999]


Que faire évoluer ?Morphologie complète


Influence de la morphologie sur le contrôle

Asimo de Honda vs Denise de l’université de Delft


Évolution de la morphologie complète

Expériences de [Sims 1994] : évolution demorphologie-contrôle pour des robots dans un univers virtuelpour différentes tâches :

marchenagesautcompétition



Expériences de [Sims 1994] : évolution demorphologie-contrôle



[Sims 1994]



Projet Framsticks [Komosinski, Ulatowski 1998]



Projet Golem [Lipson, Pollack 2000]


Outils


Outils AE standards

AE standardsGaLib http ://lancet.mit.edu/ga/OpenBEAGLE http ://beagle.gel.ulaval.ca/EO http ://eodev.sourceforge.net/

AE & robotique

Darwin 2K http ://darwin2k.sourceforge.net/Framsticks http ://www.frams.alife.pl/findex.html


SFERESPlate-Forme logicielle d’évolution artificielle et de simulation.Utilisée dans toutes les expériences du projet ROBUR.Objectif : maximiser la réutilisation de code et accélérer ledéveloppement de nouveaux composants dans desexpériences de conception automatique de contrôleursd’agents simulés.

Evolution

Population

Evaluator

Chromosome

Fitness

Individual

Genome

Simulator

Agent

Sensor

Architecture

Effector

SimuFitness

Distribuée souslicence libreCeCILL. cfhttp ://sferes.lip6.fr


Problèmes ouverts

Évolution = génération d’un individu adapté

Objectif : tendre vers la génération d’individus adaptatifs.

Solution explorée : ajouter de l’apprentissage...

Autre avantage : meilleure exploitation du temps passé àl’évaluation.


Problèmes ouverts

Passage à l’échelle dans la complexité des comportementsgénérés : problème du “bootstrap”.

Objectif : générer par évolution des comportements decomplexité croissante.

Solution explorée : incrémentalité dans la complexité :approche de type co-évolution ou multi-critères.

Autre avantage : réduire la dépendance à la stratégied’évaluation.


That’s all folks...EMail : [email protected] web :

Page AnimatLab : http ://animatlab.lip6.frSite de l’ISIR : http ://www.isir.frSFERES : http ://sferes.lip6.fr

Documents

Approche Évolutionniste de la Robotique - Master … · Observation pendant la durée de vie Condensation des observations en un ou plusieurs critères ... La selection est basée