Stanford met en ligne la leçon de Marco Pavone sur la planification de mouvement des robots sur graphes

Stanford Online a mis en ligne sur YouTube la leçon 6 du cours AA274A Principles of Robotic Autonomy, consacrée à la planification de mouvement par des méthodes de recherche sur graphes (Motion Planning I). Elle est donnée par Marco Pavone : professeur associé d'aéronautique et d'astronautique à Stanford, directeur senior de la recherche sur les véhicules autonomes chez NVIDIA et ancien chercheur du groupe de robotique du JPL de la NASA. L'enregistrement date de l'automne 2019. Les éditeurs préviennent explicitement que la structure du cours, les exercices et les supports ont pu changer depuis.

Il s'agit d'un contenu pédagogique, pas d'une annonce de sortie. Mais il couvre l'un des sujets de base de toute pile robotique, et son auteur apporte un contexte inhabituellement solide.

De quoi parle la leçon

La planification de mouvement sur graphe ramène le problème du robot à une recherche. L'espace des positions possibles est discrétisé : les nœuds représentent les états, les arêtes représentent les transitions autorisées, et chaque arête a un coût. Il faut ensuite trouver un chemin du départ à l'objectif dont le coût total est minimal.

La boîte à outils standard pour ce type de problème est bien connue. L'algorithme de Dijkstra trouve le chemin optimal, mais il étend les sommets dans toutes les directions. A ajoute une estimation heuristique de la distance à l'objectif et oriente davantage la recherche. Si l'heuristique est admissible, c'est-à-dire qu'elle ne surestime pas le coût réel, A conserve la garantie d'optimalité. Dijkstra devient alors un cas particulier d'A* avec une heuristique nulle. Pour connaître le contenu exact de la leçon, mieux vaut consulter la vidéo elle-même : sa description n'indique que le thème.

Pourquoi l'intervenant compte

Pavone travaille à la jonction de la robotique académique et du développement industriel de la conduite autonome. Cela se voit dans le cours lui-même : il suit un parcours qui va de la perception et de l'estimation d'état à la planification et au contrôle, au lieu d'empiler des algorithmes sans lien entre eux. La leçon consacrée à la recherche sur graphes sert ici de fondation. Les planificateurs plus complexes et les méthodes fondées sur l'apprentissage viennent s'y greffer ensuite.

Informations sur la publication :

• Cours : AA274A Principles of Robotic Autonomy, leçon 6
• Sujet : Motion Planning I, méthodes de recherche sur graphes
• Intervenant : Marco Pavone, Stanford et NVIDIA
• Date d'enregistrement : automne 2019
• Format : vidéo sur la chaîne Stanford Online
• Manuel : Principles of Robot Autonomy, gratuit sur porabook.com
• Calendrier actuel : stanfordasl.github.io/PoRA-I

Comment exploiter ce contenu

Il vaut mieux regarder la leçon avec le chapitre correspondant du manuel. La meilleure façon de vérifier sa compréhension : écrire A* en Python sur une grille 2D, en quelques dizaines de lignes. Comparez ensuite son comportement à celui de Dijkstra sur une même carte avec obstacles, en comptant combien de sommets chacun des deux algorithmes étend. L'écart du nombre de nœuds explorés montre vite ce que l'heuristique change en pratique.

Pour les ingénieurs qui travaillent sur des plateformes mobiles ou des drones, il est utile de confronter la leçon au planificateur de leur propre pile. On constate souvent que le coût des arêtes, le pas de discrétisation et le choix de l'heuristique pèsent plus sur le comportement du robot que l'algorithme de recherche lui-même.

Une réserve. L'enregistrement correspond à la version 2019 du cours. Si vous voulez le programme dans son état actuel, avec les nouveaux sujets et les nouveaux exercices, reportez-vous au syllabus à jour sur le site du laboratoire ASL. La leçon constitue un point d'entrée gratuit pour ceux qui veulent comprendre les bases de la planification avant de passer à des approches plus modernes.