Stanford met en ligne la leçon de Pavone sur la planification de mouvement : RRT, PRM et FMT*

Stanford Online a mis en ligne sur YouTube la septième leçon du cours AA274A Principles of Robotic Autonomy, « Motion Planning II: Sampling-Based Methods ». L'enregistrement date de l'automne 2019. La leçon est donnée par Marco Pavone, adjunct professor au département d'aéronautique et d'astronautique de Stanford et Senior Director de la recherche sur les véhicules autonomes chez NVIDIA.

Avant de rejoindre l'université, il a travaillé au Jet Propulsion Laboratory de la NASA. Il ne s'agit pas de la sortie d'un produit, mais d'un support pédagogique ; le sujet détermine pourtant directement la façon dont les robots et les véhicules autonomes calculent leurs trajectoires. Stanford précise lui-même que la structure du cours, les exercices et les supports ont changé depuis 2019, et que les liens de la description renvoient vers la version actuelle.

Pourquoi un planificateur a besoin de points aléatoires

La recherche classique sur graphe (Dijkstra, A*) exige de discrétiser l'espace des configurations. Pour un robot plan, c'est supportable. Pour un manipulateur à sept articulations et une grille de 100 valeurs par axe, on obtient 100 puissance 7, soit environ 10^14 cellules. Impossible de stocker et de parcourir une telle grille.

Les méthodes par échantillonnage contournent le problème autrement. Le planificateur tire des configurations aléatoires, écarte celles qui provoquent une collision, puis relie les autres par de courts segments admissibles. Il n'a pas besoin d'une carte explicite des obstacles dans l'espace des configurations. Il lui suffit d'une fonction qui indique si un point ou un segment donné est libre.

Quels algorithmes composent ce bloc

La description présente le sujet de la leçon sous un intitulé général, mais l'ensemble standard de la planification par échantillonnage se présente ainsi :

• PRM (Kavraki, Švestka, Latombe, Overmars, 1996) : construit une seule fois un graphe à partir de points aléatoires, puis répond à de nombreuses requêtes. Adapté à un environnement statique.
• RRT (LaValle, 1998) : fait croître un arbre depuis le point de départ vers des points aléatoires. Trouve rapidement un chemin dans les espaces de grande dimension et convient mieux que PRM pour une requête unique.
• RRT* (Karaman, Frazzoli, 2011) : ajoute une réorganisation de l'arbre et offre l'optimalité asymptotique. Le coût du chemin converge vers l'optimum quand le nombre d'échantillons augmente.
• FMT* (Janson, Schmerling, Clark, Pavone, 2015) : développé par le groupe de Pavone. Parcourt l'échantillon dans un ordre proche de la méthode de fast marching et atteint souvent un bon chemin avec moins de tests de collision.
• Rayon de connexion dans PRM* : évolue comme (log n / n)^(1/d), où d désigne la dimension de l'espace. Cette estimation sous-tend les preuves d'optimalité.

La notion théorique centrale est ici la complétude probabiliste. Si un chemin existe, la probabilité de le trouver tend vers 1 quand le nombre de points augmente. Aucune garantie ne porte sur le temps de calcul, et cette réserve est importante.

Pourquoi les leçons de 2019 n'ont pas vieilli

Les planificateurs par échantillonnage n'ont pas disparu. La bibliothèque OMPL, que MoveIt utilise par défaut pour la planification, contient des implémentations de PRM, RRT, RRT* et FMT. Les approches récentes s'appuient sur cette base : distributions apprises pour choisir les points, vérification parallèle des collisions sur GPU, comme dans cuRobo de NVIDIA, et hybrides avec l'optimisation de trajectoires. Le goulot d'étranglement reste le même pour tous : la vérification des collisions absorbe en général l'essentiel du temps de planification.

Le cours dispose d'un manuel gratuit, Principles of Robot Autonomy, sur porabook.com et d'un syllabus ouvert sur stanfordasl.github.io/PoRA-I. Pour apprendre en autonomie, il est rare de trouver au même endroit les leçons, le texte et les exercices.

Comment exploiter ce matériel en pratique

Commencez par le manuel, puis regardez la leçon. Implémentez un RRT dans le plan en une centaine de lignes de code environ et comptez combien d'appels à la vérification de collision il faut pour un chemin. Branchez ensuite OMPL et comparez RRT, RRT et FMT sur une même scène comportant un passage étroit. C'est là que la principale faiblesse de ces méthodes apparaît : la probabilité de tomber dans un couloir étroit est faible, et le temps de recherche augmente brutalement.

Deux limites sont à garder en tête. Les chemins issus de RRT sont brisés et doivent presque toujours être lissés. Pour les machines soumises à une dynamique, comme les voitures, la géométrie seule ne suffit pas : il faut des variantes kinodynamiques et une coordination avec le contrôleur. La leçon de 2019 donne les bases, mais il faudra compléter les détails avec la version récente du cours.