Rapport - PLANIART - Université de Sherbrooke
Contents
1. PlanExecutor m_timeElapsed double m_timeDiscretization double setFeedbacklterationPeriod in period int execute bool 1 GUI onOpenGLTimer Fic 2 1 Diagramme UML des classes PlanExecutor Simulator et FeedbackPlanner Le r le de chacune de ces classes est bien pr cis et l architecture pour laquelle nous avons opt permet de bien respecter leur encapsulation De plus cette architecture permet aussi d unifier les cas d terministe et non d terministe de fa on l gante DI Universit de Sherbrooke Rapport de projet pour le cours IFT 729 Parall lement cette architecture des obstacles dynamiques ont t introduits dans l environ nement Ceux ci ont t impl ment s comme des voitures simples se d pla ant al atoirement dans l environnement 2 2 Ex cuteur de plans La classe PlanExecutor est la seule qui est utilis e directement par le code client Elle se sert des deux autres pour demander au robot d ex cuter un plan i e une trajectoire Le programme principal appelle it rativement la m thode execute de l ex cuteur de plans avec un certain pas de discr tisation param trable qui ne correspond pas n cessairement au temps coul dans la r alit De plus dans le cas non d terministe cette m thode ne s ex cute pr sentement pas en temps constant sauf pour la classe NonDeterministicRealtimePlanExecutor qui comme son nom l i2. elle fonctionne sous d autres syst mes d exploitation A 2 Installation L installation du projet ne consiste qu en quelques tapes tr s simples Il faut d abord installer CMake et Visual Studio NET selon la proc dure standard ainsi que les biblioth ques Boost Kinetics OpenGL GLU et GLUT Il faut s assurer que ces biblioth ques sont connues par le compilateur de Visual Studio NET Il faut ensuite extraire l archive contenant le code source du projet dans un r pertoire au choix Finalement le r pertoire src sparsehash 1 4 src situ dans l arborescence du code source du projet doit aussi tre accessible dans les dossiers d inclusion du compilateur A 3 Compilation du projet OOPSMP utilise CMake comme moteur de production Il faut donc configurer CMake de fa on ce que toutes les biblioth ques n cessaires soient trouv es La figure A 1 donne l exemple suivre pour effectuer une bonne configuration de CMake remplacer C udes ift729 oopsmp Shttp www boost org http www cmake org 18 DI Universit de Sherbrooke Rapport de projet pour le cours IFT 729 par le chemin absolu vers le r pertoire o les sources du projet ont t extraites CMake 2 8 0 C udes ift729 oopsmp build File Tools Options Help Whereis the source code C udes ift729 oopsmp Browse Source Where to build the binaries C udes ift729 oopsmp build v Browse Build Search Simple View x dh
3. application se trouve sous le r pertoire Selector ControllerChooser exe dans l arborescence du code source du projet Une fois les param tres choisis OOPSMP peut tre lanc en cliquant sur le bouton Generate and run de l interface Controller Chooser Choose an environment Default z RRT algorithm Goal bias 0 05 Duration metric coefficient 0 25 Exploration pct before solution fo7 Nb velocity inversions coefficient Po Exploration pct after solution fo2 Nb mode switches coefficient 20 Path generator Choose a path generator Minimum duration for extend paths ho AzimutControllerBiasedPathGenerator _ Keep fraction of extend paths 09 Path generator parameters Minimum propagate time is Probability straight line fos Maximum propagate time Bo Probability naive sampling for Plan executor Choose a plan executor NonDeterministicReatimePlanExecutor rie ee 0 03125 Feedback period p2 Time scaling Bo Choose a simulator Choose a feedback planner Display Minimum refresh rate per second fio Generate only Generate and run Fic A 2 Interface du Controller Chooser 20 DI Universit de Sherbrooke Rapport de projet pour le cours IFT 729 A 5 Ex cution Une fois l application lanc e avec les param tres choisis partir du Controller Chooser plusieurs fonctionnalit s sont disponibles partir de l interface grap
4. rotation des roues peut aussi tre chang de fa on instantan e B 2 Mod le math matique La voiture poss de plusieurs param tres intrins ques par exemple sa v locit minimale et maximale dont son empattement L soit la distance entre l essieu avant et l essieu arri re Tel que mentionn dans la section pr c dente l tat du v hicule est repr sent par un triplet x y 0 Il est important de noter que la position x y correspond au milieu de l essieu arri re et non au centre du v hicule comme c est le cas pour d autres robots mobiles La figure B 1 illustre l ensemble des param tres n cessaires pour g n rer une trajectoire pour le mod le de la voiture simple dx dy Fic B 1 Mod le math matique d une voiture simple 23 DI Universit de Sherbrooke Rapport de projet pour le cours IFT 729 L orientation des roues avant de la voiture p et l empattement permettent de d finir un cercle de centre Cr cy et de rayon p autour duquel la voiture tourne La valeur p est calcul de cette fa on L tan y p p aura une valeur positive si l orientation des roues y est positive et vice versa un angle d orientation des roues de 0 rad correspond la direction de la voiture Le signe de p indique que le cercle est situ gauche de la voiture s il est positif et droite s il est n gatif Le centre du cercle est calcul en fonction de p ainsi que de l
5. tat actuel de la voiture Sx Sy 0 T Ce se p cos 0 Cy Sy p sin 0 oe L angle de l arc de cercle parcouru par la voiture en appliquant le contr le v p durant un certain temps t est calcul de la fa on suivante T mA ee a gt F 5 L tat final dz dy d obtenu en appliquant v p durant un temps t peut enfin tre calcul dy Cy p cosa dy cy p sina T dg a gt Ces quations permettent donc de calculer un tat final tant donn un tat initial un controle et une dur e en temps constant plut t que de devoir recourir une technique d int gration num rique pouvant prendre un temps d ex cution arbitrairement long B 3 G n ration d une trajectoire Une trajectoire pour la voiture simple est compos e de deux sous trajectoires un parcours sur un arc de cercle et une trajectoire en ligne droite voir la ligne rouge grasse sur la figure B 1 24 DI Universit de Sherbrooke Rapport de projet pour le cours IFT 729 La premi re sous trajectoire consiste r orienter le v hicule en direction de son objectif d dy en le faisant tourner autour d un cercle de rayon minimal l orientation des roues avant est donc maximal Le deuxi me segment de la trajectoire sera tangent au cercle il convient donc de calculer le point interm diaire m m tel que le segment d finit par les points Ma My et dz dy est tangent au cercle Le calcu
6. temps r el concerne plut t le temps allou au module de suivi de trajectoires pour d terminer le contr le que le robot doit appliquer en tenant compte du facteur d chelle du temps de la simulation e g 1 seconde de temps simul correspond 3 secondes de temps r el tant donn que nous utilisons le 3 mod le d x cution section 2 2 le seul effet du module de suivi de trajectoires mettant trop de temps fournir un nouveau contr le est que le robot continuera d appliquer l ancienne action Cela peut bien entendu entra ner une collision avec un obstacle de l environnement cons quence tr s n faste dans la vie r elle Il s agit donc aussi d une contrainte de temps r elle stricte m me si dans l impl mentation il n y a pas de cons quence fatale pour l ex cution de l application si le temps permis est coul 13 DI Universit de Sherbrooke Rapport de projet pour le cours IFT 729 4 Exp rimentations et analyse des r sultats 4 1 Tests empiriques Nous avons effectu plusieurs exp rimentations dans les environnements de simulation illustr s dans la figure 4 1 Notez que l environnement de la figure 4 1 d est deux fois plus grand que les autres d o la taille r duite des polygones vert et rouge repr sentant le robot dans sa configuration initiale et finale respectivement Nous avons utilis le modele du robot omnidirectionnel non holonome AZIMUT 3 pour effectuer nos exp rimentati
7. ter la r alit De plus certains ajouts pourraient aussi b n ficier le planificateur de trajectoires int gr au robot lui m me http www gel usherbrooke ca laborius 3https planiart usherbrooke ca redmine projects show motionplan azimut3 4 DI Universit de Sherbrooke Rapport de projet pour le cours IFT 729 1 2 Description du projet En robotique mobile le suivi de trajectoires est un probl me qui concerne les impr dictibilit s du monde r el 3 En effet lorsqu une trajectoire est planifi e pour un robot autonome se d pla ant dans son environnement il est fort probable que l environnement mod lis pour effectuer la plani fication et la simulation ne corresponde pas exactement la r alit L environnement peut n tre que partiellement connu a priori tre trop complexe mod liser parfaitement ou avoir chang entre le moment de la planification et de l ex cution de la trajectoire e g un astromobile sur la plan te Mars De plus il est tout fait possible que les capteurs et les actionneurs du robot soient impr cis ce que ajoute de l incertitude ses d placements Un module de suivi de trajectoires permettant au robot de r ajuster son tat afin de rester le plus pr s possible de sa trajectoire calcul e s av re souvent non seulement souhaitable mais n cessaire Dans le cadre du cours IFT 729 nous avons donc voulu impl menter un module de suivi de trajectoires soumis des co
8. vit es Les messages d erreur indiquant que l ex cuteur de plans a d pass sa tranche de temps n ap paraissent g n ralement que lorsque l application a t compil e en mode Debug ou lorsque plu sieurs processus s ex cutent en m me temps sur l ordinateur h te et que celui d OOPSMP se 14 DI Universit de Sherbrooke Rapport de projet pour le cours IFT 729 Fic 4 2 Obstacle entre la roue arri re droite du robot et le point de cheminement fait interrompre Puisque nous utilisons un syst me d exploitation grand public Windows XP ou Vista il ne nous est pas possible d emp cher cette situation De plus nos tests ont d montr que la taille et la complexit de l environnement n influencent pas le temps pris par l ex cuteur de plans pour effectuer son travail ce qui confirme que les op rations s ex cutent en temps constant 4 2 G n ralisation du module de suivi de trajectoires Afin de valider la bonne g n ralisation du module de suivi de trajectoires r alis dans le cadre de ce projet nous avons impl ment un g n rateur de trajectoires pour une voiture simple Les d tails d impl mentation ainsi que les raisonnements math matiques derri re un tel g n rateur de trajectoires sont donn s dans l annexe B Nos exp rimentations avec le mod le de la voiture simple ont d montr que le module de suivi de trajectoires bas sur les points de cheminement fonctionnait effec
9. Add Entry _ Remove Entry pee fe Press Configure to update and display new values in red then press Generate to generate selected build files configure Generate Current Generator Visual Studio 9 2008 ee Fic A 1 Configuration de CMake Une fois les fichiers projet configur s et g n r s boutons Configure et Generate dans CMake respectivement il faut ouvrir le fichier build OOPSMP s1n dans l arborescence du code source du projet dans Visual Studio NET Enfin le code source peut tre compil en s lectionnant l option Build du projet ALL_BUILD Ce projet de la solution se chargera de compiler tous les projets dans Vordre selon les d pendances La configuration Release permettra d obtenir de bien meilleures performances bien entendu Finalement OOPSMP doit tre install en s lectionnant l option Build du projet INSTALL Les binaires de OOPSMP seront copi s par d faut dans le r pertoire C Program Files 00PSMP dont le sous r pertoire bin doit tre ajout au PATH de Windows Cette tape d installation est n cessaire et doit tre r p t e chaque fois que le code source est modifi et compil 19 DI Universit de Sherbrooke Rapport de projet pour le cours IFT 729 A 4 Controller Chooser Une fois le projet compil elle doit tre lanc e partir d une application que nous avons cr qui sert aussi choisir les param tres d ex cution du programme figure A 2 Cette
10. Module de suivi de trajectoires en temps r el pour un robot omnidirectionnel non holonome Francis BISSON Simon CHAMBERLAND Francis Bisson USherbrooke ca Simon Chamberland USherbrooke ca Laboratoire PLANIART D partement d informatique Universit de Sherbrooke Sherbrooke QC Canada J1K 2R1 http planiart usherbrooke ca Rapport de projet pour le cours IFT 729 R sum Ce rapport rend compte du travail accompli pour le projet r alis dans le cadre du cours IFT 729 Nous avons impl ment un module de suivi de trajectoires respectant des contraintes de temps r el pour un robot omnidirectionnel non holonome Nous avons d ajou ter des fonctionnalit s la plateforme de simulation OOPSMP afin de permettre l ex cution des trajectoires de fa on non d terministe Le module du suivi de trajectoires peut aussi tre utilis pour d autres types de robots et d objets mobiles Nous avons donc aussi impl ment un g n rateur de trajectoires pour une voiture simple afin d y tester notre module de suivi de trajectoires Les exp rimentations que nous avons effectu es et les r sultats qui en d coulent d montrent qu il est possible d avoir un module de suivi de trajectoires efficace m me s il est soumis contraintes de temps r el Mots cl s Planification de trajectoires suivi de trajectoires robotique contraintes holonomes Auteur contacter Conception de syst mes temps r el DI Un
11. a tiques et dynamiques Cependant l incertitude introduite par le simulateur GaussianSimulator l incertitude sur les d placements des obstacles dynamiques ainsi que le d lai de correction des trajectoires font en sorte que des collisions peuvent tout de m me se produire 2 5 Fichiers modifi s Le tableau 2 1 liste les principaux endroits o des fichiers ont t modifi s dans OOPSMP D autres modifications moins importantes ont t effectu es un peu partout dans le code afin 11 DI Universit de Sherbrooke Rapport de projet pour le cours IFT 729 d adapter les interfaces et d ajouter des fonctionnalit s requises par les nouveaux modules que nous avons impl ment s Les fichiers que nous avons cr devraient g n ralement contenir une ent te en commantaire faisant mention du laboratoire PLANIART R pertoire Raison Selector Modifications aux Controller Chooser src PlanExecution Simulation non d terministe et suivi de trajectoires src Core Path Plugin Voiture simple OOPSMPKCarPathGenerator H OOPSMPKCarPathGenerator cpp OOPSMPKCarStateSpace H et OOPSMPKCarStateSpace cpp TAB 2 1 Fichiers modifi s dans OOPSMP 12 DI Universit de Sherbrooke Rapport de projet pour le cours IFT 729 3 Contraintes de temps r el 3 1 Borne sup rieure sur le temps de simulation La premi re contrainte de temps r el imposer pour notre projet concerne le temps maximal allou l ex cuteur d
12. avancer parce qu il fait face un mur ou si un point de cheminement n est plus accessible cause de la pr sence d obstacles dynamiques il pourrait tre de mise d abandonner les points de cheminement en faveur d une replanification compl te jusqu l tat final Certains algorithmes comme D 5 permettent d utiliser certaines informations d j calcul es afin d acc l rer le processus de replanification De plus nous devrons nous assurer que les bornes de temps du module de suivi de trajectoires sont aussi respect s sur le robot car celui ci poss de de l quipement hardware moins performant que les ordinateurs sur lesquels nous travaillions Il sera aussi n cessaire de v rifier l allocation de temps au module de suivi de trajectoires par rapport aux autres modules afin d ajuster le temps allou l optimisation de la trajectoire corrig e 17 DI Universit de Sherbrooke Rapport de projet pour le cours IFT 729 A Mode d emploi A 1 Pr requis Voici une liste des pr requis en ordre alphab tique pour pouvoir compiler installer et ex cuter le projet Boost 1 42 CMake 2 8 grid bin Kinetics OpenGL GLU et GLUT Visual C NET Tous ces logiciels sauf Visual Studio NET et ces biblioth ques sont fournis avec le code source du projet Notez que nous n avons test l application que sous Windows XP et Vista seulement bien qu il soit possible qu
13. deux op rations d un seul coup avec la commande Motion planner one click solve q qui ne fait qu ex cuter les deux commandes pr c dentes successivement Ce processus doit tre r p t jusqu ce que la console affiche le message query is solved indiquant qu une solution pour la requ te a t trouv e A 5 2 Ex cution d une trajectoire Il existe trois fa ons diff rentes d afficher une trajectoire qui a t calcul e La premi re ne fait que dessiner tous les tats que prendra successivement l objet mobile simul tout au long de sa trajectoire Cette option est accessible via le menu par la commande Draw query solution La deuxi me m thode activ e par la commande Draw query solution in animation affiche dans une animation l ex cution de la trajectoire par l objet La ligne noire indique la trajectoire qui a t planifi e et l objet bleu est l tat actuel du corps simul Le troisi me et dernier mode est celui qui nous int resse le plus dans le cadre de ce projet Il s agit de la commande Draw query solution in non deterministic execution Comme le nom l indique c est cette commande qui permet d utiliser la triade de classes d taill es dans la section 2 pour ex cuter la trajectoire de fa on non d terministe La ligne noire illustre comme pour la deuxi me m thode la trajectoire planifi e et qui devrait tre suivie aussi pr s que possible L object bleu repr s
14. duction 1 1 Mise en contexte La planification de trajectoires est un important probl me de recherche en intelligence artifi cielle qui consiste calculer une trajectoire g om trique d un tat initial une configuration finale pour un objet mobile donn 1 Les trajectoires g n r es doivent aussi tenir compte de l environ nement e g obstacles autres objets en mouvement etc et des contraintes cin matiques de l objet mobile Puisque l espace d tat est dans la plupart des cas continu plut t que discret des algorithmes d chantillonnage al atoire sont souvent utilis s OOPSMP est un logiciel extensible de planification de trajectoires impl mentant plusieurs tels algorithmes 4 Le laboratoire IntRoLab de la Facult de g nie de l Universit de Sherbrooke a con u plusieurs robots mobiles dont un robot omnidirectionnel non holonome nomm AZIMUT 3 figure 1 1 Les modules n cessaires la simulation correcte de la plateforme AZIMUT 3 dans OOPSMP ont d j t impl ment s par Daniel Castonguay et Simon Chamberland dans le cadre d un projet effectu en collaboration avec le laboratoire PLANIART lors de la session d hiver 2009 Fic 1 1 Le robot omnidirectionnel AZIMUT 5 Bien qu il soit maintenant possible de planifier des trajectoires pour le robot AZIMUT 3 dans OOPSMP il serait souhaitable d impl menter de nouvelles fonctionnalit s dans le simulateur permettant de mieux refl
15. e plans pour effectuer son travail Dans l optique de mod liser fid lement la r alit l ex cuteur de plans doit r aliser l int gration num rique i e calculer le prochain tat du robot apr s un certain temps et la v rification des collisions avec des obstacles de l environnement en temps constant Pour ce faire nous avons tabli une borne sup rieure sur le temps de calcul requis pour faire la simulation et nous utilisons ce temps maximal pour chaque tranche de temps allou e au simulateur Bien qu il s agit d une contrainte de temps r el stricte puisqu un non respect de celle ci ne permet pas de bien simuler le monde r el imposer ce genre de contrainte est quasi impossible sur un syst me d exploitation grand public qui ne permet donc pas un contr le pr cis sur les tranches de temps des processus en ex cution Nous for ons tout de m me l ex cuteur de plans ne pas d passer son temps allou l aide d une minuterie ad hoc sans quoi un message d erreur est affich dans la console Aucune allocation dynamique de m moire n est faite dans les m thodes de la classe NonDeterministicRealtimePlanExecutor la m moire est pr allou e et r utilis e pour la dur e de vie de l objet Ceci combin des op rations s effectuant en temps constant garantit le respect de la premi re contrainte de temps r el 3 2 Temps de calcul allou pour le suivi de trajectoires La deuxi me contrainte de
16. ente l tat actuel du corps simul et si le WaypointsFeedbackPlanner a t s lectionn comme module de suivi de trajectoires le polygone magenta indique le point de cheminement suivant vers lequel l objet mobile devrait se diriger A 6 D sinstallation Afin de d sinstaller le projet il ne suffit que de d sinstaller les applications et les biblioth ques install s dans la section A 2 Il faut aussi effacer le r pertoire o se trouve le code source du projet ainsi que le r pertoire o OOPSMP s installe C Program Files 00PSMP par d faut Le sous r pertoire bin peut ensuite tre enlev de la variable d environnement PATH de Windows en toute s curit 22 DI Universit de Sherbrooke Rapport de projet pour le cours IFT 729 B G n ration de trajectoires pour une voiture simple B 1 Hypoth ses Pour le mod le simple de la voiture certaines hypoth ses sont assum es pour simplifier le probl me 3 Tout d abord l tat du v hicule un moment t donn est donn par le triplet x y qui d crit sa position ainsi que sa direction Un contr le appliqu un tat de la voiture pour une certaine dur e est d fini par le couple v p qui donne respectivement la v locit du v hicule et orientation de ses roues avant Ceci implique donc que la voiture a une acc l ration infinie c est a dire qu elle peut effectuer des changements de vitesse instantan s De plus il est assum que l angle de
17. eses teira ins ii ee Ree a a e AIS Ga Pee sat eS Ar Be Mod le math matique ao edit easy eS ee ek BE ao a B 3 G n ration d une trajectoire on eh gen tele a ao AS Vote See bs Bibliographie 14 14 15 17 18 18 18 18 20 21 21 22 22 23 23 23 24 26 DI Universit de Sherbrooke Rapport de projet pour le cours IFT 729 Liste des tableaux 2 1 Fichiers modifi s dans OOPSMP 12 Liste des figures 1 1 2 1 2 2 2 3 2 4 4 1 4 2 4 3 A 1 A 2 A 3 B 1 Le robot omnidirectionnel AZIMUT 3 4 Diagramme UML des classes PlanExecutor Simulator et FeedbackPlanner 6 Diagramme de s quence des mod les d ex cution et de suivi de trajectoires 8 Champ de potentiel pour un environnement 2D simple 10 Points de cheminement sur une trajectoire 11 Environnements de simulation 4 20 2 ee Kae ane wie ae Pe Se 14 Obstacle entre le robot et le point de cheminement 15 Voiture coinc e entre deux obstacles 16 Configuration de CMake Ces Oe Maine Anne LAN Ru AS Fee 19 Interface du Controller Chooser 4 LR dE LG RME DANS BaP SOR Soa het 20 Interface graphique de OOPSMP 2 5 4028 amp 2 2 dus Malin pe Mae Rex 4 a 21 Mod le math matique d une voiture simple 23 DI Universit de Sherbrooke Rapport de projet pour le cours IFT 729 1 Intro
18. eux fils d ex cution parall les un pour le module de suivi de trajectoires et un autre pour le simulateur Le premier re oit p riodiquement de la part du simulateur un message lui demandant de calculer un contr le appliquer pour rejoindre la trajectoire initiale tant donn l tat actuel du robot Celui ci ne fait qu appliquer continuellement une action qui est modifi e de temps autre par le module de suivi de trajectoires En plus d tre fid le au monde r el le mod le serait relativement ais implanter dans le robot AZIMUT 3 le simulateur servant simuler la DI Universit de Sherbrooke Rapport de projet pour le cours IFT 729 r alit il n aurait qu tre remplac par les modules du robot servant effectuer des lectures sur les capteurs De la synchronisation doit toutefois tre ajout pour assurer l int grit des donn es En particuler les nouvelles actions g n r es par le module de suivi de trajectoire ne doivent pas corrompre celles en cours de consommation par le simulateur Afin de supporter ce mod le nous avons d apporter quelques modifications aux biblioth ques que nous utilisons dans le projet En effet les biblioth ques Kinetics d velopp e par des membres du laboratoire IntRoLab et PQP Proximity Query Package n taient pas thread safe La biblioth que Kinetics utilisait deux biblioth ques qui causaient des probl mes Pour la premi re CLAPACK un en
19. hique de OOPSMP figure A 3 Cette section d taille les proc dures suivre pour accomplir quelques t ches dignes d int r t 3 OOPSMP GGLUTEventManager enable disable point model motion planner motion planner states motion planner paths query solution query solution in animation query solution in non deterministic execution export query solution animation set time scaling set refresh rate Fic A 3 Interface graphique de OOPSMP A 5 1 Planification d une trajectoire Afin de proc der la planification d une trajectoire il faut tout d abord choisir une requ te constitu e d une paire tat initial tat final Comme c est le cas pour la plupart des fonction nalit s de OOPSMP la s lection d une requ te peut se faire via le menu contextuel ouvert avec 21 DI Universit de Sherbrooke Rapport de projet pour le cours IFT 729 un clic droit sur l interface ou l aide d un raccourci clavier Avec le menu les commandes Que ries next et Queries previous passent respectivement la prochaine et la pr c dente requ te Les raccourcis clavier sont respectivement n et p Ensuite la planification d une trajectoire se fait en deux tapes Il faut d abord effectuer un pr traitement gr ce la commande Motion planner preprocess r puis tenter de r soudre le probl me avec la commande Motion planner solve s Il est possible d effectuer les
20. isque le robot continue d appliquer le contr le pr c dent e g avancer pendant que le module de suivi de trajectoires calcule une nouvelle action ex cuter pour rejoindre la trajectoire initiale Ce mod le d ex cution utilise cependant toujours des appels synchrones entre le module de suivi de trajectoires et le simulateur Dans l impl mentation l ex cuteur de plans demande au module de suivi de trajectoires de calculer pendant un certain temps qui lui est allou un contr le appliquer permettant au robot de r int grer sa trajectoire originale Une fois le calcul effectu le simulateur applique le contr le pr c dent pendant le temps utilis par le module de suivi de trajectoires de fa on simuler l ex cution de cette m me action pendant que le planificateur DI Universit de Sherbrooke Rapport de projet pour le cours IFT 729 Program MotionPlanner FeedbackPlanner PlanExecutor i i solve env x0 xg 1 T 1 j i trajectory i i i i i temps non constant en plus il faut v rifier les obstacles updateState prend un i computeFeedbackPlan env trajectory Premi re version appels synchrones D 1 execute Trajectory trajectory getAction current state 4 action aS updateState action t_delta i i i getAction current state 4 Deuxi me version ap
21. iversit de Sherbrooke Rapport de projet pour le cours IFT 729 Table des mati res 1 Introduction JL Mis encont xte aus no GA tas ve ae a ei ets Gi Ets Bs al ee Se oes Fe amp 1 2 Deseri plone projet e 2 a RE oa a cu patte on Mae Me eae eee ss 1 3 Objectifs Wipes io me 2 0 2 Yo uae ey fe ee oe ee owe Bee he Impl mentation 2 1 Architecture haut niveau 2 2024 4 24 44 LIRE 444 2 2 Ex cuteur de plans eatin a ae Rely 2 3 Simulateur non d terministe 2 4 Module de suivi de trajectoires 2 5 Fichiers modifi s Contraintes de temps r el 3 1 Borne sup rieure sur le temps de simulation 3 2 Temps de calcul allou pour le suivi de trajectoires 4 Exp rimentations et analyse des r sultats 4 1 Tests empiriques seb eck ae Be ee Te 4 2 G n ralisation du module de suivi de trajectoires 5 Conclusion A Mode d emploi A PTS 5 settee ty Disease Na Caen de MEN dame ASS instalation are Nr M nt MARI EN ee De ee kt A Ree eee 2 A 3 Compilation du projet LE Hu es DINAN ee Ia MT ee A 4 Controller Chooser sca Los didn BS MO PPE Ne CAS se DWE ee Paco EXEGIT Re SN RS os Sek RUE ECR Nc Rd mens Ni NN NT ere A 5 1 Planification d une trajectoire A 5 2 Ex cution une trajectoire 4 4 5 oS Ve oa ee he en ae AG D sinstall tion aus nad ea a ler edad Ser A we ey Bw ae ae dw nn B G n ration de trajectoires pour une voiture simple B L Hypoth
22. l du point Mz My s effectue partir du centre du cercle trouv dans l quation B 1 de l angle 8 du segment form par les points c c et ds dy ainsi que de l angle voir la figure B 1 y est calcul partir de p et de la longueur du segment CD L tat de la voiture au point m m peut enfin tre calcul partir des r sultats trouv s dans les quations B 1 et B 2 Mz Cz p cos 8 sign p 7 My Cy p sin 8 sign p 7 mo 8 sign y 5 1 Le calcul de la sous trajectoire en ligne droite entre les points m m et dv dy est trivial et n est donc pas d taill dans le pr sent document 25 DI Universit de Sherbrooke Rapport de projet pour le cours IFT 729 Bibliographie 1 Malik GHALLAB Dana NAU et Paolo TRAVERSO Automated Planning Theory and Practice Morgan Kaufmann 2004 Jean Claude LATOMBE Robot Motion Planning Kluwer Academic Publishers 1991 Stephen M LAVALLE Planning Algorithms Cambridge University Press 2006 Erion PLAKU Kostas E BEKRIS et Lydia E KAVRAKI OOPS for motion planning An online open source programming system Dans JEEE International Conference on Robotics and Automation pages 3711 3716 2007 Anthony STENTZ The focussed D algorithm for real time replanning Dans International Joint Conference on Artificial Intelligence pages 1652 1659 1995 26
23. ndique impose une contrainte de temps r el sur le temps allou pour l ex cution d une trajectoire Nous avons tudi trois mod les d ex cution et de suivi de trajectoires par le robot Ces mod les sont d crits dans le diagramme de s quence de la figure 2 2 Le premier mod le est constitu d appels synchrones entre le module de suivi de trajectoires et le simulateur Le probl me est qu un temps de calcul non constant est n cessaire pour trouver le nouvel tat du robot tant donn un contr le e une action appliquer En effet des m thodes d int gration num rique sont parfois n cessaire voir la section B 2 pour un contre exemple pour mettre jour son tat Il faut de plus v rifier les collisions avec les obstacles qui se trouvent dans l environnement Il n est donc pas toujours possible de savoir en temps constant quelle position se trouvera le robot apr s un certain d lai At Ceci est probl matique dans le sens o la r alit tant videmment en temps r el le robot peut lire ses capteurs et connaitre en un temps constant sa position l orientation de ses roues etc Il n y a pas d int gration co teuse calculer ni de test de collision avec l environnement effectuer Ceci nous am ne donc au deuxi me mod le d ex cution o le simulateur tient compte du temps de calcul requis par le module de suivi de trajectoires Ce mod le permet donc de mieux repr senter la r alit pu
24. ndre Les fl ches indiquent au robot dans quelle direction il devrait se d placer dans tous les tats possibles afin de rejoindre sa trajectoire initiale Fic 2 3 Champ de potentiel pour un environnement 2D simple Cette technique est appropri e pour un syst me soumis des contraintes de temps r el puis qu elle permet d obtenir dans un temps constant l action que le robot doit ex cuter pour rejoindre sa trajectoire initiale s il s en est gar Cependant la planification de trajectoires en robotique mobile op re souvent sur un environnement continu et non discret c est le cas ici L espace d tat a donc une dimension infinie Associer une action chaque tat n cessite alors une discr tisation de l environnement des niveaux de granularit plus ou moins fins De plus le calcul du champ de potentiel requiert bien entendu un temps de calcul consid rable Pour ces raisons et cause d un manque de temps nous avons opt pour une autre technique de calcul du contr le que le robot doit appliquer pour rejoindre sa trajectoire initiale Nous avons con u un algorithme ad hoc bas sur les points de cheminement waypoints La figure 2 4 donne un exemple d une telle m thode dans un environnement 2D simple Le triangle vert indique la position initiale du robot et le cercle rouge donne l tat final atteindre Les toiles magenta sont les points de cheminements situ s sur la
25. ntraintes de temps r el section 3 qui pourrait tre utilis par le robot AZIMUT 3 Id alement le module devrait tre suffisamment g n rique pour fonctionner avec d autres types de corps mobiles De fa on abstraite le module de suivi de trajectoires devrait fournir une fonction f X U o X est l espace d tats et U est l espace des contr les qui tant donn un tat x X donne un contr le i e une action u U appliquer pour r int grer la trajectoire initiale Une complexit algorithmique O 1 serait souhaitable pour cette fonction 1 3 Objectifs vis s Voici une liste des principaux probl mes adress s et objectifs vis s par ce projet 1 Concevoir un simulateur non d terministe l int rieur de OOPSMP 2 Exp rimenter avec divers mod les d ex cution non d terministe permettant de repr senter plus ou moins fid lement le monde r el 3 Impl menter un module de suivi de trajectoires pour le robot AZIMUT 3 4 Assurer des contraintes de temps r el pour effectuer le suivi de trajectoires 5 G n raliser le module de suivi de trajectoires pour le rendre fonctionnel avec d autres types d objets mobiles Comme nous l avons d j indiqu dans le Livrable 01 il nous a t impossible d implanter notre projet sur le robot AZIMUT 3 nous avons dt rester en environnement de simulation Les objectifs 1 et 2 ont galement t discut s dans le Livrable 01 mais seront trait s s
26. ommairement dans le pr sent rapport en guise de rappel DI Universit de Sherbrooke Rapport de projet pour le cours IFT 729 2 Impl mentation 2 1 Architecture haut niveau Puisque nous travaillons dans un environnement de simulation et non directement sur le robot lui m me nous avions besoin d un moyen d introduire de l incertitude sur les actions ex cut es par le robot simul afin de repr senter fid lement la r alit En effet un robot r el agira de fa on plus ou moins incertaine que ce soit cause de ses capteurs bruit s de ses actionneurs impr cis ou de l environnement dans lequel la planification a t effectu e qui diff re de l environnement r el Afin de permettre l introduction d incertitude dans l ex cution des trajectoires par le robot nous avons ajout un module de simulation g n rique compos d une triade de classes de base un ex cuteur de plans PlanExecutor un simulateur Simulator et un module de suivi de trajectoires FeedbackPlanner Un diagramme UML de ces classes est illustr dans la figure 2 1 Simulator FeedbackPlanner m_state State m_feedbackPlan FeedbackPlan m_controls Control computeFeedbackPlan in solutionPath Path FeedbackPlan setControls in controls Control signalState in currentState State updateState in time double correctControls in currentState State Control getCurrentState State
27. ons a Environnement 1 b Environnement 2 c Environnement 3 d Environnement 4 Fic 4 1 Environnements de simulation Un manque de temps nous a emp ch de fournir des tableaux et des graphiques de r sultats empiriques pour nos exp rimentations N anmoins nous avons effectu plusieurs tests nous ame nant conclure que le module de suivi de trajectoires fonctionne bien et que les contraintes de temps r el nonc es dans la section 3 sont bien respect es En effet puisque le robot AZIMUT 3 entre relativement rarement en collision avec des obstacles statiques de son environnement m me si celui ci est tr s complexe cela signifie que le module de suivi de trajectoires r ussi r agir suffisamment vite selon les contraintes impos es pour emp cher une collision Les collisions avec les obstacles statiques surviennent la plupart du temps lorsqu un obstacles est plac entre le robot et son prochain point de cheminement Dans cette situation illustr e dans la figure 4 2 le robot peine faire un d tour pour viter l obstacles et rejoindre sa destination Cependant les obstacles dynamiques de par leurs comportements al atoires impr visibles causent plus souvent des collisions avec le robot Il est important de noter que notre algorithme de suivi de trajectoires ni celui de planification de trajectoires d ailleurs ne tient pas compte des obstacles dynamiques ce qui explique les collisions qui ne sont pas
28. pels synchrones gt T mais tenir compte du temps de calcul i i 1 1 lexecuteTrajectory trajectory getAction current state new_action t_calcul j j i i i i pi updateState old_action t_calcul updateState new_action t_delta i i i i i i i i i i i i i i i getAction current state 4 i Troisi me version deux threads D r veil p riodique du 2e thread avec updateState en temps constant j i i 1 i 7 i lexecuteTrajectory trajectory hi fi T i 1 correctControl state updateState action t_delta lt getAction state updateState action t_delta updateState action t_delta setAction action updateState action t_delta i correctControl state updateState action t_delta f updateState action t_delta lt getAction state updateState action t_delta Fe setAction action updateState action t_delta Fic 2 2 Diagramme de s quence des mod les d ex cution et de suivi de trajectoires effectuait son travail Le simulateur peut ensuite appliquer le nouveau contr le calcul par le module de suivi de trajectoires Le troisi me et dernier mod le utilise des appels asynchrones entre le module de suivi de trajec toires et le simulateur de fa on tre aussi fid le la r alit que possible Ce mod le n cessite la cr ation de d
29. robot qui est l action e g tourner acc l rer etc que le robot doit appliquer pour une certaine dur e donn e Dans le cas d terministe une autre sous classe concr te ne fait que transmettre le contr le fourni par le planificateur au ro bot sans lui ajouter de bruit Pour l instant le seul simulateur non d terministe que nous avons impl ment applique du bruit gaussien sur le contr le du robot avec un cart type param trable voir la section 4 Il serait bien s r possible d ajouter d autres types de simulateurs pseudo al atoires mais nous n avions pas acc s des donn es de simulations r elles partir desquelles tablir une distribution probabiliste http www netlib org clapack Shttp wuw cs umd edu mount ANN DI Universit de Sherbrooke Rapport de projet pour le cours IFT 729 2 4 Module de suivi de trajectoires La classe FeedbackPlanner est le c ur de notre projet Il s agit du module servant rectifier la trajectoire du robot qui s en serait gar suite a une ex cution non d terministe Pour concevoir ce module nous voulions utiliser une technique inspir e des champs de poten tiel 2 La figure 2 3 illustre un exemple de champ de potentiel dans un environnement bidimen sionnel simple Les cases noires sont des obstacles et les cases grises sont des positions a viter Le triangle vert indique la position initiale du robot et le cercle rouge donne l tat final at tei
30. semble d outils d alg bre lin aire nous n avons eu qu utiliser la version la plus r cente distribu e gratuitement sur Internet sous une licence libre La deuxi me ANN Approzimate Nearest Neighbor utilisait des variables globales pour viter des listes trop volumineuses de param tres formels dans les fonctions de l interface Nous avons donc cr une structure de donn es contenant l ensemble des param tres passer entre les fonctions En ce qui concerne la biblioth que PQP nous nous sommes inspir s du concept de preuve qui a t vu en classe En effet cette biblioth que est utilis e exclusivement travers l appel StateSpace applyState x qui est suivi typiquement d une v rification de collisions ou d un affichage l cran Introduire un auto verrou dans la m thode applyState x est insuffisant puisque l tat en question est utilis plus loin et nous souhaitons qu il ne soit pas modifi La solution que nous avons retenue consiste ajouter un param tre Lock l appel de applyState x qui permet de s assurer que l appelant a acquis le verrou a priori Le verrou est rel ch dans le destructeur de Lock nous comptons donc sur l appelant pour r duire la port e de l objet Lock au maximum 2 3 Simulateur non d terministe La classe abstraite Simulator ou plut t sa sous classe concr te non d terministe est celle qui introduit du bruit pseudo al atoire au contr le du
31. tivement avec d autres types de corps mobiles que celui pour lequel il a t con u en premier lieu Cependant nous avons remarqu que la voiture entrait en collision avec des obstacles dans l environnement beaucoup plus souvent que le robot AZIMUT 3 Cela s explique sans doute par le fait que le robot AZIMUT 3 peut se d placer dans toutes les directions alors que la voiture ne peux qu avancer et reculer soit en ligne droite ou sur un arc de cercle Certaines situations par exemple celle illustr e dans la figure 4 3 font 15 DI Universit de Sherbrooke Rapport de projet pour le cours IFT 729 en sorte que la voiture peut mettre beaucoup de temps et entrer souvent en collision avec un ou des obstacles avant de r ussir se rendre sa destination En effet la voiture ne pouvant se d placer lat ralement elle doit continuellement reculer et avancer en esp rant r ussir se r orienter dans la direction du point de cheminement suivant de fa on analogue un stationnement en parall le avec une vraie voiture Fic 4 3 Voiture coinc e entre deux obstacles 16 DI Universit de Sherbrooke Rapport de projet pour le cours IFT 729 5 Conclusion Avant de pouvoir impl menter l algorithme sur le robot r el nous devrons am liorer le module de suivi de trajectoires afin qu il fonctionne correctement dans la plupart des cas probl matiques que nous avons identifi s En particulier si le robot ne peut plus
32. trajectoire continue du robot illustr e par la ligne bleue 10 DI Universit de Sherbrooke Rapport de projet pour le cours IFT 729 Cette technique consiste discr tiser la trajectoire solution de fa on en extraire r guli rement e g toutes les x secondes des tats qui serviront de points de cheminement Afin de se rendre destination le robot devra donc passer par l ensemble de ces points de cheminement de fa on s quentielle Fic 2 4 Points de cheminement sur une trajectoire Dans l interface graphique le point de cheminement courant est repr sent avec la couleur ma genta Le module de suivi de trajectoires tente constamment de g n rer une action lui permettant de se rapprocher le plus possible de ce point La g n ration de cette action est confi e au g n rateur de trajectoires Selon l impl mentation de celui ci la g n ration d action peut prendre un temps constant ou d pendre des param tres de la fonction tat initial et tat final d sir Nous pouvons toutefois certifier qu une borne maximale sur le temps d ex cution existe puisque les diff rents g n rateurs de trajectoires utilis s ne font normalement pas usage de boucles de contr le for while etc Si l vitement d obstacles est activ par l option Avoid obstacles dans le Controller Chooser le g n rateur de trajectoires calculera des trajectoires n entrant pas en contact avec les obstacles st
Download Pdf Manuals
Related Search