From Global to Local: Hierarchical Probabilistic Verification for Reachability Learning

Resumen Técnico: Verificación Probabilística Jerárquica para Aprendizaje de Alcanzabilidad

1. El Problema

El diseño de controladores con garantías de seguridad probables es fundamental para sistemas autónomos en entornos críticos (como coordinación multiagente o navegación a alta velocidad). El enfoque clásico para caracterizar los conjuntos de estados desde los cuales un sistema puede alcanzar un objetivo de forma segura es la alcanzabilidad de Hamilton-Jacobi (HJ). Sin embargo, los métodos HJ clásicos sufren de la "maldición de la dimensionalidad", volviéndose computacionalmente intratables en sistemas de alta dimensión.

Para superar esto, se han propuesto aproximaciones basadas en aprendizaje (como el Aprendizaje por Refuerzo Profundo - RL). Aunque escalables, estos métodos introducen errores que pueden llevar a:

• Aproximaciones excesivamente optimistas: Clasificar regiones inseguras como seguras.
• Falta de garantías formales: No ofrecen certezas matemáticas sobre la seguridad en tiempo de ejecución.

El desafío principal es lograr un equilibrio entre la escalabilidad del aprendizaje, la eficiencia computacional y la rigurosidad de las garantías de seguridad, evitando tanto el conservadurismo excesivo (que limita el rendimiento) como la inseguridad.

2. Metodología

Los autores proponen un marco de verificación probabilística jerárquica que combina certificación global offline y refinamiento local online. El sistema integra una política de aprendizaje de alcanzabilidad con un controlador basado en modelos (MPPI) mediante una lógica de conmutación.

Componentes Clave:

• A. Verificación Global Coarse (Offline):

  • Se utiliza optimización de escenarios para construir un conjunto seguro global aproximado.
  • En lugar de usar constantes de Lipschitz deterministas (que son muy conservadoras), el método estima un límite de desviación de la trayectoria ($\Delta x^*_t$) mediante muestreo de pares de estados (nominal vs. perturbado).
  • Esto genera un certificado probabilístico inferior de la función de valor ($\check{V}_\gamma$), definiendo un conjunto global seguro ($V_{global}$) con una probabilidad de fallo acotada por $\epsilon$ y un nivel de confianza $1-\beta$.

• B. Refinamiento Local Iterativo (Online):

  • Dado que la verificación global puede ser conservadora y excluir estados seguros reales, se introduce un módulo de refinamiento local cerca del límite de $V_{global}$.
  • Se define un vecindario local alrededor del punto más cercano en la frontera del conjunto global.
  • Mediante un algoritmo iterativo (Algoritmo 1), se realizan simulaciones de trayectorias dentro de este vecindario. Si no se encuentran violaciones de seguridad en las muestras, el radio de la región segura se expande.
  • Esto recupera regiones seguras que fueron descartadas por la verificación global, manteniendo las garantías probabilísticas.

• C. Marco de Control Híbrido (Conmutación):
  El sistema opera en cuatro niveles (tiers) según la ubicación del estado actual:

  1. Tier 0 (Mantenimiento): Si el estado está dentro del objetivo, se usa un controlador MPPI rápido.
  2. Tier 1 (Verificación Global): Si el estado está en $V_{global}$, se ejecuta la política aprendida ($\pi_{lp}$).
  3. Tier 2 (Refinamiento Local): Si el estado está fuera de $V_{global}$ pero dentro del conjunto refinado localmente ($V_{local}$), se sigue usando $\pi_{lp}$.
  4. Tier 3 (Recuperación Segura): Si el estado está fuera de ambos conjuntos verificados, se activa un controlador MPPI (Model Predictive Path Integral) "calentado" (warm-started) con la política aprendida. Este controlador busca minimizar la distancia hacia la frontera del conjunto seguro verificado más cercano para recuperar la seguridad.

3. Contribuciones Clave

1. Marco Jerárquico Seguro: Un enfoque multinivel que une la verificación probabilística global con el refinamiento local adaptativo, integrando políticas aprendidas y controladores basados en modelos.
2. Expansión Local Basada en Escenarios: Un método eficiente para expandir el conjunto seguro mediante optimización de escenarios, recuperando estados seguros que la verificación global conservadora habría descartado.
3. Garantías de Seguridad Probabilísticas: Se proporcionan garantías teóricas (Teoremas 1 y 2) para ambos conjuntos (global y localmente refinado), asegurando que la probabilidad de violar restricciones de seguridad esté acotada por un riesgo $\epsilon$ con alta confianza.
4. Validación Empírica: Demostración en un escenario de carreras de drones de alta dimensión, mostrando tasas de éxito superiores en comparación con métodos de línea base.

4. Resultados

Los experimentos se realizaron en un entorno de carreras de drones (12 dimensiones, no cooperativo) donde un dron "ego" debe adelantar a un oponente y pasar por una puerta estrecha, evitando colisiones y corrientes de aire descendentes.

• Comparativa de Seguridad: El marco propuesto ("Hybrid") logró una tasa de éxito del 90.2%, superando significativamente a las líneas base:
  • MPPI con filtro CBF: 62.4%
  • MPPI con restricciones suaves: 63.2%
  • PPO con filtro CBF: 14.2%
• Estudio de Ablación: Se demostró que ni la política de alcanzabilidad sola (51.8%) ni el MPPI puro sin seguridad (63.4%) son suficientes. La combinación de la política de aprendizaje (para eficiencia y dirección) con el mecanismo de conmutación hacia MPPI (para recuperación de seguridad) es crucial.
• Comportamiento Observado: Los métodos base tendían a priorizar el objetivo a expensas de la seguridad (colisiones), mientras que el método propuesto logró un equilibrio robusto, utilizando el modo de recuperación (Tier 3) para reingresar a zonas seguras cuando era necesario.

5. Significado e Impacto

Este trabajo es significativo porque aborda la brecha crítica entre la escalabilidad de los métodos de aprendizaje y la necesidad de garantías formales de seguridad en sistemas autónomos de alta dimensión.

• Reducción del Conservadurismo: Al combinar una verificación global rápida con un refinamiento local preciso, el método evita descartar regiones de operación viable que otros métodos formales considerarían inseguras.
• Eficiencia Computacional: Al realizar la verificación global offline y el refinamiento solo online en regiones críticas (cerca de la frontera), el enfoque es computacionalmente viable para sistemas en tiempo real.
• Robustez Operativa: La arquitectura de conmutación híbrida asegura que, incluso cuando el modelo de aprendizaje falla o se encuentra en una región no verificada, el sistema no colapsa, sino que transiciona a un modo de recuperación seguro basado en modelos.

En resumen, el marco presentado ofrece una solución práctica y teóricamente fundamentada para desplegar controladores aprendidos en entornos de seguridad crítica, demostrando que es posible lograr un alto rendimiento sin sacrificar la garantía de seguridad.