La navigation autonome
Intéressons nous maintenant au problème de la navigation d’un robot mobile dans son environnement. C’est à dire la capacité d’aller d’une position initiale à une position finale de manière autonome. C’est là, encore, un vaste thème. En effet, les méthodes utilisées pour un robot du type Masokhod [Bonnafous] en environnement d’extérieur (non structuré) inconnu ne sont pas les mêmes que pour un robot cylindrique omnidirectionnel en environnement d’intérieur (structuré). Considérons la cas d’un robot mobile en environnement structuré. Dans le cas idéal d’un environnement exactement modélisé et où la cinématique du robot est parfaitement maîtrisée les étapes de la navigation se résument simplement : le robot planifie une trajectoire puis l’exécute. Mais alors pourquoi nos voitures ne sont-elles pas entièrement automatiques ? Dans la réalité nous faisons, sans nous en rendre compte, des actions extrêmement complexes lorsque nous nous déplaçons : nous estimons notre position, nous analysons en permanence les objets qui nous entourent et nous nous mouvons. Un robot doit faire de même.
Les difficultés de la navigation
Le mouvement : En robotique, il existe deux grandes catégories de robots mobiles à roues. Je ne parlerai pas des robots à pattes.
Les véhicules non-holonomes : Les véhicules dit non-holonomes sont ceux que l’on rencontre le plus dans la vie courante : voiture particulière, bus, camion,… Ces véhicules ont une structure mécanique relativement simple : des roues motrices, des roues directrices et des roues porteuses. Une roue peut avoir une, deux ou les trois fonctions. Mais tous ces véhicules ont une caractéristique commune : la direction de la vitesse d’avance (ou vitesse linéaire) est imposée par la direction des roues directrices. Pour fixer les idées prenons un exemple : pour qu’une voiture particulière aille de sa position initiale à un mètre sur sa droite elle est obligée de faire une manœuvre : une marche avant puis une marche arrière. Les véhicules holonomes : Le deuxième type de véhicules, beaucoup plus rare dans notre vie quotidienne, s’appelle les véhicules holonomes. Ils ont une structure mécanique complexe qui leur permet de se déplacer dans toutes les directions sans manœuvre !
Il existe, néanmoins, un exemple commun (et bien pratique) : le chariot de magasin. Vous pouvez prendre un chariot et le tirer sur la droite, les roues s’orientent alors dans la bonne direction. Un chariot n’a pas une structure mécanique compliquée mais ses articulations sont passives. La société Nomadic, disparue en l’an 2000, a conçu un robot holonome : le XR4000. Il dispose de 4 roues motrices et directrices montées comme des roues de chariot [Holmberg]. La synchronisation des 8 axes (2 par roue, rotation et orientation) est assurée par une carte dédiée basée sur le micro-contrôleur motorola 68332 et des circuits FPGAs et la structure mécanique est composée d’engrenages coniques.
Robot holonome ou non-holonome : les différences La relative simplicité mécanique des robots non-holonomes face aux robots holonomes à un prix. Les algorithmes d’exécution de trajectoire, de commandes et de planification de mouvements sont plus complexes. Mais leur facilité de construction en font des véhicules très répandus dont l’automatisation présente un intérêt socio- économique évident.
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 configurations) 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 configurations 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. 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] 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 différents robots non-holonomes relativement simples (espace des configuration de dimension 3) avec succès.
Utilisation de trajectoires d’évitement
Dans [Laugier], les auteurs proposent une architecture de contrôle pour une voiture autonome évoluant sur le réseau routier. Les éléments de base sont des SMB, Sensor-Base Manoeuvre. Ce sont des capacités « élémentaires », comme par exemple suivre une trajectoire ou se garer, que le robot ordonnance pour effectuer une mission.
La capacité de suivi de trajectoire se décompose en deux sous-capacités : le suivi de trajectoire et l’évitement d’obstacle.
Le véhicule suit une trajectoire initiale produite par le planificateur décrit dans [Scheuer] et utilise une famille de trajectoires d’évitement pour contourner les éventuels obstacles qui obstruent la trajectoire initiale.
Lorsque le véhicule détecte un obstacle immobile ou mobile, les paramètres de la trajectoire d’évitement sont calculés et, selon ses possibilités le robot décide soit de suivre cette trajectoire, soit de ralentir ou même de s’arrêter.
On peut dire que cette méthode d’évitement travaille dans un sous-espace des trajectoires faisables du robot.
Cette méthode a été utilisée sur deux véhicules d’expérimentations : une Ligier et le Cycab [Large] dans des environnements routiers dégagés.
Dans cette méthode, la cinématique et les possibilités d’accélération des véhicules sont rigoureusement respectées mais l’utilisation d’une famille de trajectoires d’évitement empêche l’utilisation de cette méthode pour des environnements contraints qui exigent des capacités de manœuvres plus fines.
Planification de trajectoires à partir de données proximétriques
Bien que cette méthode soit présentée comme une méthode de planification de trajectoires, les techniques utilisées sont proches de celles que nous avons utilisées dans notre méthode d’évitement réactif. C’est pourquoi elle est décrite ici.
Cette méthode est décrite dans [Divelbiss]. Les auteurs décrivent un algorithme pour trouver un chemin cinématiquement faisable pour un système non-holonome quelconque en présence d’obstacles.
La méthode transforme le problème en un système d’équations non-linéaires résolues de manière itérative par la méthode de Newton-Raphson. Les inconnues du système d’équations sont les commandes du système non-holonome considéré. Pour pouvoir résoudre le problème, ces commandes sont approximées pas des séries de Fourier à un ordre donné. Les inconnues sont donc les coefficients de ces séries de Fourier.
Les obstacles sont pris en compte par des fonctions nulles lorsque la trajectoire est sans collision, positives sinon. Ces fonctions appartiennent au système non-linéaire résolu par la méthode de Newton-Raphson.
Table des matières
Introduction
1 Problématique et état de l’art
1.1 Problématique
1.1.1 Histoire et contexte
1.1.2 La navigation autonome
1.1.3 Les difficultés de la navigation
1.2 État de l’art
1.2.1 Les algorithmes de replanification rapide
1.2.2 L’évitement réactif en vitesse
1.2.3 Utilisation de trajectoires d’évitement
1.2.4 La bande élastique
1.2.5 Planification de trajectoires à partir de données proximétriques
1.3 Notre approche et notre contribution
2 Déformation de trajectoire
2.1 Présentation du problème
2.1.1 Système non-holonome et trajectoires
2.1.2 La déformation élémentaire de trajectoire
2.1.3 La déformation de trajectoire comme système asservi
2.1.4 Champ de potentiel et produit scalaire
2.1.5 Résumé du problème
2.2 Résolution : l’algorithme de déformation
2.2.1 Les étapes de la déformation
2.2.2 L’espace de dimension finie des perturbations
2.2.3 Champ de potentiel et déformation élémentaire
2.2.4 Prise en compte des conditions aux limites
2.2.5 Produit scalaire et base orthonormée
2.2.6 Dérive des contraintes non-holonomes
2.2.7 Résumé : l’algorithme de déformation de trajectoire non-holonome
2.3 Exemple : le robot Hilare 2
3 Définition du potentiel d’une trajectoire
3.1 Introduction
3.2 Évitement d’obstacles
3.3 Exemples
3.3.1 Exemple 1 : le robot Hilare 2
3.3.2 Exemple 2 : le robot Hilare 2 muni d’une remorque
3.3.3 Exemple 3 : camion à remorque avec timon
3.4 Utilisation de segments
4 Mise en œuvre à bord du robot Hilare 2
4.1 Difficultés d’implantation à bord du robot Hilare 2
4.2 Hypothèses et contraintes
4.3 Algorithme mis en œuvre
4.3.1 cCheck : recherche des collision
4.3.2 tFollow, ou comment et quand arrêter Hilare 2
4.3.3 tDeform : déformons l’intervalle de trajectoire
4.4 Expérimentation : suivi d’une trajectoire
4.5 Expérimentation : déformation d’une trajectoire
Conclusion
Bibliographie
