Exécution réactive de trajectoires pour robots mobiles non-holonomes

Les algorithmes de replanication rapide

 Les algorithmes de replanication rapide sont basés sur l’algorithme A* de recherche de chemin optimal dans un graphe grâce à une heuristique [Nilsson ]. L’espace de travail du robot W est découpé en cellules. Chaque cellule peut être qualiée soit de libre si le robot peut la franchir soit d’obstacle si elle est infranchissable. Les arcs du graphe représentent un mouvement du robot d’une cellule à une autre. La trajectoire obtenue est toujours optimale pour le critère utilisé pour valuer les arcs du graphe. Ce critère est généralement la distance parcourue mais il peut aussi être déni par l’utilisateur. L’apport de ces méthodes par rapport à l’algorithme A* est la possibilité de modier la solution lorsque le robot détecte des modications de l’environnement sans avoir à recommencer toute la recherche. Ainsi, ces algorithme peuvent être utilisés en ligne contrairement à l’algorithme A* qui est trop coûteux en temps. Deux approches existent. Elles se distinguent par la façon de faire évoluer le graphe au fur et à mesure que le robot acquiert de nouvelles informations.  Dans la première approche, le coût des arcs du graphe évolue. On parle alors de l’algorithme D* [Stentz ] et plus particulièrement la version avec heuristique de recherche Focussed D* [Stentz ]. Plus récemment [Koenig ] propose une méthode équivalente mais algorithmiquement plus simple.  Dans la deuxième approche, les noeuds du graphe sont supprimés ou rajoutés. On peut citer IGPRR (Intelligent Global Path Planner with Replanning) [Podsdkowski ] et [Podsdkowski ]. Un inconvénient majeur de ces méthodes réside dans le fait que la cinématique des robots est très peu prise en compte. Par exemple, dans IGPRR la vitesse du robot est choisie parmi un ensemble ni de couples (vitesse linéaire, vitesse angulaire). De plus les possibilités de planication de ces méthodes sont bien inférieures aux méthodes utilisant un échantillonage aléatoire de l’environnement (en particulier pour des systèmes non-holonomes complexes). 

L’évitement réactif en vitesse 

Ces méthodes associent une méthode d’évitement local d’obstacles avec une information globale sur la connectivité de l’espace de travail (ou des congurations) du robot pour fournir la vitesse linéaire et angulaire du robot. La première méthode, appelée Global Dynamic Window Approach est décrite dans [Brock ]. Elle a été développée pour un robot holonome mais devrait pouvoir s’adapter à un robot non-holonome. Elle associe la méthode d’évitement local d’obstacles appelée Dynamic Window Approach [Fox ] à une carte de potentiels sans minimum local dans l’espace des congurations grâce à la fonction de navigation NF1 [Latombe ]. La deuxième méthode est décrite dans [Xu ]. Elle a été développée dans le cadre d’un projet industriel pour équiper un transpalette. Elle utilise une carte locale des obstacles et un chemin de référence que doit suivre le robot. Lors d’un évitement, le robot utilise des ancres virtuelles sur les obstacles et des sous buts le long du chemin pour ne pas se perdre. 

PROBLÉMATIQUE ET ÉTAT DE L’ART

 La troisième méthode est présentée dans [Mínguez ]. Cette technique appelée Nearness Diagram navigation (ND) s’appuie sur l’analyse des obstacles perçus par le robot (avec plus ou moins de mémoire) pour en déduire les conditions de navigation : navigation en espace contraint ou en espace libre. A chacune de ces conditions de navigation correspond une stratégie de navigation qui, dans tous les cas, produit la vitesse linéaire jugée la meilleure pour la stratégie utilisée. Dans [Mínguez a] les auteurs proposent une architecture logicielle permettant d’étendre l’utilisation de ND à des systèmes non-holonomes. La vitesse linéaire calculée par ND est transformée en une force virtuelle qui tire le robot selon un modèle cinématique et dynamique du mouvement du robot. Des expériences ont été faites sur diérents robots non-holonomes relativement simples (espace des conguration de dimension 3) avec succès. Dans [Mínguez b] les mêmes auteurs décrivent un espace appelé EgoKinematic Space dans lequel les points obstacles et les congurations atteignables par le robot en un seul mouvement (ligne droite ou arc de cercle) sont transformés en un couple de réels par une transformation bijective. Dans cet espace, n’importe quel algorithme d’évitement d’obstacles développé pour un robot holonome peut être utilisé pour des robots non-holonomes. La quatrième méthode est décrite originalement dans [Fiorini ]. Dans cette méthode, la vitesse des obstacles est supposée connue ou mesurable et le concept de Velocity Obstacle permet de dénir l’ensemble des vitesses qui assure, sur un horizon de temps donné, la non-collision du robot avec les obstacles. Dans le cas où la vitesse des obstacles est connue à l’avance, cette technique permet de planier des trajectoires dans un environnement fortement dynamique. Dans le cas contraire, la vitesse des obstacles est estimée et supposée constante sur des petits horizons de temps. On détermine alors pour le prochain intervalle de temps la meilleure vitesse qui assure la non collision et le rapprochement du but. Dans sa thèse, Frédéric Large [Large ] étend cette méthode au cas où la vitesse des obstacles n’est pas constante par morceaux. Il présente alors l’exemple simulé de l’insertion d’une voiture, modélisé par un point, sur une voie à circulation rapide. La dernière méthode est décrite dans [Bemporad ]. Elle s’applique à un robot du type voiture ou unicycle. À partir de deux forces dans le plan de travail appliquées en un point du robot, la première qui tire le robot vers le but et la seconde qui éloigne le robot des obstacles, elle détermine les commandes en vitesse à appliquer au robot. Cette détermination est faite en utilisant la pseudo-inverse du modèle cinématique.