Maximizing Reach-Avoid Probabilities for Linear Stochastic Systems via Control Architectures

Resumen Técnico: Maximización de las Probabilidades de Alcance-Evitación para Sistemas Estocásticos Lineales mediante Arquitecturas de Control

Formulación del Problema
El artículo aborda el desafío de maximizar la probabilidad de alcance-evitación para sistemas estocásticos lineales sobre un horizonte de tiempo finito. El sistema se define por una dinámica que contiene tanto estados que evolucionan de forma determinista ($x_d$) como estados que evolucionan de forma probabilística ($x_s$), sujetos a un ruido i.i.d. aditivo. El objetivo de control es encontrar una política que maximice la probabilidad de que el sistema alcance un conjunto objetivo $T$ mientras permanece dentro de un conjunto seguro $S$ durante una duración $[0, T]$, todo ello cumpliendo con las restricciones deterministas $G$ (como límites de entrada y de estado) en todo momento.

Los métodos existentes enfrentan un compromiso: los enfoques basados en límites estadísticos (por ejemplo, tubos estocásticos, MPC de escenarios) ofrecen escalabilidad pero suelen producir un rendimiento conservador, mientras que los métodos de optimización directa (por ejemplo, Procesos de Decisión de Markov) proporcionan garantías estrictas pero son computacionalmente intratables para espacios de estados de alta dimensión o continuos.

Metodología
Los autores proponen una arquitectura de control por capas que combina la escalabilidad del Control Predictivo basado en Modelo (MPC) con la optimalidad de la Programación Dinámica (DP). La innovación central radica en tratar el sistema de lazo cerrado (planta + MPC) como un Proceso de Decisión de Markov (MDP) donde las "acciones" son señales de referencia enviadas al MPC, en lugar de entradas de control directas.

1. Arquitectura por Capas:

   • Capa Inferior (MPC): Un Controlador Predictivo basado en Modelo (MPC) rastrea las señales de referencia generadas por la capa superior. El MPC está diseñado para ser agnóstico al objetivo de alcance-evitación estocástico; su único propósito es asegurar que el sistema cumera con las restricciones deterministas $G$ y los límites de entrada $U$. Para cerrar la brecha entre la optimización de MPC en tiempo discreto y el cumplimiento de restricciones en tiempo continuo, los autores derivan técnicas de endurecimiento de restricciones (Lema III.1) que tienen en cuenta la dinámica del sistema y el ruido durante el intervalo de muestreo.
   • Capa Superior (Generador de Referencias DP): Una política basada en DP opera en intervalos de tiempo fijos ($\Delta t$). Selecciona secuencias de referencia (comandos) para el MPC con el fin de maximizar la probabilidad de alcanzar el objetivo mientras se evitan regiones inseguras. El espacio de estados de este MDP es el estado del sistema $x_k$, y el espacio de acciones consiste en un conjunto finito de trayectorias de referencia.

2. Manejo de Espacios de Estados Continuos y Abstracción:
   Dado que el espacio de estados es continuo, los autores emplean una abstracción de rejilla finita para hacer que la DP sea computacionalmente tratable. Para asegurar que las garantías teóricas se preserven a pesar de esta discretización, introducen un marco de robustificación:

   • MPC Robusto (RMPC): El MPC se modifica para generar secuencias de entrada que sean invariantes a la realización específica del estado inicial dentro de una celda de la rejilla (partición). Esto se logra inicializando la predicción del MPC desde el centro de la celda en lugar de desde el estado medido, asegurando que la misma secuencia de control se aplique a todos los estados dentro de una partición.
   • Iteración de Valor Robusta: Los conjuntos seguros y de objetivo se endurecen mediante un radio $r$ (derivado de la desviación máxima de las trayectorias dentro de un paso de tiempo) para contabilizar los errores de abstracción. El algoritmo DP se modifica para calcular un límite inferior en la probabilidad de alcance-evitación considerando las transiciones de peor caso dentro de la vecindad de cada celda de la rejilla.

Contribuciones Clave

• Arquitectura de Control: El artículo introduce una arquitectura novedosa que reduce la dimensionalidad del espacio de planificación de la DP de la dimensión completa del estado $n$ a la dimensión del componente que evoluciona probabilísticamente $n_s$. Esto se logra aprovechando la evolución determinista de $x_d$ y las capacidades de seguimiento del MPC.
• Garantías Teóricas: Los autores proporcionan certificados formales para el enfoque. Demuestran que la arquitectura robustecida asegura el cumplimiento de restricciones en tiempo continuo y que el valor computado por el algoritmo de DP robusto sirve como un límite inferior estricto de la probabilidad de alcance-evitación real lograda por el sistema (Teorema IV.4).
• Escalabilidad y Flexibilidad: Se demuestra que el método es escalable a sistemas de mayor dimensión (específicamente un modelo de cuadricóptero de 12D) y lo suficientemente flexible para manejar entornos complejos y congestionados.

Resultos
El enfoque fue validado en un modelo de cuadricóptero de 12D perturbado navegando en diversos entornos congestionados (por ejemplo, laberintos, caminos en zigzag y campos de obstáculos).

• Desempeño: En un escenario de laberinto, la arquitectura logró una tasa de éxito del 40%, superando significativamente a las líneas base conservadoras.
• Comparación: En múltiples escenarios, la probabilidad de alcance-evitación empírica ($V_0(x_0)$) cumplió o excedió consistentemente el límite inferior computado por la iteración de valor robusta ($\tilde{V}_0(x_0)$), validando las garantías teóricas. Por ejemplo, en un entorno de "zigzag", la tasa de éxito empírica fue del 44% frente a un límite inferior teórico de 0.3%.
• Compromisos: El artículo también demuestra la capacidad de la arquitectura para resolver problemas de control óptimo con restricciones. Al ajustar un multiplicador de Lagrange, el sistema puede intercambiar el costo de la trayectoria (mantener la trayectoria cerca de un centro) contra la probabilidad de alcance-evitación, generando un frente de Pareto de soluciones.

Significancia y Reivindicaciones
El artículo afirma que este trabajo cierra la brecha entre la optimalidad teórica de los métodos basados en MDP y la escalabilidad práctica del MPC. Al desacoplar la ejecución de la seguridad (gestionada por el MPC robusto) de la optimización probabilística (gestionada por el generador de referencias DP), los autores logran una estrategia de control que es tanto computacionalmente factible para sistemas de mayor dimensión como capaz de proporcionar certificados formales de alcance-evitación sin recurrir a límites estadísticos excesivamente conservadores. Los autores enfatizan que su método proporciona certificados formales para sistemas estocásticos, una característica que a menudo falta en los enfoques heurísticos escalables, mientras evita la intratabilidad computacional de las soluciones de MDP de estado completo.