Data-Driven Reachability of Nonlinear Lipschitz Systems via Koopman Operator Embeddings

Este artículo propone un marco de alcanzabilidad basado en datos y el operador de Koopman para sistemas no lineales Lipschitz que, al elevar el sistema a un espacio lineal y proyectar los conjuntos alcanzables de vuelta al espacio original, logra over-approximaciones garantizadas y significativamente menos conservadoras que los métodos existentes, como lo demuestran simulaciones y experimentos con vehículos autónomos.

Lo esencial

¡Claro que sí! Imagina que eres el capitán de un barco (un robot o un coche autónomo) que debe navegar por un océano lleno de niebla y corrientes impredecibles. Tu trabajo es predecir dónde estará tu barco en el futuro para asegurarte de no chocar contra rocas.

Aquí tienes la explicación de este paper como si fuera una historia de navegación:

El Problema: El Mapa Borroso

En el mundo de los robots, queremos saber todos los lugares posibles a los que puede llegar un sistema (su "zona de alcance") para garantizar que sea seguro.

• El problema: Los sistemas reales (como coches o robots) son no lineales. Esto significa que no se mueven en línea recta ni de forma predecible; giran, aceleran y frenan de formas complicadas.
• La vieja solución: Los métodos antiguos intentaban dibujar un "mapa de seguridad" muy grande y conservador. Imagina que, para no chocar, decides que el barco puede estar en todo el océano, solo por si acaso. Es seguro, pero inútil: si tu mapa de seguridad es tan grande que cubre todo el océano, no te sirve para navegar con precisión. Además, si el sistema es muy complejo, estos mapas se vuelven gigantes y lentos de calcular.

La Solución Propuesta: El "Traductor Mágico" (Operador Koopman)

Los autores proponen una nueva forma de ver el problema usando algo llamado Operador de Koopman.

Imagina que el movimiento del robot es como una canción compleja y caótica.

1. El Truco (Elevación): En lugar de intentar entender la canción tal como suena (que es difícil), usamos un "traductor mágico" (el operador Koopman) que transforma esa canción caótica en una melodía simple y lineal en un mundo paralelo (un espacio de mayor dimensión).
2. En el Mundo Paralelo: En este nuevo mundo, las reglas son simples y rectas (como una línea recta). Es mucho más fácil predecir dónde estará la melodía en el futuro.
3. El Retorno: Una vez que predecimos el futuro en este mundo simple, usamos el traductor inverso para volver a nuestro mundo real y ver dónde estará el robot.

La Innovación: No solo "Escucha", sino "Escucha y Actúa"

La mayoría de los métodos anteriores usaban un traductor que solo miraba el estado del robot (dónde está). Pero este paper dice: "¡Espera! El robot también recibe órdenes (inputs)".

• La analogía: Imagina que intentas predecir el movimiento de un coche. Si solo miras dónde está el coche, no sabes si el conductor va a pisar el acelerador o el freno.
• La mejora: Este método crea un traductor que mira al coche Y al conductor al mismo tiempo. Al incluir las órdenes (inputs) en la transformación, la "melodía simple" en el mundo paralelo es mucho más precisa.

El Escudo de Seguridad (Zonotopos y Residuos)

Aunque el traductor es bueno, no es perfecto. A veces comete pequeños errores, y además, el océano tiene olas (ruido).

• Zonotopos: Imagina que en lugar de dibujar un punto exacto, dibujas una caja flexible y geométrica alrededor de la posición probable del robot. Esta caja se estira y se mueve, pero siempre contiene la verdad. Es como un escudo de seguridad que se adapta.
• El "Colchón" de Error: Como el traductor puede fallar un poco, los autores calculan un "colchón" extra (un conjunto de residuos) basado en datos reales. Si el robot se desvía un poco de la predicción, el escudo se hace un poco más grande para cubrir ese error. Así, garantizan que nunca se saldrán de la caja de seguridad, sin importar el ruido o los errores del modelo.

¿Por qué es mejor? (La Prueba)

Los autores probaron esto con:

1. Reactores químicos (sistemas complejos de laboratorio).
2. Un coche autónomo real (un robot de carreras llamado JetRacer).

El resultado:

• Los métodos antiguos (modelos lineales simples) dibujaban cajas de seguridad enormes y exageradas (muy conservadoras).
• El nuevo método dibujó cajas muy ajustadas y precisas.
• Analogía final: Si los métodos antiguos te decían: "El coche podría estar en toda la ciudad, así que cierra todo", este nuevo método dice: "El coche estará en esta calle específica, dentro de esta acera, con un margen de error de un metro".

En Resumen

Este paper presenta una forma inteligente de predecir el futuro de robots complejos:

1. Traduce el caos no lineal a un mundo lineal simple usando datos reales.
2. Incluye las órdenes del conductor en la traducción para mayor precisión.
3. Dibuja un escudo de seguridad (zonotopo) que es lo suficientemente grande para ser 100% seguro, pero lo suficientemente pequeño para ser útil y preciso.

Es como tener un GPS que no solo te dice "no te vayas a la luna", sino que te dice exactamente por qué calle debes conducir para llegar a tiempo sin chocar, incluso si el tráfico es impredecible.

Resumen técnico

Resumen Técnico: Análisis de Alcanzabilidad Basado en Datos para Sistemas No Lineales Lipschitz mediante Incrustaciones del Operador de Koopman

1. Planteamiento del Problema

La verificación de seguridad en sistemas robóticos dinámicos y bajo incertidumbre es un requisito fundamental. Los métodos tradicionales de verificación formal basados en modelos requieren dinámicas del sistema precisas y caracterizaciones conservadoras de la incertidumbre, lo cual es difícil de obtener para plataformas complejas en entornos reales.

• Limitaciones de los métodos actuales:

  • Los enfoques basados en datos que utilizan análisis de alcanzabilidad con zonotopos (representaciones de conjuntos computacionalmente eficientes) tienden a volverse excesivamente conservadores para sistemas no lineales, especialmente en horizontes de predicción largos o bajo ruido de medición.
  • Los métodos de aprendizaje profundo (como los basados en redes LSTM) a menudo carecen de garantías formales deterministas, dependen de "cajas negras" y tienen baja eficiencia en el muestreo.
  • Las aproximaciones lineales estándar (LTI) no capturan adecuadamente la dinámica no lineal, lo que genera errores de modelado grandes.

• Objetivo: Desarrollar un marco de alcanzabilidad basado en datos para sistemas no lineales (no afines) que utilice datos de entrada-estado ruidosos para generar sobre-approximaciones garantizadas (que contengan todas las trayectorias reales) pero que sean menos conservadoras que los métodos existentes.

2. Metodología Propuesta

El enfoque central del artículo es utilizar la Teoría del Operador de Koopman para elevar el sistema no lineal a un espacio de dimensión finita donde la dinámica evoluciona de manera aproximadamente lineal.

A. Representación del Operador de Koopman

• Se define una función de elevación (lifting) $\psi(x, u)$ que mapea el estado y la entrada originales a un espacio de observables de mayor dimensión.
• A diferencia de los modelos LTI (Lineales e Invariantes en el Tiempo) tradicionales, este método utiliza funciones de elevación dependientes del estado y la entrada ($\psi(x, u)$), lo que permite una representación lineal más precisa de la dinámica subyacente no lineal.
• El operador de Koopman se identifica directamente desde los datos mediante regresión por mínimos cuadrados (LS) sobre las trayectorias medidas.

B. Análisis de Alcanzabilidad en el Espacio Elevado

1. Propagación de Zonotopos: Una vez identificado el modelo lineal en el espacio elevado, se propagan los conjuntos alcanzables utilizando la suma de Minkowski y transformaciones lineales de zonotopos, lo cual es computacionalmente eficiente.
2. Modelado de Errores y Residuos: Para garantizar la seguridad formal, el método no ignora los errores de aproximación. Se construyen conjuntos de incertidumbre que engloban:
   • Error de linealización: El residuo de la expansión de Taylor del modelo elevado no lineal.
   • Error de modelado de Koopman: La diferencia entre las predicciones del modelo lineal y las trayectorias reales en los datos de entrenamiento.
   • Ruido de proceso: El ruido de medición y perturbaciones del sistema.
   • Error de cobertura del conjunto de datos: Se utiliza un argumento de radio de cobertura ($\delta$) y la constante de Lipschitz ($L^*$) para extender los límites de error obtenidos de los datos a todo el dominio alcanzable, asegurando que no haya "huecos" sin cobertura.

C. Proyección y Garantía Formal

• Los conjuntos alcanzables calculados en el espacio elevado se proyectan de vuelta al espacio de estado original.
• Se suman (Minkowski) los conjuntos de incertidumbre derivados (residuos, ruido, error de cobertura) para obtener un sobre-approximación garantizada del conjunto alcanzable real del sistema no lineal.
• Teorema Principal: El artículo demuestra matemáticamente que el conjunto alcanzable calculado por el algoritmo propuesto contiene estrictamente al conjunto alcanzable exacto del sistema real ($\bar{X}_k \subseteq R'_k$).

3. Contribuciones Clave

1. Marco de Datos para Sistemas No Lineales: Introducción de un marco de análisis de alcanzabilidad para sistemas Lipschitz no afines que aprende incrustaciones de Koopman directamente de mediciones ruidosas de estado-entrada.
2. Identificación Dependiente de Estado-Entrada: Desarrollo de un enfoque de elevación que utiliza observables dependientes tanto del estado como de la entrada, mejorando la precisión de la aproximación lineal en comparación con los modelos LTI elevados estándar.
3. Cálculo Escalable con Garantías: Cálculo de conjuntos alcanzables escalables mediante la propagación de zonotopos en el espacio elevado, proyectados de vuelta al espacio original con conjuntos de incertidumbre derivados de datos, proporcionando garantías formales de seguridad.
4. Validación Empírica: Validación del marco en sistemas de referencia no lineales y en un vehículo autónomo real, demostrando una reducción significativa en el conservadurismo en comparación con métodos basados en modelos y métodos de datos lineales.

4. Resultados y Evaluación

Los autores evaluaron el método en tres escenarios:

• Ejemplo 1: Sistema Dinámico Lipschitz Afín (Reactor CSTR):

  • Se comparó el método propuesto con CORA (herramienta basada en modelos) y un modelo de mínimos cuadrados (LS) puramente lineal.
  • Resultado: El método propuesto mostró una reducción significativa en el conservadurismo en horizontes de predicción largos, manteniendo la precisión de la sobre-approximación.

• Ejemplo 2: Sistema Dinámico No Lineal No Afín:

  • Se utilizó un sistema con dinámicas complejas no afines.
  • Resultado: El método basado en Koopman generó conjuntos alcanzables mucho más ajustados (menos conservadores) que tanto el enfoque basado en modelos como el método LS, demostrando su capacidad para capturar dinámicas no lineales complejas.

• Ejemplo 3: Vehículo Autónomo (JetRacer):

  • Experimento en un robot de carreras real con hardware embebido (NVIDIA Jetson Nano).
  • Resultado: En un escenario de mundo real con ruido, el método propuesto produjo sobre-approximaciones de conjuntos alcanzables sustancialmente más ajustadas que el método LS, especialmente a lo largo de horizontes temporales extendidos.

5. Significado e Impacto

Este trabajo es significativo porque cierra la brecha entre la identificación de sistemas basada en datos y la verificación formal de seguridad.

• Superación del Conservadurismo: Permite realizar análisis de seguridad en sistemas no lineales complejos sin caer en el exceso de conservadurismo típico de las aproximaciones lineales simples, lo que es crucial para la operación eficiente de robots en entornos dinámicos.
• Garantías Deterministas: A diferencia de los métodos probabilísticos (como la predicción conformal), este enfoque ofrece garantías deterministas de que todas las trayectorias posibles (dentro de los límites de ruido y error) están contenidas en el conjunto calculado.
• Aplicabilidad Práctica: Al demostrar su eficacia en un vehículo autónomo real, valida que la teoría del operador de Koopman puede implementarse exitosamente en sistemas embebidos para tareas de seguridad crítica.

En resumen, el artículo propone una solución robusta para la verificación de seguridad en robótica moderna, combinando la flexibilidad del aprendizaje de datos con la rigurosidad matemática de la teoría de conjuntos y el análisis de estabilidad.