⚡ electrical engineering

Computing Sound Lower and Upper Bounds on Hamilton-Jacobi Reach-Avoid Value Functions

Este artículo presenta un algoritmo que calcula cotas inferiores y superiores rigurosas para las funciones de valor de la alcanzabilidad de Hamilton-Jacobi, garantizando así aproximaciones superiores y inferiores seguras de los conjuntos alcanzables en sistemas de control no lineales, junto con un método de refinamiento para mejorar la precisión de estas cotas.

Autores originales: Ihab Tabbara, Eliya Badr, Hussein Sibai

Publicado 2026-03-31

📖 5 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Ihab Tabbara, Eliya Badr, Hussein Sibai

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina que eres el capitán de un barco que debe navegar por un océano lleno de arrecifes (el peligro) y llegar a una isla dorada (la meta). Tu misión es saber, desde cualquier punto del mapa, si es posible llegar a la isla sin chocar contra los arrecifes.

En el mundo de la ingeniería y los robots, esto se llama "análisis de alcanzabilidad". Los científicos usan una herramienta matemática muy potente llamada Ecuación de Hamilton-Jacobi para dibujar este mapa de seguridad. Pero aquí está el problema: las computadoras no pueden ver el océano infinito con total precisión; tienen que dividirlo en un tablero de ajedrez (una cuadrícula) para calcularlo.

El problema es que, al usar este tablero, a veces se cometen errores de redondeo. Es como si dibujaras un mapa en una hoja de papel cuadriculado: si la cuadrícula es muy grande, podrías pensar que un arrecife es más pequeño de lo que es, o que un camino seguro es más amplio de lo que realmente es. Esto es peligroso: podrías decirle a tu robot "¡pasa por ahí!" y chocar, o decir "¡no pases!" cuando en realidad podría haberlo hecho.

¿Qué propone este paper?

Los autores (Ihab, Eliya y Hussein) han creado un nuevo método para garantizar que el mapa nunca miente, incluso si la cuadrícula es tosca. Lo hacen de una manera muy inteligente, usando dos "guardianes" o "límites":

El Guardián Pesimista (Límite Inferior): Este es el guardián que siempre piensa lo peor. Si él dice "puedes pasar", entonces es 100% seguro. No hay duda. Si él duda, no pasa nada, simplemente no lo certificamos como seguro todavía.
El Guardián Optimista (Límite Superior): Este es el guardián que siempre ve el peligro. Si él dice "es peligroso", entonces es 100% peligroso. No hay duda. Si él duda, simplemente no lo certificamos como peligroso todavía.

La analogía de la caja de herramientas:
Imagina que intentas medir la altura de una puerta para ver si un mueble cabe.

El método antiguo usaba una regla de madera con marcas muy separadas. A veces medías 2 metros y a veces 2.1 metros. No sabías si el mueble (de 2.05m) cabía o no.
El nuevo método usa dos reglas especiales:
- Una que siempre mide un poco más bajo de lo real (garantizando que si dice "cabe", cabe de verdad).
- Otra que siempre mide un poco más alto (garantizando que si dice "no cabe", no cabe de verdad).
- Si las dos reglas coinciden en que el mueble cabe, ¡estás seguro! Si una dice que cabe y la otra que no, el sistema dice: "No estoy seguro, necesito una regla más fina aquí".

El truco del "Parada Temprana"

Normalmente, para que estos cálculos sean perfectos, la computadora tiene que repetir el proceso millones de veces hasta que el resultado deje de cambiar (como esperar a que el agua se asiente). Pero eso tarda muchísimo tiempo.

Los autores dicen: "¿Y si paramos antes?".
El problema es que si paras antes, tu cálculo puede ser un poco inexacto. Pero ellos inventaron una fórmula de corrección (como un "parche" matemático) que se aplica al resultado antes de detenerse. Es como si, al terminar de cocinar un pastel antes de tiempo, supieras exactamente cuántos minutos le faltan para estar perfecto y ajustaras la receta para que, aunque lo saques ahora, sepa igual de bien. Esto les permite obtener resultados rápidos pero matemáticamente seguros.

El "Refinamiento Inteligente" (Cortar el pastel)

Si después de aplicar los dos guardián y el parche, todavía hay zonas del mapa donde no saben si es seguro o peligroso (la "zona gris"), el algoritmo no se rinde.
En lugar de volver a calcular todo el mapa desde cero, toma solo esas zonas dudosas y las corta en pedazos más pequeños (como cortar una pizza en rebanadas más finas solo donde hay queso derretido). Luego, vuelve a aplicar los guardián en esos pedazos pequeños.

Esto hace que el mapa sea increíblemente detallado justo donde se necesita (cerca de los arrecifes o la meta) y rápido en las zonas abiertas.

¿Por qué es importante?

Seguridad Real: Para un coche autónomo o un robot quirúrgico, no sirve de nada decir "probablemente es seguro". Necesitas saber que es seguro. Este método garantiza que si el robot se mueve, no chocará.
Eficiencia: Al no tener que esperar a que los cálculos sean "perfectos" (infinitos) y al solo refinar las zonas difíciles, ahorran mucho tiempo de computadora.
Flexibilidad: Funciona tanto para evitar obstáculos (como un coche esquivando un camión) como para llegar a una meta evitando peligros (como un dron entregando un paquete).

En resumen:
Este paper es como crear un GPS para robots que nunca miente. En lugar de dar una ruta que "parece" segura, el sistema dibuja dos mapas: uno que garantiza que la ruta es segura y otro que garantiza que el peligro es real. Si hay dudas, el sistema se enfoca en esas dudas, las hace más pequeñas y las vuelve a verificar, todo sin perder tiempo calculando cosas que ya sabemos. Es una forma de hacer que la inteligencia artificial sea no solo inteligente, sino responsable y segura.

Título del Trabajo

Cálculo de Límites Inferiores y Superiores Sonoros para las Funciones de Valor de Alcanzabilidad de Hamilton-Jacobi

1. El Problema

La verificación de seguridad y la síntesis de control para sistemas de control no lineales dependen fundamentalmente del análisis de alcanzabilidad de Hamilton-Jacobi (HJ). Este análisis calcula el Conjunto de Alcanzabilidad Inversa (BRS) (estados desde los cuales es imposible evitar un conjunto de fallo) y el Conjunto de Alcanzabilidad-Evitación (RAS) (estados desde los cuales se puede alcanzar un objetivo evitando el fallo).

El problema central identificado por los autores es que los métodos clásicos de HJ resuelven numéricamente la ecuación en derivadas parciales (EDP) sobre una malla (grid) que discretiza el espacio de estados continuo. Estas aproximaciones:

No tienen en cuenta explícitamente los errores de discretización.
No garantizan que el conjunto calculado sea una sobrecarga (over-approximation) del BRS (garantizando seguridad) o una subcarga (under-approximation) del RAS (garantizando alcanzabilidad).
A menudo fallan al clasificar correctamente las celdas de la malla, especialmente cuando se detiene la iteración de valor antes de la convergencia total.

2. Metodología

Los autores proponen un marco que calcula límites superiores e inferiores sonoros (garantizados) para la función de valor de HJ, $V_\gamma$ , sobre el espacio de estados continuo.

Abstracción Discreta: Se construye una abstracción del sistema continuo utilizando una malla finita. Se define una relación de transición no determinista que sobrecarga el conjunto de estados alcanzables reales para cada celda y acción.
Funciones de Valor Acotadas: En lugar de calcular una única función de valor aproximada, el algoritmo calcula dos funciones de valor discretas:
- $V^\gamma$ (Límite inferior): Garantiza que si $V^\gamma(s) > 0$ , toda la celda $s$ pertenece al conjunto seguro (RAS).
- $V_\gamma$ (Límite superior): Garantiza que si $V_\gamma(s) \le 0$ , toda la celda $s$ pertenece al conjunto de fallo (BRS).
Manejo de Errores de Discretización y Terminación Temprana:
- Se utilizan constantes de Lipschitz de las funciones de fallo y recompensa para acotar los valores dentro de cada celda.
- Se introduce un término de corrección basado en la diferencia mínima entre iteraciones consecutivas ( $\delta_k$ ) y el factor de descuento $\gamma$ . Esto permite detener la iteración de valor antes de la convergencia completa manteniendo la garantía de sonido (soundness).
Algoritmo de Refinamiento Adaptativo (Algoritmo 2):
- Las celdas que no pueden ser clasificadas definitivamente (donde el límite inferior es $\le 0$ y el superior es $> 0$ ) se identifican como "no clasificadas".
- Estas celdas se dividen recursivamente a lo largo de su lado más largo.
- Se vuelven a calcular los límites en la malla refinada hasta alcanzar una resolución mínima definida por el usuario o hasta que todas las celdas sean clasificadas.

3. Contribuciones Clave

Algoritmo de Límites Sonoros: Presentación de un algoritmo que calcula límites superiores e inferiores rigurosos para funciones de valor de HJ en sistemas no lineales de tiempo discreto, contabilizando explícitamente los errores de discretización.
Garantía en Terminación Temprana: Demostración teórica de que los límites calculados son correctos incluso si la iteración de valor se detiene antes de alcanzar el punto fijo, gracias al término de corrección propuesto.
Refinamiento Adaptativo Local: Desarrollo de un algoritmo que refina selectivamente solo las celdas de la frontera (no clasificadas), logrando aproximaciones más precisas del BRS y RAS sin la sobrecarga computacional de refinar toda la malla uniformemente.
Validación Experimental: Comparación exhaustiva con herramientas existentes (ROCS 2.0 y un toolbox clásico de HJ), demostrando superioridad en la precisión del conjunto alcanzable y garantías de seguridad.

4. Resultados

Los autores validaron su método en dos estudios de caso:

Coche Dubins: Un modelo de vehículo con dinámica no lineal y un obstáculo cilíndrico.
Evasión 3D: Un escenario de persecución-evasión aérea en tres dimensiones.

Hallazgos principales:

Precisión vs. Herramientas Existentes: El toolbox clásico de HJ (basado en EDPs) tendía a subestimar el BRS o mal clasificar estados en resoluciones bajas, etiquetando erróneamente estados inseguros como seguros. El método propuesto nunca cometió este error.
Eficiencia y Escalabilidad: Aunque el tiempo de ejecución crece linealmente con el tamaño de la malla (que crece exponencialmente con las iteraciones de refinamiento), el método propuesto logró calcular conjuntos de alcanzabilidad-evitación (RAS) más grandes que ROCS 2.0 en menos tiempo, o con la misma resolución, ofreciendo garantías de sonido que ROCS no proporciona en la misma medida.
Impacto del Refinamiento: El algoritmo de refinamiento (Algoritmo 2) permitió reducir drásticamente el número de celdas "no clasificadas" (gris en las visualizaciones), proporcionando una definición precisa de los límites de seguridad.
Factor de Descuento ( $\gamma$ ): Se observó que valores de $\gamma$ cercanos a 1 (pero menores) ofrecen clasificaciones similares a $\gamma=1$ , pero permiten el uso del término de corrección para terminación temprana, equilibrando precisión y tiempo de cómputo.

5. Significancia

Este trabajo es significativo porque cierra una brecha crítica en la verificación formal de sistemas de control no lineales:

Garantías Formales: Proporciona la primera metodología que asegura matemáticamente que los conjuntos calculados son aproximaciones conservadoras (sobrecarga del BRS, subcarga del RAS), eliminando la incertidumbre inherente a los métodos numéricos tradicionales.
Aplicabilidad en Sistemas Críticos: Es fundamental para aplicaciones de seguridad crítica (vehículos autónomos, robótica quirúrgica), donde un error en la clasificación de un estado como "seguro" cuando en realidad es "peligroso" puede tener consecuencias catastróficas.
Eficiencia Computacional: Al combinar la iteración de valor con un refinamiento adaptativo local y correcciones por terminación temprana, hace viable el análisis de alcanzabilidad en sistemas complejos donde los métodos de convergencia total serían prohibitivamente costosos.

En resumen, el paper ofrece un marco robusto para la síntesis de control y verificación de seguridad que combina la precisión de los métodos analíticos con la eficiencia de los métodos discretos, asegurando que las decisiones de control basadas en estos análisis sean formalmente seguras.