Stanford publica la lección de Pavone sobre planificación de movimiento: RRT, PRM y FMT*

Stanford Online ha publicado en YouTube la séptima lección del curso AA274A Principles of Robotic Autonomy, «Motion Planning II: Sampling-Based Methods». La grabación es del otoño de 2019. La imparte Marco Pavone, profesor adjunto del Departamento de Aeronáutica y Astronáutica de Stanford y Senior Director de investigación en vehículos autónomos en NVIDIA.

Antes de incorporarse a la universidad trabajó en el Jet Propulsion Laboratory de la NASA. No se trata del lanzamiento de un producto, sino de material docente, pero el tema determina directamente cómo los robots y los vehículos autónomos calculan sus trayectorias. Stanford precisa que la estructura del curso, las tareas y los materiales han cambiado desde 2019, y que los enlaces de la descripción llevan a la versión actual.

Por qué el planificador necesita puntos aleatorios

La búsqueda clásica en grafos (Dijkstra, A*) exige discretizar el espacio de configuraciones. Para un robot plano es asumible. Para un manipulador de siete articulaciones y una cuadrícula de 100 valores por eje, el resultado es 100 elevado a la séptima potencia, es decir, unas 10^14 celdas. Almacenar y recorrer una cuadrícula así es imposible.

Los métodos basados en muestreo resuelven el problema de otra manera. El planificador genera configuraciones aleatorias, descarta las que provocan colisión y conecta las restantes con segmentos cortos admisibles. No hace falta un mapa explícito de obstáculos en el espacio de configuraciones. Basta con una función que indique si un punto o un segmento concretos están libres.

Qué algoritmos incluye este bloque

En la descripción, el tema de la lección aparece con un título genérico, pero el conjunto estándar de la planificación basada en muestreo es el siguiente:

• PRM (Kavraki, Švestka, Latombe, Overmars, 1996): construye una sola vez un grafo a partir de puntos aleatorios y responde a numerosas consultas. Es adecuado para entornos estáticos.
• RRT (LaValle, 1998): hace crecer un árbol desde el punto de partida hacia puntos aleatorios. Encuentra rápidamente un camino en espacios de muchas dimensiones y, para una única consulta, resulta más práctico que PRM.
• RRT* (Karaman, Frazzoli, 2011): añade la reconfiguración del árbol y logra optimalidad asintótica. El coste del camino converge al óptimo a medida que crece el número de muestras.
• FMT* (Janson, Schmerling, Clark, Pavone, 2015): desarrollo del grupo de Pavone. Recorre las muestras en un orden próximo al del método fast marching y a menudo alcanza un buen camino con menos comprobaciones de colisión.
• Radio de conexión en PRM*: escala como (log n / n)^(1/d), donde d es la dimensión del espacio. Esta estimación sustenta las demostraciones de optimalidad.

El concepto teórico central aquí es la completitud probabilística. Si existe un camino, la probabilidad de encontrarlo tiende a uno a medida que aumenta el número de puntos. No hay garantías sobre el tiempo, y es una salvedad importante.

Por qué las lecciones de 2019 no han quedado obsoletas

Los planificadores basados en muestreo siguen vigentes. La biblioteca OMPL, que MoveIt utiliza por defecto para planificar, incluye implementaciones de PRM, RRT, RRT* y FMT. Las líneas actuales de trabajo se construyen sobre esa base: distribuciones aprendidas para elegir los puntos, comprobación paralela de colisiones en GPU, como en cuRobo de NVIDIA, e híbridos con optimización de trayectorias. El cuello de botella es el mismo para todos: la comprobación de colisiones suele consumir la mayor parte del tiempo de planificación.

El curso dispone de un libro de texto gratuito, Principles of Robot Autonomy, en porabook.com y de un sílabo abierto en stanfordasl.github.io/PoRA-I. Para quien estudia por su cuenta, es un caso poco habitual en el que las lecciones, el texto y las tareas están en un mismo lugar.

Cómo usar el material en la práctica

Empiece por el libro de texto y después vea la lección. Implemente RRT en el plano en unas cien líneas de código y cuente cuántas llamadas a la comprobación de colisiones se necesitan para obtener un camino. Después conecte OMPL y compare RRT, RRT y FMT en una misma escena con un paso estrecho. Ahí se ve la principal debilidad de estos métodos: la probabilidad de caer en un corredor estrecho es baja y el tiempo de búsqueda se dispara.

Hay además dos limitaciones que conviene tener en cuenta. Los caminos de RRT salen quebrados y casi siempre hay que suavizarlos. Y para máquinas con dinámica, como los automóviles, la geometría por sí sola no basta: hacen falta variantes cinodinámicas y coordinación con el controlador. La lección de 2019 ofrece la base, pero los detalles habrá que completarlos con la versión actualizada del curso.