Probabilistic Roadmap

• Aussi appelé: PRM, probabilistic roadmap method
• Catégorie: Planning & manipulation › Motion planning
• Mots-clés: motion-planning, sampling-based-planning, path-planning, graph-search, manipulation

Un planificateur de mouvement par échantillonnage qui construit un graphe réutilisable de configurations aléatoires sans collision et des chemins réalisables entre elles, puis répond aux requêtes de planification par une recherche dans le graphe.

Définition

Carte de routes probabiliste (Probabilistic Roadmap, PRM) : méthode de planification de mouvement par échantillonnage introduite par Kavraki, Švestka, Latombe et Overmars en 1996. Au lieu de parcourir à nouveau l'espace des configurations à chaque requête, PRM construit d'abord un graphe, la carte de routes, qui capture la connexité de l'espace libre du robot, puis utilise ce graphe pour répondre à un nombre quelconque de requêtes départ-but.

La planification comporte deux phases. Dans la phase de construction, le planificateur échantillonne des configurations aléatoires du robot, conserve celles qui sont sans collision comme nœuds, et tente de relier chaque nœud aux nœuds voisins avec un planificateur local simple, généralement une ligne droite dans l'espace des configurations dont les collisions sont vérifiées à intervalles fins. Les connexions réussies deviennent des arêtes. Dans la phase de requête, les configurations de départ et de but sont reliées à la carte de routes, et une recherche dans le graphe, comme l'algorithme de Dijkstra ou A*, y trouve un chemin.

PRM convient aux problèmes à requêtes multiples, où l'environnement est statique et le robot doit planifier de nombreux mouvements dans le même espace, car la coûteuse construction de la carte de routes n'est faite qu'une fois. Il est probabilistiquement complet : si un chemin existe, la probabilité que la carte de routes en contienne un tend vers 1 à mesure que le nombre d'échantillons augmente.

Sa principale faiblesse est celle des passages étroits. Des échantillons aléatoires uniformes tombent rarement dans les régions minces de l'espace libre, si bien que la carte de routes peut ne pas relier des zones qui sont en réalité connectées. Des stratégies d'échantillonnage biaisé, comme l'échantillonnage près des frontières des obstacles, ont été développées pour y remédier. PRM* est une variante qui choisit les rayons de connexion de sorte que la carte de routes devienne asymptotiquement optimale.

Pourquoi c'est important

PRM a montré que l'échantillonnage aléatoire pouvait rendre la planification de mouvement praticable pour des robots à nombreux degrés de liberté, pour lesquels les méthodes exactes sont intraitables. Son idée de carte de routes reste utile chaque fois qu'un robot travaille de façon répétée dans le même environnement, comme une cellule industrielle fixe.

Applications principales

• Planification de mouvement à requêtes multiples pour des bras robotiques dans des cellules de travail fixes
• Planification de chemin pour des robots mobiles dans des cartes statiques
• Planification pour des systèmes à nombreux degrés de liberté comme les humanoïdes et les robots à deux bras
• Enseignement et évaluation comparative de la planification par échantillonnage

En pratique

Les équipes utilisent généralement PRM via OMPL, souvent à travers MoveIt pour la planification de bras, où PRM et PRM* côtoient des planificateurs à base d'arbres comme RRT-Connect. Comme une carte de routes peut être stockée et réutilisée, PRM convient aux cellules de travail fixes dans lesquelles un bras se déplace entre de nombreuses poses autour des mêmes montages : la carte de routes est construite hors ligne et interrogée à l'exécution, les vérifications de collision n'étant répétées que là où des objets ont pu bouger. Les ingénieurs ajustent le nombre d'échantillons et le rayon de connexion, et surveillent les composantes non connectées de la carte de routes, qui signalent généralement un passage étroit nécessitant des échantillons plus nombreux ou mieux ciblés.

Idées reçues

• PRM trouve toujours un chemin s'il en existe un — il est probabilistiquement complet, la garantie ne vaut donc qu'à la limite d'une infinité d'échantillons
• PRM sert surtout aux cartes 2D — son usage principal concerne les espaces des configurations de grande dimension comme l'espace articulaire d'un bras
• Une carte de routes reste valide indéfiniment — si des obstacles bougent, les arêtes concernées doivent être revérifiées ou la carte de routes reconstruite

Qui devrait le savoir

• Ingénieurs en planification de mouvement
• Intégrateurs de cellules robotiques industrielles
• Chercheurs en manipulation
• Étudiants en robotique qui apprennent la planification par échantillonnage

Technologies associées

• OMPL
• MoveIt
• RRT
• PRM*
• Recherche A (A Search)
• Espace des configurations (Configuration Space)

Termes associés

• Motion Planning
• RRT*
• Configuration Space

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

• Modern Robotics, Chapter 10.5: Sampling Methods for Motion Planning (Part 1 of 2): Northwestern Robotics