En robotique, on est souvent amené à devoir planifier des trajectoires pour permettre à un robot mobile de se déplacer d'un point initial à un point final. La planification de trajectoire est un sujet qui est souvent traité dans le domaine scientifique. Il existe donc pas mal d'algorithmes différents permettant de réaliser une telle tâche. Dans cet article, je présenterais certaines de ces méthodes en expliquant brièvement leur principe ainsi que leurs avantages et leurs inconvénients.

Les algorithmes existants

Méthode par décomposition de l'environnement en cellule.

Une première méthode de planification de trajectoire consiste à décomposer l'environnement du robot en cellules [Latombe 1991] (en un ensemble de régions connexes adjacentes). Il suffit ensuite de trouver un algorithme travaillant sur la discrétisation de l'environnement. Là, différentes techniques existent, par exemple, la partition de Voronoï [Choset 1996] ou les graphes de visibilité [Chazzzelle et Guibas 1989].

Dans ces cas, l'environnement discrétisé est représenté dans un graphe et trouver une trajectoire revient à chercher un chemin dans un graphe, problème qui peut être facilement traité informatiquement [Shin et McKay 1986].

D'autres algorithmes de planification travaillent dans un environnement discrétisé. Parmi les plus connus, on peut citer A* [Hart 1968] qui planifie une trajectoire optimale connaissant l'environnement  ou D* [Stentz et Anthony 1994] qui planifie une trajectoire dynamiquement, ce qui lui permet de découvrir son environnement au fur et à mesure.

Les avantages de tels algorithmes sont entre autre la facilité d'implémentation et de représentation. On travaille sur une grille et chaque case est en 8-connexité. C'est-à-dire que d'une case, on a que 8 choix de déplacement possible.

Par contre, ces algorithmes possèdent de gros défauts. Notamment le fait que les contraintes cinématiques du robots ne sont pas prises en compte (accélération, vitesse, vitesse angulaire maximale, encombrement etc.), ce qui autorise le planificateur à trouver une trajectoire qui ne sera pas exécutable par le robot.
De plus, le fait de discrétiser l'espace de recherche limite beaucoup le nombre de trajectoire possible.

La méthode des champs de potentiel

Les champs de potentiel [Khatib 1986] est une méthode est assez originale qui assimile le robot à une particule soumise à un champ de forces répulsives et attractives.

Un obstacle génère un champ de potentiel répulsif tandis que l'objectif à atteindre génère un champ de potentiel attractif. L'algorithme calcul donc un vecteur résultant qui indiquera au robot comment effectuer son déplacement.

Cet algorithme est totalement réactif et peut donc être très facilement implémenté en temps réel. Cependant, comme l'environnement est très peu souvent totalement convexe, cette méthode entraine facilement le robot dans des minimas locaux. De plus, les problèmes d'oscillation peuvent, dans certain cas, être constatés.
Ici non plus, on ne tient pas compte des contraintes du robot.

La méthode de la fenêtre dynamique

Cette méthode [Fox et al. 1997] travaille dans l'espace de commande du robot. La méthode calcule les vitesses possibles du robot pour que celui-ci ne rentre en collision avec aucun obstacle. Une fois l'espace de recherche des vitesse calculé, l'algorithme trouvera la commande optimale à envoyer au robot en minimisant une fonction de coût sur ce domaine de recherche. (minimisation du temps de parcourt, de l'énergie dépensée, maximisation de la vitesse etc.)

Cette méthode un peu plus abstraite permet de prendre en compte les contraintes cinétiques du robot. Par contre, elle manque en flexibilité, ce qui rend difficile son implémentation dans un cadre multi-robot.

La méthode de la bande élastique

Une méthode [Quinlan 1994] qui tend une "bande élastique" entre le robot et l'objectif. Cette bande étant capable de se déformer en présence d'un obstacle, celle-ci génère dont une trajectoire envisageable par le robot.

La planification par logique floue

Cette méthode de planification se base sur la logique floue [Zadeh 1965] : Chaque grandeur physique (par exemple une distance d'un obstacle) est converti en une variable linguistique (petit, moyen ou grand par exemple).
Alors qu'en logique booléenne classique, une distance serait soit petite, soit grande, la logique floue autorise une distance à être à la fois grande et petite (20% petite et 80% grande) suivant une fonction d'appartenance précise.

La planification floue va donc raisonner non pas sur des grandeurs physiques, mais sur des variables linguistiques. On appliquera des règles précises sur ces variables. Finalement, on obtiendra la commande sous la forme de variables linguistiques de l'on reconvertira en grandeurs physiques (lors de la défuzzification).

Cette approche permet de ne pas résonner au niveau de la grandeur physique, mais plus comme un humain le ferait.
Exemple : Si la distance au feu est faible et le feu est rouge, je freine fort.
Ici, on ne raisonne pas sur la valeur de la distance directement. (On ne va pas se dire, dans la vie de tous les jours : si je suis à moins de 6mètre du feu, alors, je fais telle action. Un humain raisonnera plutôt comme ça : si je suis moyennement proche, si je suis assez proche, si je suis très proche alors, je fais telle action)

La logique floue permet donc d'obtenir des trajectoires progressives qui évitent les obstacles.

La planification par juxtaposition de splines polynomiales

L'algorithme de Michael Defoort [Defoort 2007, 2009] génère des bouts de splines polynomiales qui respectent les contraintes cinématiques du robot. On peut simplifier l'algorithme en le forçant à générer non pas des splines, mais simplement des polynômes.
La trajectoire du robot est alors assimilé à la juxtaposition de plusieurs polynômes.

Un bout de trajectoire est alors représenté par un système paramétré de deux polynômes du troisième degré. Les coefficients des degrés zéro et un fixent la position initiale et la vitesse initiale du robot (ce qui permet de garder la continuité entre les différents polynômes). Ainsi, il ne reste plus qu'à optimiser les coefficients du second et du troisième degré du polynôme à l'aide d'algorithmes d'optimisation comme CFSQP [Lawrence, Zhou et Tits].

Cette méthode permet donc de respecter les contraintes cinématiques du robot. De plus, l'optimisation des paramètres des polynômes peut prendre en compte des fonctions de coût, ce qui permet de choisir selon quelle critère l'on décide qu'une trajectoire est optimale ou non.

DKP : Deterministic Kinodynamic Planning

Cette méthode de planification [Gaillard et al 2009] est assez complexe, mais permet de respecter toutes les contraintes du robot et d'éviter les problèmes des minimas locaux.

DKP peut être décomposé en deux parties. La première planifie localement des bouts de trajectoires polynomiales (d'ordre deux) sur différents temps de parcourt. Pour trouver un bout de trajectoire optimal, il suffit de chercher une solution optimale dans l'espace des paramètres des polynômes via une résolution géométrique des contraintes. Avec ce planificateur local, on construit un arbre de solutions locales.

La seconde partie de l'algorithme est un planificateur global basé sur un A*-like qui va choisir les bouts de trajectoire à adopter pour résoudre le problème.

L'avantage de cet algorithme est qu'il génère une grande diversité de bouts de polynôme, ce qui permet de trouver une solution même dans les environnements très complexes.

Conclusion

Cet article ne fait pas un état de l'art rigoureux des méthodes de planification de trajectoire. C'est juste un aperçu non exhaustif de ce qui existe déjà.

Parmi ces algorithmes, j'ai déjà personnellement testé la méthode des champs de potentiel et la planification par logique floue sur des robots réels ainsi que la planification par juxtaposition de splines polynomiale et l'algorithme DKP sur simulateur. Ces différents algorithmes ont leurs avantages et leurs inconvénients. Aucun n'est meilleur que l'autre, tout dépend de l'application. De plus, dans certains cas, une seule méthode de planification ne suffit pas, mais il est avantageux d'enchainer des techniques de planifications différentes.

La planification de trajectoire est domaine de recherche très actif et de nouvelles méthodes apparaissent régulièrement. Je vous conseille donc, si vous êtes intéressés par ce domaine, de vous tenir au courant des avancés dans ce domaine 🙂

Bibliographie

[Latombe 1991] Robot Motion Planning (Livre)
[Choset 1996] Sensor Based Motion Planning : the Hierarchical Generalized Voronoi Graph (Thèse de doctorat, California Institure of Technology)
[Chazzzelle et Guibas 1989] Visibiliy and ontersection problems in plane geometry (Article, Discrete and Computational Geometry)
[Shin et McKay 1986] A dynamic programming approach to trajectory planning of the robotic manipulators (Article, IEEE Transactions on Automatic Control)
[Hart 1968] A Formal Basis for the Heuristic Determination of Minimum Cost Paths (Article, IEEE Transactions on Systems Science and Cybernetics)
[Stentz et Anthony 1994] Optimal and Efficient Path Planning for Partially-Known Environments (Article, Proceedings of the International Conference on Robotics and Automation)
[Khatib 1986] Real-time obstacle avoidance for manipulators and mobile robots (Article; International Journal of Robotics Research)
[Fox et al. 1997] The dynamic window approach to collision avoidance (Article, IEEE Robotics and Automation Magazine)
[Quinlan 1994] Real-Time Path Modofication of Collision-Free Paths (Thèse de doctorat, Université de Stanford)
[Zadeh 1965] Fuzzy sets (Article, Information and Control)
[Defoort 2007] Contributions à la planification et à la commande pour les robots mobiles cooperatifs (Thèse de doctorat, Ecole centrale de Lille)
[Defoort 2009] Motion planning for cooperative unicycle-type mobile robots with limited sensing ranges: A distributed receding horizon approach (Article, Robotics and Autonomous Systems)
[Lawrence, Zhou et Tits] User's Guide for CFSQP Version 2.5: A C Code for Solving (Large Scale) Constrained Nonlinear (Minimax) Optimization Problems, Generating Iterates Satisfying All Inequality Constraints
[Gaillard et al. 2010] Deterministic Kinodynamic Planning (Workshop of the UK Planning and Scheduling Special Interest Group, Italy)

1 commentaire à “Algorithmes de planification de trajectoires : bref état de l'art”

  1. Bonjour,
    existe il une petite étude comparative entre les travaux réalisés pour ce stade ?
    Merci d'avance et bien cordialement

Laisser un commentaire

Vous pouvez utiliser ces tags et attributs HTML&nsbp;: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)

© 2011-2012 Ferdinand Piette