Probabilistic Roadmap

• También llamado: PRM, probabilistic roadmap method
• Categoría: Planning & manipulation › Motion planning
• Etiquetas: motion-planning, sampling-based-planning, path-planning, graph-search, manipulation

Un planificador de movimiento basado en muestreo que construye un grafo reutilizable de configuraciones aleatorias libres de colisiones y de los caminos factibles entre ellas, y después responde a las consultas de planificación mediante búsqueda en grafos.

Definición

Mapa de rutas probabilístico (Probabilistic Roadmap, PRM) es un método de planificación de movimiento basado en muestreo presentado por Kavraki, Švestka, Latombe y Overmars en 1996. En lugar de buscar de nuevo en el espacio de configuraciones para cada petición, PRM construye primero un grafo, el mapa de rutas, que recoge la conectividad del espacio libre del robot, y después usa ese grafo para responder a cualquier número de consultas de inicio a objetivo.

La planificación tiene dos fases. En la fase de construcción, el planificador muestrea configuraciones aleatorias del robot, conserva como nodos las que están libres de colisiones e intenta conectar cada nodo con los nodos cercanos mediante un planificador local sencillo, normalmente una línea recta en el espacio de configuraciones comprobada en busca de colisiones a intervalos finos. Las conexiones con éxito se convierten en aristas. En la fase de consulta, las configuraciones de inicio y objetivo se conectan al mapa de rutas, y una búsqueda en grafos como el algoritmo de Dijkstra o A* encuentra un camino a través de él.

PRM es adecuado para problemas de consultas múltiples, en los que el entorno es estático y el robot debe planificar muchos movimientos en el mismo espacio, porque la costosa construcción del mapa de rutas se hace una sola vez. Es probabilísticamente completo: si existe un camino, la probabilidad de que el mapa de rutas contenga uno tiende a 1 a medida que crece el número de muestras.

Su principal debilidad son los pasos estrechos. Las muestras aleatorias uniformes rara vez caen en regiones delgadas del espacio libre, por lo que el mapa de rutas puede no conectar zonas que en realidad están unidas. Para resolverlo se desarrollaron estrategias de muestreo sesgado, como muestrear cerca de los bordes de los obstáculos. PRM* es una variante que elige los radios de conexión de modo que el mapa de rutas se vuelve asintóticamente óptimo.

Por qué importa

PRM demostró que el muestreo aleatorio podía hacer práctica la planificación de movimiento para robots con muchos grados de libertad, en los que los métodos exactos son intratables. Su idea del mapa de rutas sigue siendo útil siempre que un robot trabaja repetidamente en el mismo entorno, como una célula industrial fija.

Aplicaciones clave

• Planificación de movimiento con consultas múltiples para brazos robóticos en células de trabajo fijas
• Planificación de caminos para robots móviles en mapas estáticos
• Planificación para sistemas con muchos grados de libertad, como humanoides y robots de dos brazos
• Enseñanza y evaluación comparativa de la planificación basada en muestreo

En la práctica

Los equipos suelen usar PRM a través de OMPL, a menudo mediante MoveIt para la planificación de brazos, donde PRM y PRM* conviven con planificadores basados en árboles como RRT-Connect. Como un mapa de rutas puede almacenarse y reutilizarse, PRM encaja en células de trabajo fijas en las que un brazo se mueve entre muchas poses alrededor de los mismos utillajes: el mapa de rutas se construye fuera de línea y se consulta en tiempo de ejecución, repitiendo las comprobaciones de colisión solo donde los objetos pueden haberse movido. Los ingenieros ajustan el número de muestras y el radio de conexión, y vigilan si aparecen componentes desconectados en el mapa de rutas, que suelen indicar un paso estrecho que necesita más muestras o muestras mejor dirigidas.

Ideas erróneas comunes

• PRM siempre encuentra un camino si existe — es probabilísticamente completo, así que la garantía solo se cumple en el límite de infinitas muestras
• PRM es sobre todo para mapas 2D — su uso principal está en espacios de configuraciones de alta dimensión, como el espacio articular de un brazo
• Un mapa de rutas sigue siendo válido para siempre — si los obstáculos se mueven, las aristas afectadas deben volver a comprobarse o el mapa de rutas debe reconstruirse

Quién debería saberlo

• Ingenieros de planificación de movimiento
• Integradores de células de robots industriales
• Investigadores en manipulación
• Estudiantes de robótica que aprenden planificación basada en muestreo

Tecnologías relacionadas

• OMPL
• MoveIt
• RRT
• PRM*
• Búsqueda A (A Search)
• Espacio de configuraciones (Configuration Space)

Términos relacionados

• Motion Planning
• RRT*
• Configuration Space

Proyectos relacionados

• 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

Vídeos

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