RRT*

• Aussi appelé: RRT star, RRT-star, optimal RRT
• Catégorie: Planning & manipulation › Motion planning
• Mots-clés: motion-planning, sampling-based-planning, path-planning, optimization, manipulation

Une version asymptotiquement optimale du planificateur Rapidly-exploring Random Tree qui recâble son arbre au fur et à mesure de sa croissance, de sorte que le chemin qu'il renvoie ne cesse de s'améliorer vers celui de moindre coût.

Définition

RRT\ (prononcé « RRT star ») est un algorithme de planification de mouvement par échantillonnage qui trouve des chemins sans collision et, avec suffisamment d'échantillons, converge vers un chemin optimal. Il a été introduit par Sertac Karaman et Emilio Frazzoli en 2011 comme extension de l'algorithme Rapidly-exploring Random Tree (RRT) proposé par Steven LaValle en 1998.

Le RRT d'origine fait croître un arbre depuis la configuration de départ en échantillonnant à plusieurs reprises un point aléatoire dans l'espace des configurations, en trouvant le nœud le plus proche dans l'arbre et en l'étendant d'un petit pas vers l'échantillon si ce mouvement est sans collision. RRT trouve rapidement des chemins réalisables, même dans des espaces de grande dimension comme l'espace articulaire d'un bras robotique, mais ses chemins sont généralement en dents de scie et loin du plus court, et ils ne s'améliorent pas lorsque l'on ajoute des échantillons.

RRT* change deux choses. Lorsqu'un nouveau nœud est ajouté, il examine tous les nœuds de l'arbre situés dans un rayon de voisinage et se connecte à celui qui donne le coût le plus faible depuis le départ, et non simplement au plus proche. Il effectue ensuite un recâblage (rewiring) : pour chaque voisin, si passer par le nouveau nœud donne un chemin moins coûteux, le parent de ce voisin est changé. Karaman et Frazzoli ont montré qu'avec un rayon de voisinage qui diminue de manière appropriée à mesure que l'arbre grandit, le coût de la solution converge vers l'optimum lorsque le nombre d'échantillons tend vers l'infini, une propriété appelée optimalité asymptotique.

Le prix à payer est un calcul supplémentaire par échantillon, de sorte que RRT est plus lent que RRT pour trouver une première solution. Des variantes comme Informed RRT et BIT* concentrent l'échantillonnage pour accélérer la convergence.

Pourquoi c'est important

De nombreux robots n'ont pas besoin de n'importe quel chemin mais d'un bon chemin : plus court, plus lisse ou moins coûteux en énergie. RRT* offre aux planificateurs par échantillonnage, qui passent à l'échelle d'espaces des configurations de grande dimension, une voie fondée sur des principes vers la qualité des chemins, et c'est une référence standard dans la recherche et les logiciels de planification de mouvement.

Applications principales

• Planification de mouvement sans collision pour des bras robotiques dans des espaces de travail encombrés
• Planification de chemin globale pour les robots mobiles et les drones
• Planification dans des espaces des configurations de grande dimension où la recherche sur grille est impraticable
• Génération de chemins de référence pour l'optimisation de trajectoire

En pratique

Les équipes de robotique utilisent généralement RRT via une bibliothèque de planification plutôt que de l'écrire elles-mêmes. L'Open Motion Planning Library (OMPL), que MoveIt utilise pour les bras robotiques, inclut RRT et plusieurs de ses variantes aux côtés de RRT, RRT-Connect et PRM. Un schéma courant consiste à exécuter RRT avec un budget de temps fixe, à prendre le meilleur chemin trouvé à l'expiration du temps, puis à le raccourcir et le lisser avant de le convertir en trajectoire paramétrée en temps. Pour les robots mobiles et les drones, les équipes utilisent aussi RRT sur une carte d'occupation 2D ou 3D comme planificateur global, en choisissant le temps de planification et la taille de pas pour arbitrer entre qualité du chemin et temps de réponse.

Idées reçues

• RRT* renvoie le chemin optimal — il est asymptotiquement optimal, le coût du chemin ne s'approche donc de l'optimum que lorsque le nombre d'échantillons croît sans limite
• Les chemins de RRT* sont lisses — ils sont linéaires par morceaux et nécessitent généralement raccourcissement et lissage avant exécution
• RRT* est toujours meilleur que RRT — lorsqu'il suffit d'obtenir rapidement un chemin réalisable, le RRT simple ou RRT-Connect est souvent le meilleur choix

Qui devrait le savoir

• Ingénieurs en planification de mouvement
• Développeurs de logiciels pour bras robotiques et manipulation
• Développeurs de drones autonomes et de robots mobiles
• Étudiants en robotique qui étudient les algorithmes de planification

Technologies associées

• OMPL
• MoveIt
• RRT-Connect
• Informed RRT*
• BIT*
• Vérification de collision (Collision Checking)

Termes associés

• Motion Planning
• Probabilistic Roadmap
• Configuration Space
• Trajectory Planning

Projets associés

• LeRobot: HuggingFace ML library for real-world robotics in PyTorch
• Isaac Lab: NVIDIA robot learning framework: one task API across Newton, PhysX and Isaac Sim
• NVIDIA Isaac GR00T: NVIDIA open foundation model for humanoid robot reasoning and skills
• OpenVLA: 7B-parameter Vision-Language-Action model for robotic manipulation
• Nav2: ROS 2 navigation stack with path planning and obstacle avoidance for mobile robots
• Drake: MIT robotics toolbox for model-based dynamics, optimization, and control system design

Vidéos

• Path Planning with A* and RRT | Autonomous Navigation, Part 4: MATLAB