RAPPORT DE STAGE - e
Contents
1. l endroit voulu et ainsi comparer avec les diff rentes m thodes de guidage leurs performances respectives on fait varier la position et l orientation du v hicule 21 BILLIAU Pierre 2 me Ann e T l communications iv Interface graphique Pour faciliter le fonctionnement de l interface une autre interface a t d velopp e A l origine seule une petite fen tre de commande existait cf figure Celle ci permettait de zoomer sur la figure de faire un scrolling et tra ait automatiquement les chemins Reeds and Shepp et CC Dubins Cette interface n est plus tr s pratique d s qu il y a beaucoup plus familles de chemins implant es et que l on d sire plus de souplesse modification directe de l orientation des roues choix d un type de chemin particulier utilisation de la fonction statistique La nouvelle interface est construite avec le logiciel FLTK comme les deux fen tres d ja existantes Ce logiciel est assez simple d utilisation avec un peu d habitude L interface graphique et les deux autres fen tres d ja existantes figure ci dessous xfi _ Unit size Scrolling wl s000 eff 250 a Reset 250 4 Reset Fen tre d j existante permettant de faire des zooms et du scrolling Fen tre d j existante permettant d afficher les Chemins ici chemin de type TST 22 BILLIAU Pierre 2 me Ann e T l communications Sur l interface cr2. e un menu a t de commandes a t implant pour permettre de s lectionner un type de chemin pour une m thode de guidage donn e On peut alors le tracer et faire des tests plus facilement Des boutons ON OFF permettent de s lectionner le choix du chemin afficher Il est aussi possible de changer l orientation des roues orientation initiale ou finale Des fen tres permettent de connaitre directement la longueur du chemin trac et le temps de calcul du chemin TET XP mK LOLI Gnarp 34354 HUG 30 LITT Ph SAYICI i t 4 1 maan a 21 191 2 as al Co pah CC etended path CC pas pars TSE TIF TIST TSTF ms por Fo o OF type i a graphic trace q vaue D b we Value Kapoe a5 Sigma 1 qtia angle fina angle Compare Paths CC_path Extended Topologic Average rtiol Average retio NeweltciT ftctt lengih esssze fasscer fee fo ose ime s ononea homes fems fo o r ne fe id res 0 fosses m n eo o kese fo aszecaa Topologic j Lateral Begrientation Statistics Path Numbers 7 000 Radius 3 DK QUIT CLEAR Interface cr e avec FLTK L utilisation de FLTK est plut t simple chaque bouton est associ un callback Plus pr cis ment une fonction callback est appel e chaque fois que la valeur du widget l interface graphique associ est modifi e Il m a donc fallu d finir l interface et les boutons et d finir aussi tous les callback associ s La c
3. es par cette activit de recherche sont celles de la robotique non manufacturi re e g maintenance d quipements ou intervention en milieu hostile ou lointain robotique de service en mettant l accent sur les domaines du transport et du m dical l autre secteur d application concern par nos travaux sur le mouvement dans le monde virtuel est celui de la r alit virtuelle et du multim dia iv Personnel Il se compose de chercheurs a temps plein mais aussi de th sards et de stagiaires Le responsable scientifique du projet est M Christian Laugier BILLIAU Pierre 2 me Ann e T l communications III Sujet du stage 1 Description du projet Le but du stage est de travailler sur l implantation d une m thode de guidage pour v hicule de type voiture Ce travail de recherche entre dans le cadre beaucoup plus g n ral du projet Sharp qui lui m me entre dans le cadre du projet fran ais La Route Automatis e Le but de ce projet est la construction de v hicules autonomes Dans ce cadre de nombreux travaux de recherche sont effectu s sur la planification de mouvement c est dire la d termination du chemin que va emprunter un v hicule en fonction des param tres internes au v hicule mais aussi ext rieurs par exemple les obstacles Les param tres internes sont les param tres cin matiques du v hicule position vitesse mais on tient aussi compte de certaines contraintes intrins ques au v hicule notamment
4. la continuit de la courbure des v hicules ainsi que de h valeur maximale de la courbure On cherche en effet mod liser de fa on la plus proche de la r alit le mouvement des v hicules Cette mod lisation doit donc tenir compte de l incapacit des roues d un v hicule tourner instantan ment ou alors le v hicule devrait stopper son mouvement braquer les roues puis red marrer ce qui n est pas tr s efficace et de la valeur maximale de la courbure des roues c est dire que le rayon de courbure du v hicule dans un virage est limit Nous verrons que ces contraintes sont fondamentales dans la planification de mouvement Si le v hicule a la capacit de se d placer en marche arri re on doit en tenir compte pour pouvoir optimiser la longueur du chemin Il y a aussi des contraintes ext rieures prendre en compte notamment l vitement des obstacles Ces obstacles peuvent tre immobiles mais aussi mobiles par exemple d autres v hicules sur une m me route La planification de mouvement va donc d terminer une trajectoire r alisable par le v hicule en fonction de tous ces param tres et d autres crit res comme le compromis entre la longueur du chemin qu on tentera bien entendu de minimiser et le temps de calcul du chemin qu on essaiera aussi de minimiser pour pouvoir d velopper l application en temps r el sur de vrais v hicules BILLIAU Pierre 2 me Ann e T l communications 2 Lien avec
5. n importe quelle configuration partir d une configuration initiale si cette m thode ne v rifiait pas cette propri t la voiture ne serait pas contr lable 11 BILLIAU Pierre 2 me Ann e T l communications 4 Propri t s du chemin CC Nous examinons ici quelles sont les cons quences des contraintes sp cifi es initialement continuit de la courbure notamment sur les m thodes de guidage On d finit ici chemin CC un chemin qui a pour propri t d avoir une courbure continue Continuous Curvature Pour un v hicule se d pla ant uniquement en marche avant la nature du chemin est facile a tablir La continuit de la courbure impose que lorsqu un v hicule amorce un virage il ne peut pas imm diatement d crire un arc de cercle ce qui signifierait que la courbure passe de la valeur 0 la valeur Kmax donc qu elle soit discontinue La courbure variant de mani re continue il faut mod liser cette variation On mod lise la variation de la courbure comme lin aire pour simplifier mais en tant tout de m me tr s proche de la r alit Une courbe ayant la propri t d avoir un rayon de courbure variant de fa on lin aire s appelle une clotho de Un chemin CC est donc compos de e Segments de droite e Arcs de cercle e Arcs de clothoide Lorsque le v hicule tourne il commence donc par braquer les roues et suivre un arc de clothoide puis lorsque la courbure atteint la valeur Kmax il d c
6. ne Alpes 8 ao t 2001 26 BILLIAU Pierre 2 me Ann e T l communications Index des mots cl s CR ENT 016 01 1 6 pen enemas dd en 14 17 19 20 Clothilde resisaet rr nT ira N A 11 12 continuit de la cOurbUTS 4855 run nine nan nn users tent 8 9 11 D bins RER SPP EN PROS n CPR a 13 14 15 21 i tertace eA ONL NS nt ee eu S 15 20 22 m thode de guidage cscs ri 1 8 9 10 13 14 16 19 20 22 planification de MOUVEMENT ennemie 8 9 14 15 Reedsand Sh pp asian nine ta 13 14 15 16 20 21 27
7. toujours les quarante chemins entre les deux configurations n existent pas tous mais au moins un dans la famille existe quelque soit le couple de configurations On peut l gitimement se demander pourquoi un chemin n existerait pas entre deux configurations Prenons l exemple de la famille TT Le chemin TT est compos de 2 virages Les deux CC Circle doivent donc tre tangents j ai bri vement d fini le CC Circle dans le sujet du stage En notant rec le rayon du CC Circle on remarque que la distance entre les deux configurations doit tre exactement gale 2 rcc pour que le chemin puisse exister Il faut aussi examiner le sens du virage Le chemin ne peut pas exister si les deux virages se font dans le m me sens le deuxi me virage doit tre de sens oppos au premier virage Si le chemin existe il faut ensuite le calculer Le but n tant pas d entrer dans les d tails de l algorithme je pr senterai simplement la m thode pour calculer un chemin Le but est de calculer un chemin Reeds and Shepp ou Reeds and Shepp tendu entre deux configurations Pour cela on calcule donc les quarante chemins de la famille Reeds and Shepp et on choisit le plus court Pour calculer un chemin d une famille donn e par exemple TT on proc de de la mani re suivante Pour chaque configuration il y a 4 CC Circle associ s on peut aller gauche ou droite et en marche avant ou arri re Pour le couple de c
8. AN EIEEE SEE ESENE EES aaa aeons 26 INDEX DES MOTS GILES sate nn A RER N E nine nee T cease nn ann nt 27 BILLIAU Pierre 2 me Ann e T l communications Abstract My internship of 11 weeks at INRIA National Institute of Research in Computer science and Automation Rh ne Alpes was dedicated to work on the improvement of a steering method for car like vehicles A steering method is an algorithm that computes paths between two configurations without the presence of obstacles The modelling of the problem also imposes other constraints especially the continuity of the curvature There were already steering methods that had been developed but I had to extend them or to define new ones My work was divided into four parts 1 The extension of the steering method CC Reeds and Shepp the method was still implemented but we had to extend it to compute shorter paths 2 The computation of topological paths it allows the steering method to be useful with the computation of the paths in the presence of obstacles 3 The implementation of statistics functions it allows the program user to compare the relative performances of the different steering methods 4 The designing of a graphic user interface GUI which allows the user to test easily the steering methods BILLIAU Pierre 2 me Ann e T l communications I Introduction Ce rapport de stage pr sente le travail que j ai r alis pour valider ma deuxi me ann e d
9. BILLIAU Pierre 2 Ann e T l communications RAPPORT DE STAGE Intitul Implantation d une m thode de guidage pour v hicule de type voiture en C VA INRIA RHONE ALPES R alis l INRIA Rh ne Alpes du 9 juillet au 21 septembre 2001 au sein du projet Sharp Responsable M Thierry Fraichard BILLIAU Pierre 2 me Ann e T l communications Table des mati res PRBS RAG Tenses Rad EE nn E E T A E EEEE E ER aR 3 L INTRODUCTION ar E E E EE a I CONTEXTE DU STAGE 1 Pr sentation de l INRIA 2 La recherche l INRIA 3 Les diff rents projets de recherche l INRIA 4 Le projet SGD annee EE ce casdusavs teases AE EE E RE E E beatae ies TIT SUJET DU STAGE 1 Description du projet 2 Lien avec le stage 4 3 Mod lisation di probl me ssssneennnsinenntennannnnnemennttennmneneneensnnenilemenntnnitnus 4 Propri t s du CEMINIG Corie arrire eosa TEE E E Gbacg cos item EA A EETA AREA EE EEN ER 12 5 Les diff rentes m thodes de guidage sise 14 IV ERAVAIL EFFECTU E poiesis anneer seraa RESE een na enr de at ee nent tr le Ea ENEO ttes einen de se ae nue 1 Ce qui existait d j 2 LO travail effectus ek ak tise E nee Ae escent nas IV CONCLUSION BILAN GLOBAL ccsssssessessesseeseessessesesseesessessessesseesssesssessessesseesecsseseessessessecseesessesseeseeaeeaueesensenseasenss 25 BIBLIOGRAPHIE sscszschecsecsccscesdesseeaiadeicesasedeesbcaacancsntaezisiaetuovesteaeesiealk osadet dan ose AEEA
10. aintes cin matiques et dynamiques incertitude dans des mondes r els ou virtuels M thodologie pour le d veloppement d architectures d cisionnelles pour le contr le de robots mobiles dans des environnements dynamiques peu ou pas connus a priori Mod les et algorithmes pour la simulation dynamique i e la gestion des interactions physiques et la simulation de la dynamique des corps complexes en mouvement et en interaction d formations collisions forces Outils de mod lisation et de calcul probabiliste pour la g om trie permettant de traiter correctement les incertitudes et leurs impacts sur les probl mes inverses et les probl mes d interpr tation de donn es sensorielles que nous rencontrons sujet trait en collaboration avec le laboratoire Leibniz de l IMAG iii Applications L activit de recherche pr c dente est la fois valoris e et fertilis e par des activit s plus appliqu es qui visent au d veloppement de solutions des probl mes industriels Plusieurs prototypes de recherche et exp rimentations r elles e g sur des v hicules autonomes ou des syst mes de vid o professionnelle et de production d images sont ainsi r alis s en relation avec les moyens robotiques de l INRIA Rh ne Alpes et des industriels certains de ces prototypes ont d j donn lieu des transferts de technologies en CAO robotique et en vid o professionnelle en particulier Les applications plus particuli rement vis
11. algorithme existant ainsi qu tude du langage C pour mieux me familiariser avec la programmation orient e objets Il a donc fallu que je lise et comprenne la documentation existante sur la th orie de la planification de mouvement Ensuite mon stage a t d coup en quatre t ches principales l extension de la m thode de guidage Reeds and Shepp cf partie th orique la sp cification des chemins topologiques et l implantation de la m thode de guidage topologique l implantation de fonctions permettant de faire des statistiques et des comparaisons sur les diff rentes m thodes de guidage et le d veloppement d une interface graphique 16 BILLIAU Pierre 2 me Ann e T l communications i L extension de Reeds and Shepp Comme nous l avons vu dans l explication th orique du sujet du stage la m thode de guidage Reeds and Shepp poss de une extension de neuf a quarante familles de chemin Il faut donc implanter les familles restantes Rappelons que la m thode de guidage Reeds and Shepp calcule les quarante chemins associ s chaque famille puis retourne le plus court chemin parmi ceux ci Pour chaque famille de chemin le calcul du chemin entre deux configurations se fait de la fa on suivante test de l existence du chemin puis calcul du chemin s il existe Un chemin d un type donn n existe pas syst matiquement mais le chemin calcul par la m thode de guidage existe
12. c dentes ne v rifiaient pas cette proposition puisque la longueur des chemins tait toujours au moins gale 2 foc U Le d tail des chemins topologiques sera expos dans la partie Travail effectu 15 BILLIAU Pierre 2 me Ann e T l communications IV Travail effectu Pour mieux comprendre mon travail je vais d abord pr senter le travail qui avait d j tait effectu pour avoir une vue globale du projet puis je pr senterai plus pr cis ment ce que j ai personnellement ajout ou compl t J ai effectu ce travail seul pas en bin me et j avais ma disposition les moyens informatiques n cessaires 1 Ce qui existait d j Les m thodes de guidage pour le calcul des chemins CC Dubins et Reeds and Shepp existaient d j Ces algorithmes taient test s et valid s Une interface graphique et une fen tre de commande associ e taient galement implant es avec le logiciel FLTK L interface graphique permet de tester tr s facilement les m thodes de guidage lorsqu on clique sur l interface on peut d finir des positions de configurations et ainsi tracer le chemin correspondant La plupart des sp cifications tait donc fournie au d part i e la sp cification des types Chemin Configuration Ces algorithmes sont crits dans le langage C 2 Le travail effectu Le d but de mon stage a t consacr l tude de la partie th orique du stage la compr hension de l
13. e de mon stage Consid rons un v hicule a quatre roues deux roues arri re et deux roues avant motrices Il faut trois param tres pour d terminer la position et l orientation du v hicule et un param tre pour d terminer l orientation des roues avant On d finit la configuration du v hicule par un quadruplet q x y 9 K o x y repr sente les coordonn es du milieu du segment joignant les roues avant O l orientation du v hicule et l orientation des roues avant On d finit un chemin comme un ensemble de fonctions continues x t y t t K t A partir de ce mod le on peut d terminer quels sont les chemins admissibles i e les chemins effectivement r alisables un chemin admissible est solution d un syst me d un syst me diff rentiel que nous ne mentionnons pas ici pour simplifier Cependant les chemins admissibles doivent v rifier les deux contraintes suivantes la condition de roulement sans glissement les roues tournent perpendiculairement leur axe et les contraintes sur la courbure Un chemin admissible est donc un chemin qui relie les configurations initiale et finale Le probl me est donc de d terminer un chemin admissible partir d une configuration initiale qs et d une configuration finale qg donn es tel que e J doit relier qs et qg e La longueur du chemin doit tre minimale si l on trouve plusieurs chemins admissibles Cependant une m thode de guidage arrive relier
14. entique celui du mouvement lat ral Il sert redresser les roues une fois que l on a atteint la position de la configuration finale Il est compos de trois mouvements 1 un virage en marche arri re 2 une ligne droite en marche arri re 3 un virage en marche avant Le mouvement de r orientation sert redresser les roues du v hicule pour aller dans la direction souhait e 19 BILLIAU Pierre 2 me Ann e T l communications La aussi il existe un infinit de mouvements de r orientation c est pourquoi on contraint ce mouvement tre sym trique par rapport une droite remarquable cf figure Suivant l angle de redressement des roues on d termine l angle de braquage n cessaire effectuer Si l on veut redresser les roues d un angle theta il faut braquer les roues d un angle theta 4 Une fois le chemin topologique implant d finition de la classe calcul des chemins puis test on implante une super m thode de guidage qui inclut la fois le chemin topologique et le chemin Reeds and Shepp tendu 20 BILLIAU Pierre 2 me Ann e T l communications iii Statistiques et comparaison Une fois ces m thodes de guidage implant es il est int ressant de savoir quelle m thode est la plus efficace et de quantifier les optimisations successives sur les m thodes de guidage Reeds and Shepp Reeds and Shepp tendu chemin topologique Pour cela on d fi
15. er quelles sont les activit s pr cises de l INRIA il peut tre utile de pr senter quels sont les diff rents projets de recherche men s dans l tablissement BILLIAU Pierre 2 me Ann e T l communications 3 Les diff rents projets de recherche l INRIA Ma triser les r seaux et syst mes informatiques R seaux parall lisme et syst mes r partis APACHE Algorithmique programmation parall le et partage de charge ARENAIRE Arithm tique des ordinateurs PLANETE Protocoles et applications pour l Internet ReMaP R gularit et parall lisme massif RESO R seaux haut d bit et applications eSIRAC Syst mes informatiques r partis pour applications coop ratives eVASY Validation de systemes Aider la conception et la cr ation Bases de connaissances documents multim dia mod les cognitifs EIFFEL Cognition et coop ration en conception EXMO Echanges de connaissance structur e m diatis s par ordinateur HELIX Informatique et g nomique OPERA Outils pour les documents lectroniques recherche et applications Percevoir simuler et agir Synth se d images r alit virtuelle vision par ordinateur et robotique IMAGIS Mod les algorithmes g om trie pour le graphique et l image de synth se MOVI Mod lisation localisation reconnaissance et interpr tation en vision eSHARP Programmation automatique et syst mes d cisionnels en robotique Mod liser les ph nom nes complexe
16. ir accept en stage et pour m avoir conseill tout au long de mon travail ainsi que INRIA pour m avoir accept en stage dans ses locaux BILLIAU Pierre 2m Ann e T l communications II Contexte du stage Le stage s est d roul l INRIA Rh ne Alpes Montbonnot du 9 juillet au 21 septembre 2001 au sein du projet Sharp 1 Pr sentation de INRIA Un institut de recherche au c ur de la soci t de l information L INRIA est un tablissement public caract re scientifique et technologique qui m ne des recherches avanc es dans le domaine des sciences et technologies de l information et de la communication Ce domaine inclut l informatique et l automatique mais aussi les t l communications et le multim dia la robotique le traitement du signal et le calcul scientifique B timent de l INRIA BILLIAU Pierre 2 me Ann e T l communications 2 La recherche l INRIA Les recherches l INRIA sont men es au sein de groupes de travail appel s des projets de recherche Un projet de recherche se caract rise par eune quipe d une quinzaine de scientifiques eune unit th matique forte eun programme de travail et des objectifs moyen terme eune autonomie financi re et scientifique edes liens et des coop rations avec les partenaires industriels et scientifiques en France et dans le monde eune valuation rigoureuse des r sultats eune dur e limit e Pour mieux cern
17. ir de cette description on peut d finir m thodes de guidage calculant des chemins CC et d finir ainsi plusieurs m thodes de guidage La m thode de guidage CC Dubins du nom de la personne ayant d termin la forme des plus courts chemins pour la voiture marche avant calcule des chemins courbure continue et o le v hicule se d place uniquement en marche avant Pour rejoindre deux configurations on peut soit 1 faire un virage une ligne droite puis un virage il faire un virage un virage dans le sens inverse puis un virage dans le sens initial On peut d montrer qu il y a 6 sortes de chemins qui minimisent la longueur parcourue entre deux configurations LSL LSR RSL RSR LRL RLR S repr sente une ligne droite L un virage a gauche R un virage a droite Il faut d abord tester l existence de chaque sorte de chemin puis le calculer s il existe S il y a plusieurs chemins possibles le chemin le plus court d termine le chemin CC Dubins reliant les deux configurations La m thode de guidage CC Reeds and Shepp du nom des personnes ayant d termin la forme des plus courts chemins pour la voiture marche arri re Cette m thode de guidage calcule des chemins pour des v hicules ayant la capacit d aller en marche arri re On peut ainsi faire beaucoup plus de sortes de mouvements Reeds et Shepp ont d fini l origine des familles pour les chemins courbure non continue On re
18. le stage Le stage consiste d velopper une m thode de guidage steering method i e un algorithme qui calcule un chemin entre deux configurations du v hicule sans prendre en compte la pr sence d obstacles dans l environnement Etant donn e une m thode de guidage il est alors possible de d terminer le chemin global en utilisant un algorithme g n ral de planification des chemins prenant en compte les obstacles il en existe plusieurs connus the Probabilistic Path Planner the Ariadne s Clew Algorithm the Holonomic Path Approximation Algorithm Une m thode de guidage est donc un l ment cl dans l algorithme g n ral de planification de mouvement Comme dit pr c demment on peut d velopper plusieurs m thodes de guidage suivant les crit res du r sultat que l on veut obtenir Les m thodes de guidage d velopp es pendant le stage devront tenir compte des contraintes du v hicule nonc es pr c demment continuit de la courbure dans les virages limitations m caniques du v hicule rayon de braquage limit variation de l angle de braquage limit e Quelles seront les cons quences de ces contraintes sur l algorithme d velopper Mod lisons le probl me puis examinons ces cons quences 10 BILLIAU Pierre 2 me Ann e T l communications 3 Mod lisation du probl me Je vais ici pr senter quelques r sultats th oriques simples qui permettront de mieux comprendre quel tait le context
19. nit une fonction de statistiques et une fonction de comparaison qui permettent de comparer deux m thodes de guidage La fonction de statistiques calcule un nombre donn de configurations finales de mani re al atoire pour qu elles soient r parties de mani re la plus uniforme possible et calcule les deux chemins correspondants en utilisant les m thodes de guidage ad hoc Le nombre de chemins doit tre grand pour avoir une haute pr cision mais le temps de calcul peut tre alors un peu long quelques minutes pour comparer 50 000 chemins Cette fonction calcule e la longueur du plus court chemin et du plus long pour les deux m thodes de guidage e les moyennes des longueurs des chemins e les rapports de ces longueurs e l cart type pour savoir si les diff rences entre les longueurs de chemins sont r guli res ou pas e le temps de calcul n cessaire chaque m thode de guidage Il est aussi n cessaire de pr ciser le rayon de la ane dans laquelle on veut trouver les configurations au del d une certaine limite toutes les familles renvoient le m me chemin le chemin le plus court est le chemin simple TST Cette fonction de statistiques est tr s utile car elle permet de voir les performances relatives entre les diff rentes m thodes de guidage Il est aussi possible de comparer les chemins directement l aide de l interface graphique On peut d finir la position de la configuration finale en cliquant
20. onfigurations initiale finale il y a donc 16 couples de CC Circle diff rents Pour chacun de ces couples une fonction teste l existence d un chemin et le calcule s il existe il peut y avoir plusieurs chemins existants un seul ou aucun cela d pend du type du chemin et de la position des configurations Par exemple pour le chemin TST virage ligne droite virage il y a plusieurs chemins possibles les deux virages peuvent tre dans le m me sens ou dans un sens oppos Le plus court sera diff rent selon les cas Pour le calculer il faut calculer les configurations interm diaires et les CC Circle interm diaires du chemin pour pouvoir ensuite tracer le chemin et calculer sa longueur Plus le chemin est complexe plus il y a de configurations interm diaires a calculer ce qui est le cas pour la famille tendue et d ventuels chemins possibles Il est facile de tester la validit de l algorithme de calcul des chemins un outil graphique tait d ja 4 ma disposition pour visualiser les chemins On peut alors facilement v rifier si le calcul du chemin est correct 17 BILLIAU Pierre 2 me Ann e T l communications ii Calcul du chemin topologique Comme je l ai bri vement rappel dans la pr sentation de mon stage le chemin topologique a t implant pour v rifier une propri t topologique ce que les deux m thodes de guidage pr c dentes ne font pas Le chemin topologique permet aussi nous le
21. orithmiques demandant un minimum d explication 24 BILLIAU Pierre 2 me Ann e T l communications IV Conclusion Bilan global J ai trouv ce stage int ressant dans la mesure o il m a permis d aborder un sujet sur lequel je n avais jamais travaill la robotique Il tait pour moi tr s motivant de travailler sur une partie d un projet mobilisant beaucoup de monde et qui avait un r sultat plut t spectaculaire la construction de v hicules autonomes Il m a aussi permis de compl ter mes connaissances en programmation orient e objet et plus g n ralement en algorithmique Il m a aussi permis de voir comment se passait le travail en laboratoire dans le projet Sharp mais aussi plus g n ralement dans les autres projets de recherche l INRIA en tant en contact avec d autres tudiants en stage dans d autres projets Je regrette de n avoir pas pu aller plus loin dans mon stage c est dire tester l algorithme sur des v hicules autonomes m me s il y avait encore beaucoup de tests mener 25 BILLIAU Pierre 2 me Ann e T l communications Bibliographie 1 Th Fraichard et J M Ahuactzin Smooth Path Planning for Cars EEE Int Conf On Robotics and Automation May 2001 2 Th Fraichard A Scheuer et R Desvigne From Reeds and Shepp s to Continous Curvature Paths IEEE Int Conf On Advanced Robotics October 1999 3 Th Fraichard Chemins courbure continue INRIA Rh
22. portant mais les chemins sont plus complexes donc aussi plus longs a calculer On remarquera cependant cf la suite de ce rapport que la longueur des chemins est parfois beaucoup plus courte Le chemin le plus court n appartient pas non plus a la famille Reeds and Shepp tendue plus exactement il existe des cas o le chemin le plus court n appartient pas cette famille contrairement la famille CC Dubins e La m thode de guidage topologique Les m thodes de guidage calculent un chemin en l absence d obstacles et sont utilis es l int rieur d autres algorithmes de planification de mouvement qui eux permettent l vitement d obstacles Cependant pour pouvoir tre ins r e dans l algorithme de planification de mouvement la m thode de guidage a besoin de v rifier certaines propri t s Ve gt 0 2n gt 0 V qi q2 Ce q2 B qi N Steer qi qz2 B qi C est l ensemble des configurations B d note une boule ferm e Steer le chemin calcul par la m thode de guidage entre les configurations q1 et q2 Ceci signifie d un point de vue topologique que dans toute boule ici un cercle car on est dans le plan de rayon gt 0 il existe un n gt 0 pour lequel on doit pouvoir r unir par un chemin inclus dans cette boule deux configurations distantes de cet n La longueur du chemin topologique n est donc pas toujours sup rieure une constant donn e ce que les m thodes de guidage pr
23. prend les m mes familles pour les chemins a courbure continue Cette m thode calcule donc le chemin le plus court parmi les neuf suivantes i Tl ou r rr ii AcAA iii AAcA iv AACAA V ACAACA Vi AcASAcA Vil AcASA viii ASAcA 1x ASA A repr sente un virage S une ligne droite et c un point de rebroussement De m me que pour le chemin CC Dubins il n existe pas toujours neuf chemins possibles entre deux configurations il faut donc d abord tester l existence d un chemin avant de le calculer La m thode de guidage CC Dubins calculait un chemin parmi 6 familles donn es et le chemin le plus court se trouvait parmi ces familles Cependant le chemin le plus court ne se trouve pas parmi les neuf familles pr c dentes D o l id e d tendre la famille un nombre plus important On a donc d fini une m thode de guidage Reeds and Shepp tendue 14 BILLIAU Pierre 2 me Ann e T l communications e La m thode de guidage Reeds and Shepp tendue Elle calcule un chemin parmi un nombre de familles plus importants la famille tendue se compose de quarante familles incluant les neuf familles pr c dentes se composent des familles suivantes i iv TUJ S T v vill THT YT ix Xvi T HTU S I T o I indique un changement de xvii xxiv T IS UTIUT direction optionnel xxv xl TOUTS THYT Le temps de calcul de ces familles est plus long car le nombre de familles est plus im
24. r ation de cette interface m a pris un certain temps car je l ai modifi e en m me temps que je modifiais le programme principal car alors certains boutons n avaient plus lieu d tre ou pouvaient tre rassembl s en un seul Le reste du temps de mon stage a t consacr des tests et au d buggage du code ou son optimisation et aussi la cr ation d une documentation en ligne 23 BILLIAU Pierre 2 me Ann e T l communications v Documentation Jai compl t une documentation d taill e sur le programme avec l outil Doxygen Cette documentation contient la pr sentation du programme la d finition d taill e et la hi rarchie des classes la liste des codes source comment s un index de toutes les fonctions et des attributs des classes Cette documentation est une documentation html facilement consultable en ligne et il est possible de g n rer la documentation au format Latex pour avoir une documentation papier totalement compl te environ 200 pages Cette documentation doit tre structur e pour tre facilement utilisable C est une documentation technique et aussi un manuel d utilisateur elle d taille certains points techniques des algorithmes et explique aussi comment utiliser l interface Les points de d tail dans les algorithmes ne sont pas mentionn s pour laisser en relief les points importants du programme Il faut donc veiller ne rien mettre de superflu et expliquer les points alg
25. rit un arc de cercle puis redresse les roues en suivant un autre arc de clothoide Lorsque la valeur de la courbure est nulle il d crit 4 nouveau un segment de droite Chemin de type TST virage ligne droite virage Les virages sont compos s de deux arcs de clothoide sym triques et d un arc de cercle les traits fins sont les rayons de ce cercle On peut encore d finir un objet important pour les chemins CC le CC Circle Lorsque le v hicule tourne il ne d crit pas exactement un arc de cercle mais un virage compos d un arc de clotho de correspondant au braquage des roues d un arc de cercle correspondant la partie du virage sont braqu es au maximum puis d un deuxi me arc de clotho de sym trique correspondant au redressement des roues Les 12 BILLIAU Pierre 2 me Ann e T l communications arcs de clothoide sont toujours de m me longueur et l angle du virage est d termin par la longueur de l arc de cercle ou langle de l arc de cercle Si on appelle Q le centre de l arc de cercle du virage on d finit le CC Circle comme le cercle de centre Q et passant par la configuration initiale du virage et la configuration finale du virage il a donc un rayon l g rement sup rieur au rayon du cercle que d crit le v hicule et le virage est strictement inclus dans le CC Circle 13 BILLIAU Pierre 2 me Ann e T l communications 5 Les diff rentes m thodes de guidage A part
26. s Automatique simulation et calcul scientifique BIP Robot bip de contr le commande et programmation temps r el IDOPT Identification et optimisation de syst mes en physique et en environnement eIS2 Inf rence statistique pour l industrie et la sant NUMOPT Optimisation num rique SINUS Simulation num rique dans les sciences de l ing nieur BILLIAU Pierre 2 me Ann e T l communications 4 Le projet Sharp Mon stage s est d roul au sein du projet Sharp Programmation automatique et syst mes d cisionnels en robotique i Pr sentation du projet Le projet SHARP centre son activit de recherche sur l tude des probl mes li s la mod lisation et la g n ration automatique du mouvement et des interactions physiques en robotique Le terme robotique rev t ici un caract re particulier dans le sens o il inclut la fois des machines physiques commun ment appel es robots capables d actions autonomes dans le monde r el et des agents mobiles ou articul s ou robots virtuels poss dant des capacit s de mouvements propres leurs permettant d voluer de mani re autonome ou semi autonome dans un monde virtuel poss dant des lois physiques semblables celles du monde r el SHARP est un projet commun avec le CNRS l INPG et l Universit Joseph Fourier 11 Axes de recherche Algorithmique pour la planification de mouvements prise en compte de contraintes de nor collision contr
27. tudes d ing nieur au D partement T l communications de l INPG ENSIMAG ENSERG Il pr sente d abord succinctement l institut de recherches INRIA qui m a accueilli ainsi que l quipe du projet SHARP qui m a entour Il pr cise ensuite quel est le sujet du stage ainsi que la th orie et les travaux de recherche men s dans ce domaine Il est pour moi n cessaire de d finir dans ce rapport certaines notions et d noncer quelques r sultats th oriques si l on veut comprendre mon travail Jai essay d tre bref sur la th orie tout en essayant d tre le plus complet possible sur les travaux de recherche sur la planification de mouvement A cet gard si l on veut plus de pr cisions sur un point th orique on pourra se r f rer aux documents d taill s dont les r f rences sont fournies dans la bibliographie Enfin j ai essay d expliquer quel a t mon travail et quels ont t les enseignements b n fiques de ce stage Je n ai pas jug pertinent de fournir les sources du code que j ai produit pendant le stage En effet ce rapport ne constitue pas une documentation technique pour un programmeur qui d sirerait comprendre ou reprendre mon travail je le renvoie alors a la documentation de mon code mais simplement une description d taill e de ce que j ai r alis c est pourquoi je ne m attarde pas sur les d tails des aspects techniques Je tiens remercier M Thierry Fraichard pour m avo
28. verrons dans la suite du rapport de r duire consid rablement la taille des chemins pour des configurations voisines Le chemin topologique se compose de trois chemins un chemin lat ral un chemin en ligne droite et un chemin de r orientation Le chemin topologique relie deux configurations initiale et finale debut et fin via une configuration interm diaire milieu e Le chemin lat ral relie deux configurations qui ont une orientation identique Il sert se positionner en face de la configuration finale il faut faire une ligne droite pour parvenir la position de la configuration finale Il est compos de trois mouvements 1 un virage en marche avant 2 une ligne droite en marche arri re 3 un virage en marche avant ee Chemin topologique entre les configurations debut et fin 18 BILLIAU Pierre 2 me Ann e T l communications Comme il existe une infinit de mouvements lat raux entre deux configurations on le contraint a tre sym trique par rapport au milieu du segment reliant les deux configurations Pour d terminer les configurations interm diaires du chemin il faut trouver l angle de braquage des roues alpha n cessaire pour rejoindre la deuxi me configuration L angle alpha d pend de la distance s parant les configurations et correspond la valeur du braquage des roues e Le troisi me mouvement mouvement de r orientation a un principe id
Download Pdf Manuals
Related Search