Provably Safe Motion Planning Under Unknown Disturbances

Enunciado del Problema
Este artículo aborda el desafío de la planificación de movimientos para sistemas robóticos sujetos a perturbaciones aleatorias con distribuciones desconocidas. Los planificadores basados en muestreo tradicionales a menudo asumen modelos deterministas o dependen de fuertes supuestos distribucionales (por ejemplo, ruido gaussiano) y modelos de perturbación acotados. Estos enfoques frecuentemente resultan en planes excesivamente conservadores que fallan en entornos congestionados o requieren un conocimiento poco realista de la distribución de la perturbación. Los autores formulan el problema como la generación de un plan de movimiento para sistemas lineales (o linealizables por retroalimentación) que satisfaga restricciones de probabilidad para la evitación de colisiones y la alcanzabilidad del objetivo con alta confianza, a pesar de que las distribuciones del estado inicial y del ruido del proceso sean desconocidas. El sistema debe operar dentro de restricciones de estado y control en espacios de trabajo que contienen obstáculos de forma arbitraria.

Metodología
El enfoque propuesto, denominado WDR-X (Robustez Distribucional de Wasserstein-X), es un marco de planificación de movimientos basado en muestreo que integra la cuantificación de incertidumbre basada en datos con una búsqueda basada en árboles. La metodología procede en dos fases principales:

1. Construcción del Tubo de Ambigüedad (Offline):
   En lugar de asumir una distribución de ruido específica, el algoritmo aprende un tubo de ambigüedad de Wasserstein a partir de un conjunto de $N$ muestras de trayectorias i.i.d. Este tubo es una secuencia de conjuntos de ambigüedad (bolas de Wasserstein) que, con un nivel de confianza definido por el usuario, contiene la verdadera distribución del estado en cada paso de tiempo.

   • Dinámica del Error: Los autores desacoplan el problema de planificación de la propagación de la incertidumbre analizando la dinámica del error con respecto a una trayectoria de referencia. Demuestran que el conjunto de ambigüedad para el estado puede derivarse del conjunto de ambigüedad del error y del estado de referencia.
   • Horizonte Infinito: A diferencia de métodos anteriores donde los límites de ambigüedad crecen sin límite con el tiempo, este enfoque construye un tubo de longitud temporal infinita con confianza finita. Logra esto aprendiendo conjuntos de ambigüedad basados en datos en pasos de tiempo específicos y derivando los conjuntos para los pasos intermedios utilizando la dinámica del sistema, resultando en un perfil de radio "diente de sierra" que permanece acotado.
   • Descomposición de Menor Dimensión: Para abordar la maldición de la dimensionalidad, el marco aprovecha tubos de ambigüedad de menor dimensión. Al proyectar la distribución del estado sobre subespacios relevantes para restricciones específicas (por ejemplo, posición en el espacio de trabajo para obstáculos, esfuerzo de control para límites), el método reduce significativamente la complejidad de la muestra y el costo computacional mientras mantiene garantías de seguridad.

2. Planificación Probablemente Completa (Online):
   El planificador hace crecer un árbol basado en muestreo (por ejemplo, RRT) sobre las trayectorias de referencia nominales (deterministas).

   • Verificación de Validez: En cada nodo, el algoritmo verifica si el estado satisface las restricciones de probabilidad. Esto se realiza evaluando la probabilidad de colisión en el peor caso sobre el conjunto de ambigüedad aprendido.
   • Verificadores Eficientes: El artículo introduce tres estrategias de verificación de validez:
     • Verificador Exacto: Un algoritmo sin optimización basado en el transporte de masa de probabilidad que calcula la probabilidad exacta de colisión en el peor caso para distribuciones discretas.
     • Verificador Perezoso (Lazy): Un método más rápido y más conservador que utiliza tubos (bolas) de confianza precalculados, evitando cálculos detallados de transporte de masa.
     • Verificador Basado en Bandidos: Un enfoque híbrido que selecciona adaptativamente entre los verificadores exacto y perezoso utilizando un marco de bandidos multi-brazo. Esto equilibra la eficiencia y el conservadurismo, particularmente en entornos complejos como pasillos estrechos.

Contribuciones Clave
El artículo realiza las siguientes contribuciones específicas:

• Algoritmo: Un algoritmo de planificación de movimientos basado en muestreo para sistemas lineales con perturbaciones aditivas desconocidas que utiliza datos de observación de trayectorias.
• Garantías Teóricas: Demostraciones de solidez y completitud probabilística para el planificador bajo supuestos relajados respecto a las distribuciones de perturbación.
• Propagación de Ambigüedad: Nuevos resultados teóricos sobre la propagación de la ambigüedad distribucional, mostrando específicamente que la propagación de la ambigüedad se desacopla de la planificación para sistemas lineales, lo que permite un único tubo aprendido offline.
• Límites Más Estrictos: Una caracterización más estricta del tamaño de los conjuntos de ambigüedad basados en datos definidos por la distancia de Wasserstein-1 en comparación con la literatura existente, utilizando desigualdades de McDiarmid unilaterales e información de momentos.
• Verificación de Validez: Tres métodos de verificación de validez que intercambian eficiencia y conservadurismo, todos menos conservadores que el trabajo existente, unificados por un esquema de bandidos multi-brazo que selecciona adaptativamente el verificador apropiado.
• Reducción de Dimensionalidad: Una formalización del uso de múltiples tubos de ambigüedad de menor dimensión para reducir los requisitos de datos y computación sin sacrificar la seguridad.

Resultados Experimentales
Los autores evaluaron el enfoque en dos sistemas: un sistema lineal de 4 dimensiones y un sistema de dron de 8 dimensiones navegando en espacios de trabajo 2D.

• Líneas Base: El método se comparó con enfoques de robustez distribucional basados en momentos (TS y Risk-Assigned) y otras variantes basadas en Wasserstein (Partícula, Confianza, Híbrido).
• Rendimiento:
  • En entornos congestionados y de pasillos estrechos, el Bandit-WDR-RRT propuesto superó significativamente a las líneas base basadas en momentos, las cuales fallaron en encontrar caminos debido a un conservadurismo excesivo. Por ejemplo, en un pasillo estrecho con ruido no gaussiano, las líneas base lograron tasas de éxito del 0–9%, mientras que Bandit-WDR-RRT alcanzó hasta un 100%.
  • El verificador basado en bandidos demostró el mejor equilibrio, igualando o superando las tasas de éxito de otras variantes mientras era 1.5–3 veces más rápido que el enfoque Híbrido.
  • El enfoque de menor dimensión permitió exitosamente la planificación para el sistema de dron de 8 dimensiones aprendiendo tubos separados para restricciones de posición y control, demostrando escalabilidad.
• Seguridad: Las simulaciones de Monte Carlo confirmaron que los planes generados alcanzaron tasas de éxito del 99–100% en la evitación de colisiones, validando la solidez de las restricciones del tubo de ambigüedad.

Significado
El artículo afirma que su significado principal radica en proporcionar un marco de planificación de movimientos probablemente seguro y escalable para sistemas con distribuciones de perturbación desconocidas. Al aprovechar conjuntos de ambigüedad de Wasserstein y aprendizaje basado en datos, el enfoque evita las sobreaproximaciones geométricas inherentes a los métodos basados en momentos y los supuestos distribucionales de los métodos basados en gaussianas. La capacidad de manejar obstáculos de forma arbitraria y restricciones no convexas sin sacrificar la completitud probabilística hace que el método sea adecuado para aplicaciones robóticas complejas del mundo real donde la seguridad es crítica y los modelos de perturbación son inciertos. La introducción del verificador de validez basado en bandidos mejora aún más la utilidad práctica al gestionar dinámicamente el equilibrio entre la velocidad computacional y el conservadurismo de la solución.