Introducción a la ingeniería de control: Planificación de trayectorias — A*, Dijkstra, RRT, RRT* y PRM

Mover un robot desde el punto de partida hasta el objetivo rara vez implica trazar una línea recta. Un plan útil debe tener en cuenta paredes, ancho de paso, huella del robot, límites de giro, incertidumbre de localización, mapas obsoletos, movimiento de personas y distancia de frenado. La planificación de la trayectoria elige hacia dónde ir; la generación y el control de la trayectoria deciden cómo seguir esa ruta en condiciones dinámicas. Una pila segura mantiene estas responsabilidades diferenciadas, compartiendo sus límites.

Esta introducción compara Dijkstra en cuadrícula y A con RRT, RRT y PRM en espacio continuo. Explica la inflación de obstáculos, heurísticas, muestreo, complejidad, integración SLAM/Nav2, comprobaciones de implementación y comportamiento de seguridad independiente. Consulte Introducción a SLAM visual, Introducción a ROS 2 y Introducción a la fusión de sensores para capas relacionadas.

Conclusión práctica

• Dijkstra garantiza la ruta más corta en un grafo ponderado no negativo, pero se expande en direcciones no relacionadas con el objetivo. A* dirige la expansión con una heurística admisible, manteniendo la misma optimalidad.

• RRT tiende a encontrar una ruta factible rápidamente en espacios continuos de alta dimensión. RRT* se aproxima a una ruta óptima a medida que aumenta el número de muestras, con un coste adicional de vecinos y reconfiguración. PRM amortiza la construcción del mapa de ruta en múltiples consultas en un espacio suficientemente estático.

• La ruta más corta a través de un mapa no inflado es una ruta de colisión para un robot con radio, error de localización y distancia de frenado.

• Una ruta devuelta no es prueba de seguridad. La actualización del mapa, la detección local, el error de seguimiento, los obstáculos dinámicos, la latencia de replanificación y la parada de emergencia requieren un tratamiento independiente.

Definir el espacio libre antes de seleccionar un algoritmo

Sea el espacio de estados \mathcal X, el espacio de obstáculos \mathcal X_{obs} y el espacio libre \mathcal X_{free}=\mathcal X\setminus\mathcal X_{obs}. Una trayectoria \sigma:[0,1]\to\mathcal X_{free} conecta x_s con x_g, mediante \sigma(0)=x_s,\sigma(1)=x_g. Un robot puntual en 2D utiliza x=(x,y); un vehículo añade la dirección \theta, la velocidad y la dirección; un manipulador incluye todos los ángulos de las articulaciones. Simplificar el estado reduce el coste de búsqueda, pero puede generar curvas que el vehículo posterior no puede realizar.

La inflación de obstáculos convierte un robot finito en una búsqueda puntual al expandir los obstáculos. Aquí, r_{loc} debería ser un término de incertidumbre especificado, como un radio elegido para un nivel de confianza definido, en lugar de un error promedio no especificado. Un mínimo conceptual es:

donde r_{robot} es el radio del cuerpo, la incertidumbre de localización está representada por el término anterior y r_{safe} es el margen de seguimiento/parada. En realidad, el margen varía según la resolución del mapa, los puntos ciegos de los sensores, la velocidad del objeto que se aproxima y la capacidad de frenado. Un margen demasiado pequeño provoca colisiones; un margen demasiado grande hace imposibles los pasos viables.

Diagrama: Duskcoil, conceptual en lugar de medido. El tamaño de la celda y la inflación deben derivarse de la huella del robot real, la incertidumbre y el rango operativo.

Búsqueda en cuadrícula: Dijkstra y A*

Para el grafo G=(V,E) con un costo de arista no negativo c(u,v)\ge0, Dijkstra resuelve repetidamente el nodo no resuelto con el menor costo inicial conocido g(n) y se relaja. vecinos. Una vez establecido, su valor g es el más corto. Con un montículo binario, una complejidad representativa es O((|V|+|E|)\log|V|). Garantiza la distancia más corta en el grafo, pero, sin conocimiento del objetivo, tiende a expandirse ampliamente.

A* ordena los nodos por:

donde h(n) es una cota inferior del coste restante. Una heurística admisible nunca sobreestima el coste restante real; por lo tanto, A* sigue siendo óptimo. La distancia de Manhattan es adecuada para cuadrículas de 4 conexiones, mientras que la distancia euclidiana o relacionada con Chebyshev puede ser adecuada para el movimiento de 8 conexiones. Una heurística consistente satisface además h(n)\le c(n,n')+h(n') y reduce la reexpansión.

A* ponderado escala la heurística por w>1 para buscar una ruta factible más rápidamente a costa de la optimalidad. Esto puede ser una buena compensación operativa si se hace explícitamente. El coste de la arista puede codificar no solo la longitud, sino también Riesgo de obstáculos inflado, espacio libre, giro, energía o terreno. El resultado es el costo mínimo definido, no necesariamente la longitud geométrica mínima.

Espacios continuos y de alta dimensión: RRT, RRT*, PRM

Las cuadrículas finas se expanden en un espacio de configuración de brazo de seis articulaciones o en un espacio de pose de vehículo. RRT muestrea x_{rand} del espacio libre, encuentra el nodo de árbol más cercano x_{near}, se dirige una distancia limitada hacia él, comprueba si hay colisiones y añade x_{new}. Es probabilísticamente completo: con suficientes muestras, la probabilidad de encontrar una ruta factible se aproxima a uno cuando existe. No garantiza una primera ruta corta.

RRT* elige el padre de menor costo entre los vértices cercanos y reconecta los vecinos a través de un nuevo vértice cuando es más económico. Es asintóticamente óptimo, no óptimo en tiempo finito; la búsqueda de vecinos, las pruebas de colisión y la reconexión consumen computación. Mida la calidad en el plazo operativo en lugar de prometer "óptimo".

PRM muestrea configuraciones libres y conecta pares cercanos sin colisiones en un mapa de ruta reutilizable. Es atractivo en un entorno de fábrica estática o de consulta de brazos repetida porque el preprocesamiento se puede amortizar. Los obstáculos dinámicos invalidan los bordes. Los pasajes estrechos dificultan el muestreo uniforme, por lo que pueden ser necesarias muestras de límites de obstáculos, sesgadas por la ruta o informadas por la tarea.

Diagrama: Duskcoil, simplificado. El muestreo, la comprobación de colisiones y la conectividad no son una medida de rendimiento ni una ruta de producción final.

SLAM, Nav2 y planificación local

SLAM proporciona un mapa y una estimación de la posición, pero un planificador necesita transformaciones alineadas con la marca de tiempo y un significado claro de ocupación/costo. El cierre de un bucle o la relocalización pueden modificar la posición en el marco del mapa; continuar siguiendo una ruta antigua puede ser inseguro. Incorpore la incertidumbre, el reinicio de la localización y los eventos de actualización del mapa a las reglas de replanificación; consulte Visual SLAM Primer.

En una arquitectura ROS 2 similar a Nav2, un mapa de costos global y un planificador eligen una ruta a gran escala, mientras que un mapa de costos local y un controlador gestionan los obstáculos cercanos y la velocidad. Un algoritmo A* global puede seleccionar un corredor; la capa local debe ceder el paso, detenerse o desviarse para evitar a una persona. Una capa puramente local puede quedar atrapada en un callejón sin salida. Defina explícitamente el planificador, el controlador, la recuperación, las tasas de actualización del mapa, los plazos y las prioridades. El transporte ROS 2 descrito en ROS 2 Primer no garantiza la seguridad ni el funcionamiento en tiempo real.

Antes del despliegue, mida la huella, incluyendo la carga útil, el campo de visión del sensor, la velocidad/desaceleración máxima, el error de localización y la resolución del mapa. Pruebe el espacio libre real en pasajes estrechos. Verifique la colisión de las trayectorias planificadas con respecto al movimiento y la cinemática continuos: una ruta de cuadrícula puede girar entre celdas de maneras que un diferencial, un automóvil o un brazo no pueden.

Para obstáculos dinámicos, mida la frescura de la detección, la velocidad relativa, la distancia de frenado y el tiempo de replanificación; nunca continúe el movimiento porque el planificador se retrase. Considere a personas desconocidas, agujeros, obstáculos transparentes y fallas del sensor como casos de seguridad, no como celdas libres automáticamente. Reduzca la velocidad, deténgase o transfiera el control cuando no haya ruta, la trayectoria local sea insegura, la covarianza sea demasiado grande, el mapa esté desactualizado o el error de seguimiento exceda su rango. La parada de emergencia debe funcionar independientemente de la salida del planificador.

Lista de verificación de implementación y seguridad

1. Definir el espacio de estados, la huella, los marcos, la resolución del mapa y el significado de las celdas desconocidas.

2. Incluir en la inflación el error de localización, la velocidad y la distancia de frenado; probar pasajes estrechos reales.

3. Verificar la admisibilidad heurística o documentar la garantía deliberadamente relajada.

4. Registrar la resolución de la comprobación de colisiones, la semilla aleatoria, el plazo límite y el comportamiento de falta de solución para los planificadores de muestreo.

5. Inyectar relocalización, cambios de mapa, pérdida de sensores, obstáculos dinámicos y retardo de comunicación.

6. Verificar una parada segura y una ruta de registro diagnosticable para eventos de ruta nula, mapa obsoleto y desviación de seguimiento.

Referencias

• Hart, Nilsson, Raphael, 1968: Una base formal para A*
• LaValle: Árboles aleatorios de exploración rápida
• Karaman y Frazzoli, 2011: RRT*
• Documentación de Nav2