Stanford publica la lección de Marco Pavone sobre planificación de movimiento de robots con grafos

Stanford Online ha publicado en YouTube la lección 6 del curso AA274A Principles of Robotic Autonomy, dedicada a la planificación de movimiento con métodos de búsqueda en grafos (Motion Planning I). La imparte Marco Pavone: profesor asociado de Aeronáutica y Astronáutica en Stanford, director sénior de investigación en vehículos autónomos de NVIDIA y, en el pasado, investigador del grupo de robótica del JPL de la NASA. La grabación es del otoño de 2019. Los editores advierten expresamente de que la estructura del curso, las tareas y los materiales pueden haber cambiado desde entonces.

Se trata de material docente, no de la noticia de un lanzamiento. Pero cubre uno de los temas básicos de cualquier stack de robótica y cuenta con un contexto de autoría inusualmente sólido.

De qué trata la lección

La planificación de movimiento en grafos reduce el problema del robot a una búsqueda. El espacio de posiciones posibles se discretiza: los nodos representan estados, las aristas representan transiciones admisibles y cada arista tiene un coste. Después hay que encontrar un camino desde el punto de partida hasta la meta con el coste total mínimo.

El conjunto estándar de herramientas para este planteamiento es bien conocido. El algoritmo de Dijkstra encuentra el camino óptimo, pero expande los vértices en todas direcciones. A añade una estimación heurística de la distancia a la meta y busca de forma más dirigida. Si la heurística es admisible, es decir, si no sobrestima el coste real, A conserva la garantía de optimalidad. Dijkstra, por su parte, resulta ser un caso particular de A* con heurística nula. Conviene comprobar en el propio vídeo qué contenido concreto se aborda en la grabación: la descripción solo enumera el tema de la lección.

Por qué importa el autor

Pavone trabaja en la intersección entre la robótica académica y el desarrollo industrial de conducción autónoma. Se nota en el propio curso: está planteado como un recorrido que va de la percepción y la estimación del estado a la planificación y el control, y no como un conjunto de algoritmos sueltos. Aquí, una lección específica sobre búsqueda en grafos sirve de cimiento. Sobre él se apoyan más adelante planificadores más complejos y métodos basados en aprendizaje.

Datos de la publicación:

• Curso: AA274A Principles of Robotic Autonomy, lección 6
• Tema: Motion Planning I, métodos de búsqueda en grafos
• Ponente: Marco Pavone, Stanford y NVIDIA
• Fecha de la grabación: otoño de 2019
• Formato: vídeo en el canal de Stanford Online
• Libro de texto: Principles of Robot Autonomy, gratis en porabook.com
• Calendario actual: stanfordasl.github.io/PoRA-I

Cómo aprovechar el material

Lo mejor es ver la lección junto con el capítulo correspondiente del libro. La mejor forma de comprobar que se ha entendido es escribir en Python un A* sobre una cuadrícula 2D en unas pocas decenas de líneas. Después conviene compararlo con Dijkstra sobre el mismo mapa con obstáculos y contar cuántos vértices expande cada uno. La diferencia en el número de nodos expandidos muestra rápidamente qué es una heurística en la práctica.

A los ingenieros que trabajan con plataformas móviles o drones les resultará útil contrastar la lección con el planificador de su propio stack. A menudo se descubre que el coste de las aristas, el paso de discretización y la elección de la heurística influyen más en el comportamiento del robot que el propio algoritmo de búsqueda.

Una salvedad. La grabación corresponde a la versión del curso de 2019. Si necesita el programa tal como es hoy, con los temas y tareas nuevos, consulte el sílabo actual en la web del laboratorio ASL. La lección sirve como punto de entrada gratuito para quienes quieran entender los fundamentos de la planificación antes de pasar a enfoques más modernos.