Rapidly-exploring random tree

• Aussi appelé: RRT
• Catégorie: Planning & manipulation › Motion planning
• Mots-clés: motion-planning, sampling-based-planning, path-planning, kinodynamic-planning, collision-avoidance

Un planificateur de mouvement par échantillonnage qui fait croître un arbre depuis l'état de départ en échantillonnant à répétition un état aléatoire et en étendant vers lui le nœud le plus proche de l'arbre, explorant rapidement de grands espaces.

Définition

L'arbre aléatoire à exploration rapide (rapidly-exploring random tree, RRT) est un algorithme par échantillonnage qui trouve un chemin réalisable d'un état de départ à une région but. Il a été introduit par Steven LaValle en 1998. L'algorithme fait croître un arbre enraciné au départ : à chaque itération, il échantillonne un état aléatoire dans l'espace des configurations ou l'espace d'état, trouve le nœud de l'arbre le plus proche et étend ce nœud d'une courte distance vers l'échantillon. Si l'extension est sans collision, le nouvel état est ajouté à l'arbre. La recherche s'arrête lorsque l'arbre atteint la région but, et le chemin est relu en remontant le parent de chaque nœud.

La propriété clé est le biais de Voronoï. Les nœuds de la frontière de l'arbre ont les plus grandes régions de Voronoï ; ce sont donc eux qui ont le plus de chances d'être les plus proches d'un échantillon aléatoire, et l'arbre est attiré vers l'espace inexploré au lieu de remplir les régions déjà couvertes. Cela rend le RRT efficace dans les espaces de grande dimension comme l'espace articulaire d'un bras robotique. Le RRT est probabilistiquement complet : si une solution existe, la probabilité de la trouver tend vers un lorsque le nombre d'échantillons augmente. Les améliorations courantes comprennent le biais vers le but (goal biasing), où une fraction des échantillons est tirée sur le but, et RRT-Connect, qui fait croître des arbres depuis le départ et depuis le but et tente de les relier de façon gloutonne.

Comme l'étape d'extension n'a besoin que d'un moyen d'aller d'un état vers un autre, le RRT traite aussi la planification cinodynamique, où le robot ne peut pas se déplacer en ligne droite dans son espace d'état. L'étape d'extension applique alors des commandes échantillonnées ou optimisées et simule la dynamique vers l'avant, comme dans le RRT cinodynamique de LaValle et Kuffner, ou enchaîne des primitives de mouvement précalculées. Il est ainsi utile pour les véhicules, les robots à pattes et la manipulation riche en contacts, où la métrique de distance et l'étape d'extension doivent être conçues autour de la dynamique. Les chemins du RRT sont généralement en dents de scie et non optimaux, et ajouter des échantillons n'améliore pas un chemin une fois trouvé. RRT\ ajoute une étape de choix du parent et une étape de recâblage (rewiring) qui reconnecte les nœuds voisins chaque fois qu'il existe un trajet moins coûteux, ce qui le rend asymptotiquement optimal au prix de plus de calcul par échantillon. Lorsqu'un chemin réalisable est nécessaire rapidement, le RRT simple ou RRT-Connect suivi de raccourcissement et de lissage reste un choix courant.

Pourquoi c'est important

Le RRT a rendu la planification de mouvement praticable pour les robots à nombreux degrés de liberté et pour les systèmes dotés d'une dynamique, et il reste un planificateur par défaut dans des bibliothèques comme OMPL et MoveIt. De nombreux planificateurs ultérieurs, dont RRT*, reposent sur sa structure.

Applications principales

• Planification de mouvement de manipulateurs dans des espaces de travail encombrés
• Planification cinodynamique pour voitures, drones et robots à pattes
• Planification de manipulation riche en contacts avec des métriques de distance sur mesure
• Planification sur des graphes de primitives de mouvement pour la locomotion
• Exploration d'environnements inconnus

En pratique

Une équipe qui configure MoveIt pour un bras à sept axes prélevant des articles sur des étagères utilise RRT-Connect d'OMPL comme planificateur par défaut. La vérification des collisions utilise le modèle du robot et un octree construit à partir d'une caméra de profondeur. L'équipe fixe la limite de temps de planification et la taille du pas d'extension en fonction du dégagement des ouvertures d'étagère, puis post-traite chaque chemin par raccourcissement et paramétrage temporel pour que le bras se déplace en douceur. Quand la planification peine à atteindre le fond des casiers étroits, elle augmente le biais vers le but ou essaie un planificateur qui se comporte mieux dans les passages étroits, et pour des requêtes répétées dans une cellule statique elle envisage plutôt une feuille de route probabiliste.

Idées reçues

• Le RRT trouve le plus court chemin — il trouve un chemin réalisable ; RRT* ou un post-traitement est nécessaire pour une bonne qualité de chemin
• Le RRT trouve à coup sûr un chemin en un temps donné — il est probabilistiquement complet, il trouve donc un chemin avec une probabilité qui tend vers un à mesure que l'échantillonnage continue, et les passages étroits peuvent prendre longtemps
• RRT* est toujours le meilleur choix — il améliore les chemins au fil du temps mais met plus longtemps à trouver une première solution ; RRT-Connect avec lissage est souvent préféré quand la vitesse compte

Qui devrait le savoir

• Ingénieurs en planification de mouvement
• Développeurs de robots manipulateurs et mobiles qui utilisent MoveIt ou OMPL
• Ingénieurs en planification pour véhicules autonomes et drones
• Étudiants en robotique

Technologies associées

• OMPL
• MoveIt
• RRT-Connect
• Kinodynamic RRT
• Informed RRT*
• Raccourcissement de chemin (Path Shortcutting)

Termes associés

• Configuration Space
• Motion Planning
• Obstacle Avoidance
• RRT*
• Probabilistic Roadmap
• Motion Primitive

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
• MoveIt 2: Motion planning framework for ROS 2 robot arms, with kinematics and collision checking
• PyRoki: Modular Python toolkit for kinematic optimization across CPU, GPU, and TPU via JAX
• mink: Python inverse kinematics library built on MuJoCo supporting 20+ robot platforms

Vidéos

• Motion Planning: Rapidly Exploring Random Trees (RRT): Algorithm Implementation Step by Step!: VDEngineering