Open Source Robotics

Une collection organisée de projets, outils et logiciels robotiques open source de haute qualité.

Hybrid A*

  • Aussi appelé: Hybrid A-star, hybrid-state A*
  • Catégorie: Planning & manipulation › Motion planning
  • Mots-clés: path-planning, graph-search, autonomous-driving, nonholonomic, parking

Variante de la recherche A* pour les robots de type voiture, qui développe les nœuds en simulant des mouvements de braquage réalisables dans un état continu, tout en élaguant à l'aide d'une grille grossière (x, y, cap).

Définition

Hybrid A est un planificateur de chemin fondé sur la recherche pour les véhicules soumis à des contraintes non holonomes, introduit par Dolgov, Thrun, Montemerlo et Diebel pour l'équipe de Stanford engagée dans le DARPA Urban Challenge 2007, où il gérait les parkings et d'autres zones non structurées. Comme A standard, il maintient une liste ouverte triée par coût plus heuristique. La différence tient à la représentation des états. L'espace de recherche est découpé en cellules selon la position et le cap, mais chaque nœud conserve une pose continue exacte. Un nœud est développé en simulant le véhicule, généralement avec un modèle bicyclette** cinématique, sur un court arc pour quelques angles de braquage, par exemple braquage maximal à gauche, tout droit et braquage maximal à droite, en marche avant et, si c'est autorisé, en marche arrière. Une nouvelle pose n'est conservée que si sa cellule n'a pas déjà été atteinte à un coût inférieur.

Comme chaque arête est un mouvement simulé, le chemin obtenu est praticable par construction, ce que ne peut garantir un simple A sur grille passant par les centres des cellules. La contrepartie est que l'élagage par cellule écarte des états qui auraient pu mener à une solution ; le planificateur n'est donc ni complet ni optimal au sens strict. Des cellules grossières le rendent rapide mais peuvent lui faire manquer des manœuvres serrées. La méthode d'origine utilisait deux heuristiques admissibles et retenait la plus grande : la longueur du plus court chemin d'une voiture sans obstacles, comme un chemin de Reeds–Shepp ou de la voiture de Dubins**, et le plus court chemin tenant compte des obstacles pour un robot capable de tourner sur place, issu d'une recherche 2D sur la grille. Elle tentait aussi périodiquement de relier directement le nœud courant au but par une courbe de Reeds–Shepp, ce qu'on appelle une expansion analytique (analytic expansion), qui aide la recherche à atteindre une pose de but exacte.

Le chemin brut suit les choix de braquage discrets, si bien qu'il zigzague légèrement. Le système d'origine le lissait avec un optimiseur à base de gradient qui équilibrait dégagement, courbure et régularité, puis l'interpolait pour le contrôleur de suivi. Hybrid A se distingue de la planification par treillis d'états (state lattice), qui relie des points fixes du treillis par des primitives de mouvement** précalculées, et des planificateurs dans le repère de Frenet, qui supposent une voie de référence.

Pourquoi c'est important

Hybrid A* est l'un des planificateurs les plus utilisés pour les robots de type voiture dans les parkings, les cours et les autres espaces sans voies. Il montre une manière pratique d'allier la rapidité de la recherche sur grille à des chemins qui respectent les limites de braquage d'un véhicule, et sa structure se retrouve dans de nombreuses piles logicielles de conduite open source.

Applications principales

  • Stationnement automatisé et manœuvres de voiturier
  • Manœuvres de camions, de tracteurs et de remorques dans les cours et les dépôts
  • Robots de type voiture dans les entrepôts, les exploitations agricoles et les chantiers
  • Planification dans les zones non structurées des piles logicielles de conduite autonome
  • Planification de chemin pour véhicules tout-terrain et miniers

En pratique

Un tracteur autonome doit entrer en marche arrière dans un quai de chargement. Le planificateur discrétise la cour en cellules de position et en intervalles de cap, développe les nœuds avec quelques angles de braquage en marche avant et arrière à l'aide du modèle bicyclette, et vérifie à chaque pose simulée les collisions de l'emprise complète du véhicule (footprint). Toutes les quelques expansions, il tente une connexion directe de Reeds–Shepp vers la pose du quai. Une fois un chemin trouvé, il est lissé en courbure et en dégagement, revérifié contre les collisions et doté d'un profil de vitesse avant qu'un contrôleur de suivi de chemin ne l'exécute. Lorsque le planificateur échoue dans les endroits serrés, l'équipe réduit d'abord la taille des cellules ou ajoute des angles de braquage avant de modifier quoi que ce soit d'autre.

Idées reçues

  • Hybrid A est un A ordinaire sur grille — les nœuds stockent des poses continues atteintes par des mouvements de braquage simulés, et la grille ne sert qu'à élaguer les doublons
  • Ses chemins peuvent être cinématiquement irréalisables à cause de la grille — les arêtes sont des mouvements simulés du véhicule, donc la réalisabilité est assurée ; ce que coûte la grille, c'est la complétude et l'optimalité
  • Hybrid A* donne le plus court chemin — l'élagage par cellule et le nombre limité de choix de braquage rendent le résultat approximatif, généralement suivi d'un lissage
  • Il planifie la trajectoire complète avec les vitesses — il planifie un chemin géométrique ; les profils de vitesse et la dynamique sont traités ensuite

Qui devrait le savoir

  • Ingénieurs en conduite autonome travaillant sur le stationnement et les zones non structurées
  • Développeurs de robots mobiles sur plateformes de type voiture ou Ackermann
  • Étudiants en planification de mouvement qui étudient la planification par recherche
  • Ingénieurs en robotique de terrain dans l'agriculture, les mines et la logistique

Technologies associées

  • Recherche A*
  • Courbes de Reeds–Shepp
  • Planificateur à treillis d'états (state lattice planner)
  • Champ de Voronoï (Voronoi field)
  • Lissage de chemin
  • Contrôleurs Pure Pursuit et Stanley

Termes associés

  • Nonholonomic Constraint
  • Dubins Car
  • Bicycle model
  • Motion Primitive
  • Configuration Space
  • Frenet Frame Planning

Projets associés

  • Nav2: ROS 2 navigation stack with path planning and obstacle avoidance for mobile robots
  • ROS Motion Planning: One repo implementing 40+ classic and learning-based robot path planners as ROS plugins
  • OMPL: Sampling-based motion planning library powering MoveIt and countless robotics applications
  • Mesh Navigation: Robot navigation on 3D triangle meshes for rough outdoor terrain, from Nature Robots
  • Fields2Cover: Coverage path planning library for autonomous agricultural vehicles
  • Vision Pilot: Autoware Foundation's open-source L2 ADAS stack from a single camera

Ce site nécessite JavaScript. Veuillez activer JavaScript pour explorer nos projets de robotique open source.