Embed Size (px)
Citation preview
Académie de Montpellier
Université Montpellier II- Sciences et Techniques du Languedoc -
Mémoire de Stage de Master 2
effectué au Laboratoire d’Informatique de Robotiqueet de Micro-électronique de Montpellier
Spécialité : Professionnelle et Recherche unifiée en Informatique
Apprentissage Supervisé en
Robotiquepar
Emmanuel PERALTA
Date de soutenance : 30 Juin 2009Sous la direction de Éric BOURREAU
2
Remerciements
Comme le veut la tradition je remercie mon maître de stage Eric Bourreau. Je tiens égalementà remercier Jean Sallantin pour l’intérêt qu’il a porté à mon travail ainsi que pour ses nombreusesidées. Je remercie également Sebastien Lengagne et Fréderic Kamara pour leur précieuse aideen robotique et sans qui l’expérience Hoap ne se serait pas réalisée. J’adresse mes plus sincèresremerciements à mes voisins de bureau Richard et Samuel. Je remercie également Caroline pourm’avoir soutenu (d’aucuns diraient supporté) durant ce stage au LIRMM.
3
4
Table des matières
1 Introduction 9
2 État de l’art 132.1 Architectures logicielles de contrôle . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.1.1 Architectures comportementales . . . . . . . . . . . . . . . . . . . . . . . 132.1.2 Architectures délibératives . . . . . . . . . . . . . . . . . . . . . . . . . . . 142.1.3 Architecture hybride . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2 Séquence de pas d’un robot humanoïde . . . . . . . . . . . . . . . . . . . . . . . . 152.3 Robotique Autonome . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3 Programmation par Contraintes 173.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173.2 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4 STRIPS 194.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
5 Module de planification 215.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215.2 Modèle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
5.2.1 Définitions liminaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225.2.2 Définition du Modèle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
5.3 Actions parallèles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245.3.1 Compatibilité entre actions . . . . . . . . . . . . . . . . . . . . . . . . . . 245.3.2 Parallélisme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245.3.3 Implémentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
5.4 Actions compilées . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
6 Waterbucket 296.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
6.1.1 Définition du Problème . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306.2 Description du modèle original . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306.3 Résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
7 Tribot 337.1 Présentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
7.1.1 Programmation du Tribot via Urbi . . . . . . . . . . . . . . . . . . . . 347.2 Actions Élémentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
5
7.2.1 Discrétisation des Valeurs des Capteurs . . . . . . . . . . . . . . . . . . . 357.2.2 Actions parallèles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357.2.3 Communication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
7.3 Autonomie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367.3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367.3.2 Expérience . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 387.3.3 Mémoire Episodique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 387.3.4 Apprentissage sur la mémoire épisodique . . . . . . . . . . . . . . . . . . . 39
7.4 Couplage avec Intègre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
8 Hoap 418.1 Présentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 418.2 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 428.3 Descripteurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
8.3.1 Capteurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 428.3.2 Moteurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
8.4 Actions élémentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 438.5 Commande du Hoap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
8.5.1 Serveur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 448.5.2 Expérience . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
9 Conclusion & Perspectives 47
10 Annexes 49
6
Table des figures
1.1 Schéma de plate-forme “Classique” selon Brooks [Bro85]. . . . . . . . . . . . . . 101.2 Lien entre Actions et Perceptions. . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.1 Schéma d’organisation des architectures comportementales. . . . . . . . . . . . . 132.2 Schéma d’organisation des architectures délibératives. . . . . . . . . . . . . . . . 142.3 Aperçu de l’algorithme mis en place par Kuffner. . . . . . . . . . . . . . . . . . . 15
5.1 Schéma UML du kernel. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215.2 Préconditions et postconditions de a0 et de a1. . . . . . . . . . . . . . . . . . . . 265.3 Précondition de a1 à filtrer. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265.4 Postcontion de a0 à filtrer. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265.5 Filtrage des préconditions et des postconditions qui dépendent d’une postcondition. 275.6 Action compilée (a0, a1). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
6.1 Capacités des vases. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296.2 Etat initial. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296.3 Exécution de l’action DumpAtoB. . . . . . . . . . . . . . . . . . . . . . . . . . . 306.4 Etat final désiré. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306.5 Temps et nombre de noeuds pour la résolution du plan de taille 7 pour le waterbucket-
3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316.6 Temps et nombre de noeuds pour la résolution du plan de taille 8 pour le waterbucket-
4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
7.1 Equivalence entre Moteurs et leurs objets Urbi. . . . . . . . . . . . . . . . . . . . 347.2 Equivalence entre Capteurs et leurs objets Urbi. . . . . . . . . . . . . . . . . . . 347.3 Lego Nxt Mindstorm Tribot. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347.4 Equivalence entre Capteurs et leurs objets Urbi. . . . . . . . . . . . . . . . . . . 357.5 Interaction entre Apprenti et Instructeur. . . . . . . . . . . . . . . . . . . . . . . 377.6 L’Apprentissage influe les perceptions. . . . . . . . . . . . . . . . . . . . . . . . . 377.7 Arbre de décision Weka. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 397.8 Production de diagnostic par simulation d’action. . . . . . . . . . . . . . . . . . . 40
8.1 Le Hoap-3 de Fujitsu. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 418.2 Communication avec le module temps réel. . . . . . . . . . . . . . . . . . . . . . 428.3 Arbre de décision Weka. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 438.4 Serveur d’envoi de commandes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
7
8
Chapitre 1
Introduction
La robotique autonome est un sujet de recherche fréquemment abordé depuis une dizained’années, l’approche des roboticiens et automaticiens est de chercher à calculer et modéliser lemonde au travers de modèles mathématiques et physiques complexes. Si l’on raisonne par an-thropomorphisme lorsque l’on marche on ne calcule pas de dérivée ou de ZMP1
Nous allons donc développer une architecture où ces lois physiques sont considérées commeapprenables. Dans la seconde partie de sa thèse Mathias Paulin [Pau08] défini une plate-forme,comprenant différents composants : une plate-forme d’acquisition automatique des actions élé-mentaires, un module de planification et un module de supervision.
La partie acquisition automatique des actions élémentaires se fait au travers d’expérimenta-tions, le résultat de ces expérimentations se présente sous la forme d’un log des capteurs durantl’exécution de l’action. Nous fournissons ces instances (on aura préalablement étiqueté ces tuples)à Conacq [CBQ03] qui modélise ces actions élémentaires sous forme de réseau de contraintes.
Une fois cette phase d’acquisition [PBDK06] faite, le module de planification utilise ces actionsélémentaires comme briques de base pour construire une séquence d’actions afin de satisfaire unbut.
Cette architecture est à rapprocher de ce que Brooks [Bro85] qualifie de plateforme “classi-que”.
1Le Zero Moment Point est le point de jonction entre l’axe inertiel et le sol. Dans un cas simple d’un robot bipèdemarchant sur sol horizontal, cet axe inertiel est définit comme étant l’axe porteur de la somme de l’accélérationdu robot et de son poids.
9
Actionneurs
Capteurs
Perception
Modélisation
Planification
Exécution de tâche
Contrôle des moteurs
Fig. 1.1 – Schéma de plate-forme “Classique” selon Brooks [Bro85].
La partie Modeling correspond à l’étape de symbolisation via Conacq, la partie TaskExecution et Motor Control correspondent au module de supervision et les modules dePlanning et de Perception au module de planification.
La plate-forme de Mathias Paulin permet donc un lien entre les Action les Perceptions [PBDK06].Le module de Diagnostic (planificateur) produit une séquence d’actions élémentaires en fonctiondes perceptions, cette séquence d’action est ensuite réalisée par le module de Supervision, quienvoie des ordre sensorimoteurs à faire executer par le module d’Action (Urbi dans le cas duTribot) et le module de perception via urbi renvoie une information capteur (c.f. figure 1.2).
10
DiagnosticPerceptions
SupervisionActions
Fig. 1.2 – Lien entre Actions et Perceptions.
Dans la première partie de ce mémoire nous nous intéresserons à la planification d’actionsélémentaires via la résolution d’un réseau de contraintes. Ce planificateur est un dérivé de C-Plan [vBC99] avec quelques idées reprises de GraphPlan [LB03, BF97]. Ce plan reste théoriqueet sa réalisation va se heurter à la réalité du monde, c’est à dire que l’exécution de ce plan va êtreperturbée. Par exemple si le robot exécute l’action Avancer(20cm) il va avancer d’environ 20centimètres mais pas exactement la réalisation du plan diverge du plan original à chaque exécu-tion d’action. Pour lutter contre cet état de fait deux mécanismes sont mis en place la correctionmineure et la re-planification.
La correction mineure Avancer(20cm);Avancer(20cm) lorsque la première action s’est exé-cutée le robot à avancé de 17 centimètres la correction mineure modifie la distance à parcourirde la seconde action par propagation Avancer(23cm) pour prendre en compte l’erreur.
Lorsque l’erreur n’est pas absorbable par la suite du plan, on effectue un nouvelle passe deplanification.Nous allons mettre en place deux mécanismes afin de permettre au robot d’être plus efficace :
– La parallélisation des action permet au robot d’être plus efficace dans la satisfaction deson but. En effet la durée d’exécution du plan s’en retrouve plus courte et donc on dépensemoins d’énergie ;
– La compilation d’action fréquente permet de diminuer la complexité de la passe de la pla-nification ;
Au travers d’expérimentation on constitue une mémoire épisodique dans laquelle on stocke latrace de descripteurs tout au long de l’expérience, le résultat de l’expérience, le plan théorique,les re-planifications, et l’exécution des actions. Cette mémoire peut être qualifiée de mémoireautiste car il n’y a pas de mécanisme d’oubli, de généralisation.
Nous mettrons en place un apprentissage minimal sur cette mémoire épisodique.Et enfin nous tenterons de réaliser une expérience sur le robot Hoap-3 en collaboration avec
les roboticiens. Dans cette expérience le robot va suivre une cible et tenter de minimiser sadistance à la cible afin de montrer l’indépendance de l’approche par rapport au robot.
11
12
Chapitre 2
État de l’art
2.1 Architectures logicielles de contrôle
2.1.1 Architectures comportementales
Les architectures comportementales se basent sur l’architecture proposée en 1985 par RodneyBrooks [Bro85] qu’il nomme “subsumption architecture” (c.f. figure 2.1). Ces architectures sontcomposées de plusieurs modules de comportement, que l’on appelle réactifs car ils associent à unétat, une commande moteur.
Module d'arbitrage
Couche Robot
DonnéesCapteurs
Asservissementdes Moteurs
Comportements
boucle de traitements
Fig. 2.1 – Schéma d’organisation des architectures comportementales.
Ces architectures sont issues de l’observation des comportements des animaux et sont axéessur l’idée qu’un comportement complexe peut émerger d’une composition de comportements ré-actifs simples. Chaque comportement réactif est défini de manière indépendante, il faut donc unmodule d’arbitrage afin d’éviter d’exécuter des comportements contradictoires.
13
Le principal enjeu de ces architectures est de définir la ou les bonnes règles d’arbitrage,permettant au robot de se comporter de façon cohérente face à la tache qu’il a à accomplir.
2.1.2 Architectures délibératives
Les architectures délibératives (c.f. figure 2.3), parfois dénommées architectures hiérarchisées,centre la conception sur le système décisionnel.
Les architecture délibératives sont historiquement les premières à avoir été proposées [Nil80].Ces architectures sont généralement organisées en plusieurs couches hiérarchisées. Chaque
couche ne communique qu’avec la couche ayant le niveau hiérarchique directement supérieur etavec la couche ayant le niveau hiérarchique directement inférieur.
Couche décisionelle
Couche éxecutive
Couche fonctionelle
Robot
DonnéesCapteurs
EtatDiscrétisé
EtatDiscrétisé
Décision àexécuter
Action àexécuter
Commandemoteur
Fig. 2.2 – Schéma d’organisation des architectures délibératives.
Ces architectures sont composées en général de trois couches :– une couche fonctionnelle chargée de la gestion et la symbolisation de la perception ainsi
que de l’asservissement des moteurs en fonction des ordres de la couche exécutive ;– une couche exécutive chargée de la supervision de l’action à accomplir, par exemple se
rapprocher de son biberon ;– une couche décisionnelle chargée de gérer la planification des actions du robot ;Les données capteurs remontent verticalement de la couche fonctionnelle vers la couche déci-
sionnelle, en traversant toutes les couches intermédiaires.
Le principal problème de cette architecture est que cette séparation en couche impliquentque les fonctionnalités de la couche décisionnelle doivent se décomposer en éléments de plus basniveau à chaque couche traversée, avant d’arriver à la commande. Ce transfer d’information entreles différentes couches, pose un problème de réactivité de l’architecture.
En effet chaque transfer d’information inter-couche induit une latence d’autant plus impor-tante que le nombre de couches est grand.
14
2.1.3 Architecture hybride
Comme nous venons de le voir les architectures comportementales et délibératives sont deuxapproches très différentes, voire opposées. Elles présentent donc des avantages et des défautscomplémentaires, il était donc naturel que l’on tente de synthétiser les qualités de chaque archi-tecture.
La définition des architectures hybrides, dans lesquelles on cherche à prendre en compteles aspects décisionnels et réactifs, tente de combiner les aspects les avantages des architecturedélibératives et comportementales.
Les architectures hybrides intègrent ainsi une hiérarchisation des couches permettant la sym-bolisation, et donc la prise de décision (i.e. planification haut niveau, gestion de mission, etc.),à laquelle s’ajoutent des boucles réactives imbriquées permettant à chaque couche de fournir desréactions adaptées à sa dynamique et la réalité opérationnelle du robot. On distingue ainsi deuxentités principales :
– Un panel de comportements (les modules temps réels d’execution de fonction sensorimo-trices et de perception ;
– Un mécanisme de choix du ou des comportements actifs ;
2.2 Séquence de pas d’un robot humanoïde
En robotique Humanoïde le problème de la marche est le sujet de nombreux travaux, on peutnotamment citer les travaux de James Kuffner [JKK+01].
Dans ces travaux James Kuffner utilise l’algorithme RRT [JL00]1 afin de planifier une trajec-toire sans collision, et dynamiquement stable pour le robot.
Planificateur de mouvements
Recherche de chemins RRT
Vérification des collisions
PostureInitiale
Posturefinale
Gestion dynamique de
l'équilibre
Lissage de trajectoire
Trajectoiresolution
Fig. 2.3 – Aperçu de l’algorithme mis en place par Kuffner.
Cette methode est une methode continue au contraire de notre methode qui est une methodediscrète.
1Rapidly-exploring Random Trees.
15
2.3 Robotique AutonomeLa robotique autonome est un sujet fréquemment abordé. On peut aborder les travaux de
Masashiro Fujita [FK98] avec AIBO.AIBO est un robot quadrupède doté d’une architecture de contrôle comportementale nommée
Emotion System [FK98], où chaque comportement est arbitré par le module de supervision enfonction de “l’état émotionnel” du robot.
Les travaux de Martin Bush [BKL+] dans lesquels un robot mobile à été capable d’atteindreun lieu sans GPS, ni carte simplement en demandant son chemin aux passants.Une architecture de robot autonome à également été proposée par la NASA, cette architectureest une architecture hybride, qui utilise le langage Lisp pour des raisons de robustesse2 [PB98].
2Dans le sens sécurité face au dépassement de tampon et de transtypage.
16
Chapitre 3
Programmation par Contraintes
3.1 Introduction
La programmation par contraintes à été formalisée en 1974 par Montanari [Mon74] et en1977 par Mackworth [Mac77]. La programmation par contraintes est utilisée pour résoudre desproblèmes d’affectation de valeurs à des variables. Ces variables sont liées entre elles par desrelations que l’on nomme contraintes.
Cela revient à poser un problème sous forme de relations logiques entre plusieurs variables.Un problème à résoudre comporte un ensemble fini de variables. Chacune des variables possèdeun domaine et un certain nombre de contraintes, le domaine des variables peut être discret oucontinu. Dans le cadre de nôtre approche on ne manipule que des réseaux de contraintes discrets.
3.2 Définitions
Définition 1 (Réseau de contraintes) Un réseau de contraintes R est un triplet (X ,D, C)où :
– X = {x1, . . . , xn} est l’ensemble des variables du problème ;– D = {d(x1), . . . , d(xn)) est l’ensemble des domaines des variables du problème. Chaque
variable x prends ses valeurs dans d(x) ;– C = {c1, . . . , cm} est un ensemble de contraintes sur X . Une contrainte c est définie un
ensemble de variables que l’on note var(c), et une relation sur ses variables que l’on noterel(c) qui spécifie les tuples autorisés par la contrainte.
Une contrainte est dite binaire lorsqu’elle implique exactement deux variables. Un réseau decontraintes est dit binaire lorsque l’ensemble C ne contient que des contraintes binaires.
Définition 2 (Instanciation) Soit Y = {y1, . . . , yk} où Y ⊆ X une instanciation EY de Y estun k-uplet (v1, . . . , vk) ∈ (D1 × . . .×Dk). On dit que l’instanciation est complète lorsque Y = X(cette instanciation sera notée E).
Une instanciation EY viole la contrainte c ∈ C si et seulement si
var(c) ⊆ Y, EY [var(c)] 6∈ rel(c)
17
Définition 3 (Solution) Une solution est une instanciation complète telle que ∀c ∈ C, E [var(c)] ∈rel(c). On note l’ensemble des solution d’un réseau S(R), ou S(X ,D, C).
18
Chapitre 4
STRIPS
STRIPS (ou STanford Research Institute Problem Solver) est un algorithme de Planificationclassique conçu par Richard Fikes et Nils Nilsson en 1971 [FN71]. L’algorithme de STRIPS estassez basique, mais il est intéressant comme exemple pédagogique. On nomme aussi par ce nomle langage de représentation des données utilisée par l’algorithme. Avec le GPS (General ProblemSolver) de Newell et Simon de 1961, il fait partie des premiers planificateurs utilisés en intelligenceartificielle et été suivi de nombreux dérivés (GraphPlan, IPP, STAN, etc).
4.1 DéfinitionsDéfinition 4 (pre(ai)) pre(ai) représente l’ensemble des préconditions de l’action ai
pre(ai) = {c0, . . . , ck}
où k est le nombre de contraintes composant la précondition.
Définition 5 (post(ai)) post(ai) représente l’ensemble des postconditions de l’action ai
post(ai) = {c0, . . . , ck}
où k est le nombre de contraintes composant la postcondition.
On préférera représenter les contraintes comme un ensemble de contraintes binaires plutôtque comme une conjonction afin de pouvoir plus facilement filtrer des contraintes notammentlors de la compilation de séquence d’action.
Définition 6 (modified(ai)) modified(ai) représente l’ensemble des descripteurs modifiés parl’action ai.
19
20
Chapitre 5
Module de planification
5.1 Introduction
La première partie de notre travail a été de retravailler le module de planification utilisé parMathias Paulin était très lié à la plateforme Tribot, utilisait la bibliothèque Choco 1, et peuréutilisable. En conservant l’interface de programmation, nous avons réalisé un nouveau modulede planification utilisant la bibliothèque Choco 2 1.
Les principales structures du module de planification (c.f. figure 5.1) sont :– StandardPlanningModel ;– StandardPlanningSolver ;– Descriptor ;– Action ;– MetaConstraint ;– Mutex ;
Cette interface de programmation mime celle de Choco, mais là ou le modèle Choco manipuledes variables et des contraintes, le modèle de planification manipule des Actions sur lesquellesportent des Mutexes et des des Descripteurs sur lesquels portent des Meta Contraintes.
AbstractPlanningModel AbstractPlanningSolver
StandardPlanningSolverStandardPlanningModelWaterbucketModel
IAction IDescriptorMetaConstraintMutex
Fig. 5.1 – Schéma UML du kernel.
1http ://www.emn.fr/x-info/choco-solver/doku.php
21
5.2 Modèle
Dans cette partie nous présenterons en détail le modèle utilisé pour la résolution du pro-blème de planification, ce modèle est issu des travaux de Peter van Beek [vBC99] et d’AdrianaLopez [LB03]. Dans ces travaux le graphe de planification est représenté sous forme d’un réseaude contraintes.
5.2.1 Définitions liminaires
En analysant les préconditions et les postconditions des actions on peut déterminer si ellespeuvent être exécutées en parallèle (technique analogue à celle de détections des Mutexes [LB03])
Définition 7 (Problème de planification) Résoudre le problème planification revient à trou-ver la séquence S d’actions qui permet la transition entre l’état initial Ei et l’état final Ef .
EiS−→ Ef
Conformément au Base-CSP [LB03] on teste les séquences d’actions de taille 0 à n. Onconserve le plan de taille 0 car l’état initial Ei peut être conforme à Ef
Ei ∼ Ef
Il faut donc en utilisant n actions élémentaires parvenir à l’état final.
E0a0−→ E1
a1−→ E2 . . . En−1an−−→ Ef
Nous allons dans la partie suivante définir le modèle de résolution du problème de planifica-tion.
5.2.2 Définition du Modèle
Dans le module de supervision de Mathias Paulin [Pau08] les états initiaux et finaux sontcontraints par des contraintes d’égalité. Cette représentation des états limite les buts que l’onpeut donner au robot, pour palier à ce problème nous définissons les Meta contraintes.
Meta contraintes
Afin de pouvoir poser des contraintes plus variées sur les états initiaux et finaux (c’est à direplus variées que la simple égalité), nous avons défini un ensemble de meta contraintes qui sontinstanciées par le solver. Elles portent sur les variables de l’état final ou initial du réseau decontraintes représentant le problème de planification.
Définition 8 (Meta Contrainte) On peut voir une meta contrainte comme une fonction quiassocie un état E, un ensemble de descripteurs D = d0, . . . , dn, ainsi qu’une contrainte et qui as-socie une contrainte portant sur les variables de l’état E correspondant à l’ensemble de descripteurD.
metacontrainte(E ,D0, . . . ,Dn) : E × Dn → C(e, (d0, . . . , dn)) → c(E(d0, . . . , dn))
22
Définition des Variables
Pour modéliser le problème de planification de longueur k nous définissons k + 1 ensemblesde variables descripteurs que nous nommerons états.
L’état à l’étape s, Es est définit ainsi Es = {ds0, . . . , d
sn} ou ds
0 représente le descripteur 0à l’étape s, le domaine de chaque variable descripteur di ∈ [min(di),max(di)]. L’ensemble desactions A = {a0, . . . , am} pour chaque étape du plan s on définit une variable actions dontle domaine est l’ensemble des indices des actions contenues dans A (as ∈ [0,m]). actions =index(ae) est vraie si l’action ae permet la transition entre Es et Es+1, donc entre les étapes s ets + 1 du plan.
Algorithme 1 Methode de définition des variables.defineVariables
model, stepfor all descriptor ∈ descriptors do
model.addV ariable(descriptor.getName()+step, descriptor.getMin(), descriptor.getMax()end forfor all action ∈ actions do
model.addV ariable(”a” + step, 0, actions.size()− 1)end for
Définition des Contraintes
Tout d’abord il faut imposer des contraintes sur l’état initial Ei et l’état final Ef (i = 0 etf = k + 1). Ici l’état initial nous est donné par l’utilisateur (Etat du robot, ou état du monde)sous forme d’un ensemble de meta contraintes ainsi on instancie les méta contraintes portant surl’état initial2. Il faut également instancier les méta contraintes portant sur l’état final.
Ensuite pour chaque étape une action ai ∈ A ne peut être exécutée entre les pas s et s + 1que si sa précondition sur Es est vraie, comme l’on veut être en mesure d’exécuter une action àtoute étape du plan, pour chaque action nous ajoutons la contrainte (as = i) ⇒ pre(ai, Es) (laprécondition de l’action ai appliquée à l’état Es).
Pour finir on instancie les exclusions mutuelles Mutex(Actiona1, Actiona2, Integerordre)sous la forme (ai = a1) =⇒ (ai+ordre 6= a2)
Ainsi défini le modèle est semblable au Base-CSP défini par Lopez [LB03] avec une extensionaux variables non booléennes3. Les architectures de planification et de supervision sont capablesde planifier et d’exécuter des actions en parallèle.
Algorithme 2 defineConstraint(step, model)for all i ∈ [0,m] do
model.add(implies(eq(action[i], i), action.getPrecondition(state(step))))model.add(implies(eq(action[i], i), action.getPostcondition(state(step), state(step + 1))))
end for
2On notera que si un état initial n’est pas suffisamment contraint, le solveur choisira des valeur pour lesvariables de l’état initial et donc mènera à des résultats inattendus
3ce qui posera problème pour la compilation automatique d’action sans reformulation
23
5.3 Actions parallèles
5.3.1 Compatibilité entre actions
On à ensuite besoin de définir la compatibilité entre actions afin de caractériser les conditionssous lesquelles deux actions sont exécutables en parallèle.
Définition 9 (Compatibilité entre deux actions) On dit que deux actions sont compatiblessi et seulement si il existe une instanciation complète pour pre(ai)∧pre(aj) et post(ai)∧post(aj).
La compatibilité entre deux actions et une condition nécessaire mais pas suffisante la définitionde l’opérateur ‖ permet de poser la dernière condition.
5.3.2 Parallélisme
Proposition 5.3.1 (Opérateur ‖) deux action ai et aj sont exécutables en parallèle (on lenotera ai ‖ aj) si et seulement si :
ai est compatible avec aj
modified(ai) ∩modified(aj) = ∅
rapide démonstration :pre(ai), pre(aj) doivent être compatible (il existe un support pour pre(ai)∧pre(aj)). post(ai),
post(aj) doivent être également compatibles.Le fait que les préconditions et les postconditions soient compatibles ne garanti pas que les
actions soient parallélisables.En effet si l’on pose i = j les préconditions et les postconditions sont évidemment compatible
mais ai et aj ne sont pas indépendantes car elles modifient les mêmes descripteurs. il faut alorsajouter une dernière condition qui est que les ensembles de descripteurs modifiés par ai et aj
doivent être disjoints.
5.3.3 Implémentation
Avant la résolution du problème de planification, on teste pour couples d’action non symé-triques, par résolution d’un réseau de contraintes. Soient Ei et Ef deux états non contraints (ie.sans meta contraintes), on ajoute les contraintes pre(a, Ei)∪pre(b, Ei) et post(a, Ef )∪post(b, Ef ).Si il existe une solution à ce réseau de contraintes les deux actions sont compatibles.
Eia,b−−→ Ef
5.4 Actions compilées
Les actions compilées sont des séquences d’actions fréquentes que l’on compile en une seuleaction, cela permet de réduire la longueur des plans et donc de réduire le temps de calcul decelui ci [YT89]. Dans le cas d’actions dont les préconditions et les postconditions ne sont pas desconjonctions de prédicats simples il faut utiliser la plate-forme Conacq afin de ré-acquérir leréseau de contraintes représentant cette action à partir des données expérimentales de l’exécutionde la séquence d’action.
24
Algorithme 3 parallelActions(actions)m = length(actions)for all i ∈ [0,m] do
for all j ∈ [i,m] doif compatibles(actions[i], actions[j]) then
model.add(a)model.add(b)model.add(initialState)model.add(finalState)model.add(implies(eq(a, i), action.getPrecondition(initialState)))model.add(implies(eq(b, j), action.getPostcondition(initialState, finalState))s.read(model)s.solve()if s.hasSolution() then
parallelActions.add(newParallelAction(actions[i], actions[j]))end if
end ifend for
end for
Définition 10 (opérateur u) L’opérateur u travaille sur un ensemble C de contraintes et unensemble V de variables. Cet opérateur permet de filtrer les contraintes dont une ou plusieursvariables appartiennent à l’ensemble V .
C u V ⇔ C ′ = {∀(c, v) ∈ C × V, v 6∈ var(c)}
Définition 11 (Précondition d’un mouvement compilé) Grace à l’opérateur u on peut dé-finir la précondition d’un mouvement compilé. Voici un exemple du calcul d’une préconditiond’une action compilée d’ordre 3.
Pre(Comp) = pre(a) ∪ pre(b) umodified(a) ∪ pre(c) u (modified(a) ∪modified(b))
s Et voici la forme générale du calcul de la postcondition d’un mouvement compilé.n∧
i=0
(pre(ai)
� [ i⋃j=0
modified(pre(aj))])
Définition 12 (Postcondition d’un mouvement compilé) Voici un exemple du calcul d’uneprécondition d’une action compilée d’ordre 3.
post(Comp) = post(c) ∪ post(b) umodified(c) ∪ post(a) u (modified(b) ∪modified(c))
Action = a0, . . . , an
Et voici la forme générale du calcul de la postcondition d’un mouvement compilé.
n∧i=0
(post(ai)
� [ n⋃j=i+1
modified(post(aj))])
25
Exemple 1 (Exemple de compilation de deux actions) Dans cet exemple on souhaite com-piler de façon automatique deux actions a0 et a1. Dans ce modèle l’ensemble de descripteurs est{A,B, C}. a0 possède des préconditions sur {A,B} et une postcondition sur {C} et a1 possèdedes préconditions sur {B,C} et des postconditions sur {B,C} (c.f. figure 5.2).
A
B
C
A
B
C
A
B
C
a0 a1
Fig. 5.2 – Préconditions et postconditions de a0 et de a1.
La précondition de a1 portant sur C est dépendante de la postcondition de a0 (c.f. figure 5.3).Cette contrainte ne peut pas apparaître dans la precondition de l’action compilée, car elle est enconflit avec la contrainte faisant partie de la postcondition portant sur C de a0.
A
B
C
A
B
C
A
B
C
a0 a1
Fig. 5.3 – Précondition de a1 à filtrer.
La postcondition de a0 portant sur C est par la suite modifiée par a1 (c.f. figure 5.4). Cettecontrainte ne peut pas apparaître dans la postcondition de l’action compilée, car elle est en conflitavec la contrainte portant sur C de la precondition de a1.
A
B
C
A
B
C
A
B
C
a0 a1
Fig. 5.4 – Postcontion de a0 à filtrer.
On filtre donc cette contrainte conflictuelle de la précondition de a1 et la contrainte conflic-tuelle de la postcondition de a0 (c.f. figure 5.5) et on effectue l’union ensembliste de l’ensemblede préconditions de a0 et de l’ensemble des préconditions restantes de a1 afin de construire laprécondition de l’action compilée (c.f. figure 5.6), on raisonne de manière analogue sur les post-conditions.
26
A
B
C
A
B
C
A
B
C
a0 a1
Fig. 5.5 – Filtrage des préconditions et des postconditions qui dépendent d’une postcondition.
A
B
C
A
B
C
comp(a0, a1)
Fig. 5.6 – Action compilée (a0, a1).
27
28
Chapitre 6
Waterbucket
6.1 Introduction
Le waterbucket est un problème très connu semblable au problème des tours de Hanoï. Ceproblème fait partie de la collection de problèmes CSPlib1.
8 5 3
Fig. 6.1 – Capacités des vases.
8 0 0
Fig. 6.2 – Etat initial.
1http ://www.csplib.org/
29
3 5 0
Fig. 6.3 – Exécution de l’action DumpAtoB.
4 4 0
Fig. 6.4 – Etat final désiré.
6.1.1 Définition du Problème
Nous avons trois vases (A,B, C) pouvant contenir respectivement 8, 5, 3 litres d’eau (c.f. fi-gure 6.1). A l’état initial le vase A est plein, il contient huit litres d’eau, et les deux autres vasesB,C sont vides (c.f. figure 6.2).
Il faut par transvasements (c.f. figure 6.3) successifs diviser en deux volumes égaux les huitlitres d’eau (ie. finir avec quatre litres dans le vase A et quatre litres dans le vase B) (c.f.figure 6.4).
Le problème du waterbucket nous a permis de mettre en place une infrastructure de test dumodèle de résolution du problème de planification, afin de limiter les problèmes de performancepour les expériences robotique.
6.2 Description du modèle original
Le modèle de résolution du problème de planification, représentait l’action exécutée à l’étapes de la séquence sous forme d’un vecteur de variables booléennes as
0, . . . , asn pour chaque variable
asi on définit les contraintes suivantes (as
i = 1) =⇒ pre(ai, Es) et (asi = 1) =⇒ post(ai, Es + 1)
30
6.3 RésultatsNous avons testé différentes combinaisons d’heursitiques de selection de variable avec les
différents modèles BaseCSP-MH2 et BaseCSP-EP3
Problème Heuristique Modèle Nombre nœuds Tempswaterbucket-3 DomOverWDeg BaseCSP-EP 47 134mswaterbucket-3 StaticVarOrder BaseCSP-EP 90 249mswaterbucket-3 StaticVarOrder BaseCSP-MH 236 440mswaterbucket-3 StaticVarOrder BaseCSP-MH+Mutexes 135 238mswaterbucket-3 DomOverDeg BaseCSP-MH 5086 6,5swaterbucket-3 DomOverWDeg BaseCSP-MH 22464 27s
Fig. 6.5 – Temps et nombre de noeuds pour la résolution du plan de taille 7 pour le waterbucket-3
On note que le nouveau modèle avec ses variables d’actions sur lesquelles portent plus decontraintes se prête bien à l’heuristique de sélection de variables DomOverWDeg4. On définit unsecond problème le waterbucket-4 qui possède un vase de plus d’une capacité de douze litresl’état initial {12, 0, 0, 0} et l’état final {4, 4, 4, 0}.
problème heuristique Modèle nombre nœuds tempswaterbucket-4 DomOverWDeg BaseCSP-EP 3146 15swaterbucket-4 StaticVarOrder BaseCSP-EP 7665 30swaterbucket-4 StaticVarOrder BaseCSP-MH 9739 38,7swaterbucket-4 StaticVarOrder BaseCSP-MH+Mutexes 6153 24,61swaterbucket-4 DomOverDeg BaseCSP-MH - -waterbucket-4 DomOverWDeg BaseCSP-MH - -
Fig. 6.6 – Temps et nombre de noeuds pour la résolution du plan de taille 8 pour le waterbucket-4
Ces mesures ont été réalisées sur un pentium 4 avec 512mb de mémoire vive5.
On note des résultats similaires pour le waterbucket-4 mais il reste encore des problèmes àétudier.
2Le planificateur de Mathias Paulin.3Le nouveau module de planification.4Domaine sur Dégrée5Sur une machine plus récente Macbook Pro, la résolution du problème wb-4 ne prends que 7s.
31
32
Chapitre 7
Tribot
7.1 Présentation
Le Tribot est produit par Lego son utilisation est principalement prévue pour une utilisa-tion de type jouet mais une société indépendante produit un kit de développement. Nous allonsprésenter plus en détail le robot.
Le Tribot possède 3 servomoteurs. Ils permettent au robot respectivement :– de commander les deux roues ;– de commander l’ouverture et la fermeture de la pince ;
Il dispose en plus de capteur :– un capteur de distance (à base d’ultrason) qui permet de détecter les objets se trouvant en
face du Tribot et de calculer la distance à cet objet (dans l’intervalle [0cm, 255cm]) ;– un capteur de niveau sonore (micro) qui permet d’estimer le bruit ambiant ;– un capteur de luminosité (qui peut être configuré pour capter la réflexion du sol, ou sa
couleur) qui permet de détecter le niveau de luminosité du milieu ;– un capteur de toucher ce qui permet au Tribot de détecter la collision avec un obstacle
(si ses pinces sont ouvertes) ;– un capteur de niveau de batterie qui indique l’état de charge de la batterie ([0, 1]) ;
Ces moteurs et ces capteurs sont connectés à la brique Lego qui contient un microcontro-leur et une mémoire de quelque kilos octets qui permet de stocker le firmware du robot ainsique les programmes envoyés au robot via le logiciel de programmation graphique de Lego. C’estce microcontroleur qui à en charge la commande des moteurs et le retour des valeurs des capteurs.
Le Tribot est un robot assez élémentaire, ne possédant qu’une gamme réduite d’actionneursil est cantonné à des actions relativement élémentaire1
La programmation du Tribot via l’interface graphique de Lego ne permet que des pro-grammes de type machine à états finis très simples. Une fois le programme conçu il est compilépuis envoyé sur la brique pour être exécuté.
1Les actions élémentaires des informaticiens sont rarement en adéquation avec les actions élémentaires desroboticiens.
33
7.1.1 Programmation du Tribot via Urbi
La société Gostai qui édite et maintient le langage Urbi2 propose, en libre téléchargementun kit pour le Mindstorm. Ce kit est composé d’un serveur qui utilise le driver du Mindstormafin de lui envoyer des comportement sensori-moteurs et récupérer les valeurs des descripteurset d’une partie client qui permet d’intégrer ces fonctionnalitées dans un programme.
Le langage Urbi présente diverses qualités :– Il est indépendant de la plate-forme (tant qu’il existe un serveur Urbi pour le robot.) ;– Il est facile à apprendre ;– Partiellement objet dans sa version 1.x ;– Il est interfacable avec plusieurs langages (C++, Java) ;– Il est orienté événements et traitements parallèles ;
Chaque composant du robot est représenté en Urbi par un objet.
Moteurs Objet UrbiMoteur de la roue droite wheelRMoteur de la roue gauche wheelL
Moteur de la pince claw
Fig. 7.1 – Equivalence entre Moteurs et leurs objets Urbi.
Capteur Objet UrbiCapteur de distance sonar
Capteur de niveau sonore soundCapteur de luminosité lightIndicateur de batterie battery
Fig. 7.2 – Equivalence entre Capteurs et leurs objets Urbi.
Fig. 7.3 – Lego Nxt Mindstorm Tribot.
2Universal Robot Behavior Interface
34
7.2 Actions Élémentaires
Le robot dispose des actions élémentaires suivantes :– OpenClaw, fermeture de la pince ;– CloseClaw, ouverture de la pince ;– CarrefullyMove, qui fait avancer le robot de 1cm à 20cm ;– StandardMove, qui fait avancer le robot à 30cm ;– FindTarget, qui cherche le biberon ;– Catch qui ferme la pince sur un objet ;
Ces actions élémentaires sont définies dans la seconde partie de la thèse de Matias Pau-lin [Pau08]
7.2.1 Discrétisation des Valeurs des Capteurs
Les valeurs des capteurs sont soit des réels, soit des valeurs entières dans un intervale borné.
Capteur Valeur Urbi Valeur discrétiséeCapteur de distance [0, 255] -
Capteur de niveau sonore [0.0, 1.0] 0 si sound < 0.8, 1 sinonCapteur de luminosité [0.0, 1.0] [Floor, F lying]Indicateur de batterie [0.0, 1.0] [0, 100]
Fig. 7.4 – Equivalence entre Capteurs et leurs objets Urbi.
Pour le capteur de luminosité3 on travaille sur la dérivée, ainsi si la dérivée est nulle on nechange pas d’état et lorsque la dérivée est négative on passe dans l’état Flying et lorsque elleest positive on passe dans l’état Floor4.
La discrétisation de sound et de light, nous permet de définir de nouvelles actions.
7.2.2 Actions parallèles
Dans le cas du tribot peu d’actions sont parallélisables. En effet ne possédant que troismoteurs (deux pour les roues, un pour la pince) seuls les mouvements impliquant d’une part lapince et d’autre part les roues peuvent être exécutés en parallèle.
Exemple :
Exemple 2 (Action parallèle OuvrirPince et Avancer)
OpenClaw/StandardMove = {pre = {distancei < 100 ∧ distancei > 20} ∪ {clawi = 0}post = {distancef < distancei − 20} ∪ {clawf = 1}}
Cette action est exécutée par Urbi en utilisant ses opérateurs de parallélisme, notamment le |qui impose que les deux actions soient exécutées exactement en parallèle.
3la valeur du capteur de luminosité augmente en fonction de la quantité de lumière reçue par le capteur.4Le capteur de Luminosité étant placé sous le robot on peut se servir de cette information afin de déterminer
si le robot est sur le sol ou non.
35
7.2.3 Communication
Deux nouvelles actions ont été rajoutées afin d’introduire une communication primitive avecle robot. La première Reset lorsque le robot est soulevé du sol coupe les moteurs. La seconde Badse déclenche lorsque le robot est soulevé et qu’on lui souffle dans le nez (ie. la valeur du capteursonore est 1), cela indique que l’expérience en cours doit être stoppée et étiquetée négativement.
Ces deux actions ont la particularité de ne poser aucune contrainte sur le but, ainsi le solveurpeut tout de même trouver une solution au problème, ici c’est sur le bumper que porte le butcomme il n’y a pas de contraintes sur le bumper, le domaine du bumper est 0, 1 la contrainteissue du but étant du type eq(bumperf , 1) le domaine s’en trouve réduit à 1. Le but est satisfaitau point du vue “modèle” en une action.
Définition 13 Reset
Reset = {pre = {lighti = FLY ING ∧ soundi = 0 ∧ instructeuri = 0}post = {}}
Définition 14 Bad
Bad = {pre = {lighti = FLY ING ∧ soundi = 1 ∧ instructeuri = 0}post = {}}
Définition 15 Help
Help = {pre = {lighti = FLOOR ∧ instructeuri = 1}post = {}}
7.3 Autonomie
7.3.1 Introduction
Tout d’abord commençons par donner une définition à l’autonomie.
Définition 16 (L’autonomie) L’autonomie demande :– L’interaction– L’apprentissage qui permet de fixer ses propres lois ;– L’abstraction production d’idées, de rêves ;
36
Interaction
DiagnosticPerceptions
SupervisionActions
: instructeur
Fig. 7.5 – Interaction entre Apprenti et Instructeur.
L’interaction avec un instructeur, utilise le paradigme “apprendre de l’autre” l’instructeurintervient lorsqu’il faut “punir” le robot.
Par exemple la conduite accompagnée, où le conducteur chevronné interagit avec le jeuneconducteur afin de corriger ses diagnostics.
Apprentissage
L’apprenti ne doit solliciter l’instructeur qu’a bon escient.
Diagnostic/ Planification
Perceptions/ Urbi
SupervisionActions/ Urbi
Apprendreà Prévoir l'echec
Fig. 7.6 – L’Apprentissage influe les perceptions.
Abstraction
L’abstraction permet de mettre en place une simulation d’actions coupées de la réalité, desperceptions. Cette abstraction met en place la fleche retour de Diagnostic -> Supervision ->Action, donc Action -> Supervision -> Diagnostic.
37
On peut noter qu’un formalisme semblable à été utilisé par Martin Bush [BKL+] et son équipedans un projet de robotique autonome ACE5.
7.3.2 ExpérienceDans l’expérience Tribot de Mathias Paulin [Pau08], le robot poursuit le mug de façon réac-
tive, tant qu’il est capable de produire un plan pour atteindre le mug il continue de le poursuivresans répit. On aimerai qu’il soit capable de prendre la décision de s’arrêter en fonction de qui estson instructeur.
Dans notre expérience on défini deux instructeurs le bon instructeur et le mauvais instructeur.Le but de cet expérience est d’arriver à distinguer le bon instructeur du mauvais, et lorsque
c’est le mauvais le Tribot arrete de poursuivre son biberon et demande de l’aide à son instruc-teur.
Définition 17 Bon instructeur Le bon instructeur ne déplace le biberon trois fois au maximum,et Tribot arrive à attraper le biberon.
Définition 18 Mauvais instructeur Le mauvais instructeur déplace sans cesse le biberon (doncplus de trois fois), et le Tribot est systématiquement puni après.
L’instructeur est donc défini comme une perception du robot, en effet c’est une perception qu’ilva au travers de l’apprentissage simuler afin de se passer de son instructeur.
Implémentation
On fourni au Tribot un nouveau descripteur supplémentaire l’Instructeur qui peut prendreles valeurs {0, 1} (0 lorsque l’instructeur est le gentil, 1 lorsque c’est le mauvais).
La valeur de ce nouveau descripteur est mise à jour au cours de l’expérience par un algorithmede classification afin de prédire l’issue de l’expérience. En prévoyant l’issue de l’expérience le robotest informé du type de l’instructeur. Lorsque le mauvais instructeur est détecté la seule actionqui doit pouvoir s’exécuter est NeedHelp pour cela il suffit d’ajouter aux préconditions des autresactions instructori = GOOD. La précondition de NeedHelp est quant à elle instructori = BAD.
7.3.3 Mémoire EpisodiqueLa mémoire épisodique peut être assimilé à une sorte de mémoire du robot. En effet il contient
la trace des expériences réalisées (dans notre cas l’expérience attraper le biberon).
Une première version de cette mémoire avait été réalisée en 2008 lors du TER du secondsemestre de Master première année.
La mémoire épisodique se présente sous la forme d’un fichier XML il contient dans le préam-bule, le plan d’origine, la liste des action utilisées et la liste de descripteurs. Dans la secondepartie il contient l’exécution du plan, pour chaque action exécutée le cahier de labo contientles descripteurs pré et post action ainsi que la “prévision”. Durant l’exécution du plan si unere-planification a lieu elle apparaît ainsi que le nouveau plan théorique.
Le résultat de l’expérience est + si le robot a réussi à saisir le biberon et - si il a été puni parl’instructeur.
5http ://ace-robot.de
38
7.3.4 Apprentissage sur la mémoire épisodiqueIntroduction
A partir de la mémoire épisodique il faut produire une règle permettant de caractériserl’instructeur.
Par souci de simplicité nous avons utilisé Weka[WF05] afin de pouvoir tester différents clas-sificateurs.Comme la règle à apprendre est de type fréquentielle, (on veut que le robot stoppe sa recherchede biberon lorsqu’il l’a déjà cherché trois fois (ie. frequence(FindTarget) > 3)). On transformedonc chaque expérience de la mémoire épisodique en un vecteur de fréquence dont la taille estle nombre d’action du robot, et ou chaque élément est le nombre de fois ou l’action est apparuedurant l’expérience.
On transforme la mémoire épisodique en un fichier ARFF dont les instances sont composéesde la fréquence d’apparition de chaque action à l’intérieur d’une même expérience et du résultatde cette expérience. Le résultat de l’expérience représente la classe de l’instance.
Résultats
Sur une mémoire épisodique comprenant 10 expérimentations J48 nous donne l’arbre dedecision suivant (c.f. figure 7.7) :
freq_FindTarget
- +
> 3 <= 3
Fig. 7.7 – Arbre de décision Weka.
Donc on a bien un système capable d’apprendre une règle.
7.4 Couplage avec IntègreIntègre est un logiciel développé par la société Normind, ce logiciel fonctionne sur la base
d’une ontologie, et de normes (règles). Ce couplage devrait permettre d’enrichir le module dedécision, et de mettre en place l’abstraction présentée.
Une action simulée produit un diagnostic, on peut faire un parallèle avec le rêve en effet cettesimulation coupe de la réalité d’exécution des action le module de supervision et le module dediagnostic(c.f. figure 7.8).
39
DiagnosticPerceptions
SupervisionActions
Fig. 7.8 – Production de diagnostic par simulation d’action.
40
Chapitre 8
Hoap
8.1 Présentation
Le Hoap-3 est un robot humanoïde fabriqué par Fujitsu depuis 2004. Hoap possède 28 degrésde liberté et plusieurs capteurs dont :
– Des capteurs de pression sous chaque pied ;– Un Télémètre placé sur la tête ;– Un Gyroscope et un Accéléromètre ;– Des capteurs de pression dans chaque main ;– Deux webcams dans la tête (les yeux) ;
Fig. 8.1 – Le Hoap-3 de Fujitsu.
L’expérimentation sur Hoap-3 était principalement pour lever certains verrous techniques surla programmation sur cette machine.
Le système d’exploitation du PC embarqué de Hoap-3 est un linux assez ancien (FedoraCore 1, 2003), utilisant le noyau temps réel RTLinux1(c.f. figure 8.2). L’absence d’interface deprogrammation, implique l’utilisation de lignes de commandes lancées sur le PC embarqué viatelnet.
La première étape du travail à été de constituer une interface de programmation minimalecapable :
– d’envoyer un mouvement articulaire via un fichier CSV contenant les positions à envoyeraux moteurs en fonction du temps ;
– d’envoi d’une commande à un moteur ;
1http ://rtlinux.org
41
Linux RTLinux
USB-RTSharedMemory
UserPrograms
RT Module
Fig. 8.2 – Communication avec le module temps réel.
– de Récupérer un retour capteur (position d’un moteur, valeurs des différents capteurs) ;La seconde étape à été d’interfacer le module de supervision avec Hoap-3. Avoir une machine
virtuelle java récente fonctionnant sur ce robot s’est avéré impossible, or comme les outils deplanification définis plus haut sont écrit en Java il a fallu permettre au module de supervision decommander le Hoap à distance via le réseau. Ainsi nous avons écrit un serveur de commandespour Hoap-3 et nous avons defini un protocole de communication avec le serveur réseau.
8.2 DéfinitionsDéfinition 19 (Mouvement Simple Support) Un mouvement en simple support est un mou-vement durant lequel un des deux pied n’est plus en contact avec le sol, par exemple le pas droit.
Définition 20 (Pas Double Support) Un mouvement en double support est un mouvementdurant lequel les deux pieds restent en contact avec le sol, par exemple le changement de piedd’appui.
8.3 Descripteurs
8.3.1 CapteursDu point de vue des capteurs nous n’utilisons que les cameras du robot afin de déterminer la
distance à une cible grâce à un programme utilisant la bibliothèque OpenCV écrit par BrunoAdorno.Par manque de temps nous n’avons pas pu utiliser plus de capteurs.
8.3.2 MoteursLe hoap possédant 23 degrés de liberté et ne travaillant que sur la marche pour l’instant nous
n’allons nous préoccuper que d’une valeur discrétisée, qui va nous permettre de connaître le piedd’appui afin de pouvoir enchaîner le pas droit et le pas gauche.
Ce descripteur prends ses valeurs dans [-1 , 1] (resp. pied gauche en appui, pied droit enappui).
Discrétisation
Afin de discretiser les informations capteur pour la marche nous avons pris les pas simplesupport de Sébastien, un étiquetté chaque ligne de ces fichiers en fonction du pied d’appui de ce
42
pas (Droit et gauche), 35180 instances que l’on analyse avec Weka.
Right hip joint roll
- +
>= -527 < -527
Fig. 8.3 – Arbre de décision Weka.
Weka nous donne l’arbre de décision ci dessus, en effet il y à quatre moteurs dont les positionssont complètement séparables, grace à l’un de ces quatre moteurs on peut obtenir l’informationdiscrétisée du pied d’appui.
8.4 Actions élémentaires
Sebastien Lengagne à généré les fichiers CSV contenant les trajectoires articulaires du robotdiscrétisées avec l’aide de l’analyse par intervale qui lui permet de construire des trajectoiresarticulaires sûres [LRF07, LRF09]2.
Voici la liste des mouvements que nous utilisons :– le pas droit (simple support) ;– le pas gauche (simple support) ;– le changement de pied d’appui droit vers gauche (double support) ;– le changement de pied d’appui gauche vers droit (double support) ;
A partir de ces mouvements nous définissons deux actions élémentaires voici la modélisationStrips :
PasDroit :pre : {JambeGauchei = 1 ∧ JambeDroitei = −1}
post : {JambeGauchef = −1 ∧ JambeDroitef = 1∧ TargetDistancef < TargetDistancei
∧ TargetDistancef > TargetDistancei − 10}
L’action élémentaire PasDroit est composée de deux mouvements que l’on enchaîne, unsimple support qui change l’appui du pied droit vers pied gauche et du mouvement simplesupport qui déplace le pied droit.
2Contrairement à la discrétisation par grille qui n’assure pas qu’entre deux points de la grille tout les critèressoient respectés.
43
PasGauche :pre : {JambeGauchei = −1 ∧ JambeDroitei = 1}
post : {JambeGauchef = 1 ∧ JambeDroitef = −1∧ TargetDistancef < TargetDistancei
∧ TargetDistancef > TargetDistancei − 10}
L’action élémentaire PasGauche est composée de deux mouvements que l’on enchaîne, unsimple support qui change l’appui du pied gauche vers pied droit et du mouvement simple sup-port qui déplace le pied gauche.
Le but est exprimé par une méta contrainte, distancef <= 50cm.
8.5 Commande du HoapNous avons donc défini un protocole réseau permettant de communiquer avec un serveur sur la
machine qui lui execute sur le robot les sequences de pas générées par Sébastien Lengagne [LRF07,LRF09].
L’exécution d’une séquence n’était alors non bloquantes, et donc il était difficile d’enchaînerdeux actions, nous avons donc remédié à ce problème en modifiant la routine d’envoi de com-mandes pour qu’elle attende la fin de l’exécution de la séquence par le robot avant de rendre lamain à l’utilisateur.
Hoap
h3srv
SharedMemory
SupervisionRéseau
Fig. 8.4 – Serveur d’envoi de commandes.
8.5.1 ServeurProtocole
Le protocole mis en place peut se rapprocher des protocoles POP et SMTP. Ce protocoleest donc un protocole texte, les commandes sont de la forme suivante :
<commande> <arg0> <arg1> ... <argn>\n
Les réponses du serveur sont de la forme :
44
<OK | ERR>\n
Le réponse OK indique qu’il n’y a pas eu d’erreur à l’exécution de la commande, OK peut êtreprécédé par une liste de données dans le cas de la commande STATE. La réponse ERR peut êtresuivie par un message d’erreur.
Voici la liste détaillée des commandes du protocole :– MOVE, prends en paramètre le nom du fichier CSV à exécuter ;– HEAD, prends en paramètre la commande moteur à envoyer aux servomoteurs de la tête ;– STATE, qui retourne l’état courant du robot ;
L’état courant du robot est stocké sous la forme de couples de <variable, value> dans d’undictionnaire afin d’en faciliter l’accès. Le serveur lit en permanence la fifo dans laquelle le pro-gramme de Bruno Ardono envoie la distance à la cible.
Exemple 3 (Exemple de dialogue entre le client et le serveur) --> MOVE library\D33.csv\n<-- OK--> STATE\n<-- distance = 55\n<-- righthip = -735\n<-- OK
Dans ce dialogue on demande au robot d’exécuter la sequence stockée dans le ficher D33.csv,puis on demande au serveur l’état du robot.
Commande MOVE
Les mouvements élémentaires sont stockées sur le robot sous forme de fichiers CSV. Par lebiais de la commande MOVE on demande au serveur d’envoyer le fichier dont on passe le nom enparamètre. Cet envoi est bloquant donc le client est bloqué en attente de la réponse du serveur(OK ou ERR).
8.5.2 ExpérienceL’expérience se déroule ainsi, le robot detecte une cible placée en face de lui et estime sa dis-
tance. Ensuite le module de planification construit la séquence d’action permettant d’approcherla cible à moins de 50cm.
Le but est de modifier la distance à la cible pendant l’exécution du plan afin de provoquerune replanification.
L’expérience que nous avons mené était de planifier une séquence de pas sur ce robot huma-noïde.
45
46
Chapitre 9
Conclusion & Perspectives
Nous avons montré la portabilité de notre approche au travers de l’expérience avec Hoap-3.Et les outils définis dans le cadre de l’expérimentation sur Hoap sont actuellement utilisés parSebastien Lengagne et Frederic Kamara pour réaliser une nouvelle expérience avec Hoap.
L’architecture du module de planification est maintenant indépendante du Tribot, et montrede meilleures performances.
Pour l’expérience sur le Tribot le module de planification est capable de planifier des actionsélémentaires en parallèle et le module de supervision grace à Urbi est capable d’exécuter cesactions en parallèle.
Nous avons donné au Tribot un capacité minimale d’apprentissage, et en fonction de cetapprentissage une décision minimale.
Comme perspectives on peut envisager d’utiliser des robots “intermédiaires” en terme dequalité des capteurs et des moteurs, c’est à dire entre le Mindstorm et Hoap-3, on peut citerpar exemple AIBO.
AIBO est beaucoup plus riche du point des vue capteurs et du point de vue des moteurs, cen’est pas un robot mobile, mais un quadrupède qui n’a pas les problèmes de gestion de l’équilibrede Hoap-3. De plus il existe une version d’Urbi pour AIBO donc le portage vers ce nouveaurobot devrait s’avérer plus facile. L’utilisation d’AIBO permettra de définir de nouvelles expé-riences plus riches, et plus porteuses car ce robot est très connu du grand public.
L’algorithme d’apprentissage est extrêmement simple et mériterai d’être plus complexe d’au-tant plus que la quantité de données à étudier est grande.On peut faire de l’apprentissage à différent niveaux :
– au niveau de l’enchaînement des actions, recherche de motifs, etc. ;– au niveau des valeurs des capteurs, afin de diagnostiquer la défaillance des capteurs ;
Ensuite du point de vue de la planification chercher une séquence complète pour atteindrele but, s’avère assez inefficace car le monde qui entoure le robot est dynamique. Une solutionpourrait être de générer des “sous-buts” de manière à ne résoudre qu’une partie de la séquence.Ainsi nous aurions des séquences plus courtes à planifier et donc moins d’actions inutiles.
47
48
Chapitre 10
Annexes
Algorithme de résolution du problème de planification :
Algorithme 4 Solve()1: result := false2: currentBound := lowerBound3: while currentBound < upperBound ∧ ¬result do4: defineVariables(currentBound, model)5: defineConstraints(currentBound, model)6: defineInitialState(initialState, model)7: defineGoalState(currentBound, finalState, model)8: if solveok then9: return extractSolution()
10: else11: currentBound = currentBound + 112: end if13: end while
49
50
Bibliographie
[BF97] Avrim L. Blum et Merrick L. Furst : Fast planning through planning graph analysis.1997.
[BKL+] Andrea Bauer, Klaas Klasing, Georgios Lidoris, Quirin Mühlbauer, FlorianRohrmüller, Stefan Sosnowski, Tingting Xu, Kolja Kühnlenz, Dirk Wollherret Martin Buss : The Autonomous City Explorer : Towards Natural Human-RobotInteraction in Urban Environments. 2(1).
[Bro85] Rodney A. Brooks : A robust layered control system for a mobile robot. Rapporttechnique, Cambridge, MA, USA, 1985.
[CBQ03] Rémi Coletta, Christian Bessiere et Joel Quinqueton : Modélisation Semi-Automatique par Acquisition de Contraintes. Dans Presses Universitaires de Gre-noble, éditeur : RJCIA’03 : Sixièmes Rencontres des Jeunes Chercheurs en Intelli-gence Artificielle, pages 97–110, Laval (France), 2003. 10136.
[FK98] Masashiro Fujita et Hiroaki Kitano : Development of an autonomous quadrupedrobot for robot entertainment. 1998.
[FN71] Richard Fikes et Nils J. Nilsson : STRIPS : A new approach to the application oftheorem proving to problem solving. Dans IJCAI, pages 608–620, 1971.
[JKK+01] James Kuffner Jr, Jr. Koichi, Nishiwaki Satoshi Kagami, Masayuki Inaba et Hi-rochika Inoue : Footstep planning among obstacles for biped robots. Dans Proc.of 2001 IEEE Intl. Conf. on Intelligent Robots and Systems (IROS), pages 500–505,2001.
[JL00] James J. Kuffner Jr. et Steven M. Lavalle : Rrt-connect : An efficient approachto single-query path planning. Dans Proc. IEEE Int. Conf. Robot. Autom. (ICRA,pages 995–1001, 2000.
[LB03] Adriana Lopez et Fahiem Bacchus : Generalizing graphplan by formulating plan-ning as a csp. Dans Proceedings of the 18th International Joint Conference on Ar-tificial Intelligence (IJCAI-2003), 954960, pages 954–960. Morgan Kaufmann Publi-shers, 2003.
[LRF07] Sebastien Lengagne, Nacim Ramdani et Philippe Fraisse : Guaranteed Compu-tation of Constraints for Safe path Planning. Dans Humanoids’07 : 7th InternationalConference on Humanoid Robots, page NA, Pittsburgh, PA, USA États-Unis d’Amé-rique, 12 2007. IEEE-RAS.
[LRF09] Sebastien Lengagne, Nacim Ramdani et Philippe Fraisse : Safe Motion Plan-ning Computation for Databasing Balanced Movement of Humanoid Robots. DansICRA’09 : IEEE International Conference on Robotics and Automation, pages 1669–1674, 05 2009.
51
[Mac77] Alan Mackworth : Consistency in networks of relations. Artificial Intelligence,8(1):99–118, 1977. Reprinted in Readings in Artificial Intelligence, B. L. Webber andN. J. Nilsson (eds.), Tioga Publ. Col., Palo Alto, CA, pp. 69-78, 1981. [This paperwas honoured in Artificial Intelligence 59, 1-2, 1993 as one of the fifty most citedpapers in the history of Artificial Intelligence.].
[Mon74] Ugo Montanari : Networks of constraints : Fundamental properties and applicationto picture processing. 1974.
[Nil80] Nils . J. Nilsson : Principles of artificial intelligence. Morgan Kaufmann, SanFrancisco, CA, USA, 1980.
[Pau08] Mathias Paulin : Contributions à l’apprentissage automatique de réseau decontraintes et à la constitution automatique de comportements sensorimoteurs enrobotique. Thèse de doctorat, Université Montpellier II, 2008.
[PB98] Barney Pell et Douglas E. Bernard : An autonomous spacecraft agent prototype.1998.
[PBDK06] Mathias Paulin, Eric Bourreau, Christopher Dartnell et Sébastien Krut : Mo-délisation et planification d’actions élémentaires robotiques par apprentissage de ré-seaux de contraintes. Dans Deuxièmes Journées Francophones de Programmation parContraintes (JFPC06), Nîmes - Ecole des Mines d’Alès / France, 2006.
[vBC99] Peter van Beek et Xinguang Chen : CPlan : A constraint programming approachto planning. Dans AAAI/IAAI, pages 585–590, 1999.
[WF05] Ian H. Witten et Eibe Frank : Data Mining : Practical Machine Learning Toolsand Techniques, Second Edition (Morgan Kaufmann Series in Data Management Sys-tems). Morgan Kaufmann, June 2005.
[YT89] Seiji Yamada et Sabinro Tsuji : Selective learning of macro-operators with perfectcausality. Dans IJCAI, pages 603–608, 1989.
52
