On the Computation of Backward Reachable Sets for Max-Plus Linear Systems with Disturbances

A continuación presento un resumen técnico detallado del artículo "On the Computation of Backward Reachable Sets for Max-Plus Linear Systems with Disturbances" (Sobre el cálculo de conjuntos alcanzables hacia atrás para sistemas lineales max-plus con perturbaciones), escrito por Yuda Li y Xiang Yin.

---

1. Problema de Investigación

El artículo aborda el problema de análisis de alcanzabilidad hacia atrás (backward reachability) en Sistemas Lineales Max-Plus (MPLS) que operan bajo incertidumbre.

• Contexto: Los sistemas MPLS son un modelo fundamental para sistemas de eventos discretos (como redes de Petri temporizadas, sistemas de fabricación y transporte) donde la sincronización y los retrasos se describen mediante el álgebra max-plus.
• Desafío: En aplicaciones prácticas, estos sistemas están sujetos a perturbaciones (ruido, errores de modelado, variaciones de parámetros). El objetivo es determinar, dado un conjunto objetivo (o de seguridad) $E$, el conjunto de estados iniciales desde los cuales existe una entrada de control admisible tal que, para todas las perturbaciones admisibles, el estado sucesor permanece dentro de $E$.
• Dificultad: La cuantificación universal sobre el conjunto de perturbaciones ($\forall w \in W$) introduce una complejidad computacional significativa. Los enfoques existentes basados en matrices de límites de diferencia (DBMs) o representaciones por intervalos pueden volverse prohibitivamente costosos a medida que crece la dimensionalidad del sistema o la estructura de la incertidumbre.

2. Metodología Propuesta

Los autores proponen un marco computacional basado en la geometría tropical y, específicamente, en la teoría de poliedros tropicales.

A. Formulación del Sistema

Se considera un sistema lineal max-plus con perturbaciones aditivas:
$$x_k = A \otimes x_{k-1} \oplus B \otimes u_k \oplus C \otimes w_k$$
Donde:

• $x_k$: Estado del sistema.
• $u_k$: Entrada de control (pertenece a un conjunto $U$).
• $w_k$: Perturbación (pertenece a un conjunto $W$).
• $\otimes$ y $\oplus$ son las operaciones de suma y multiplicación del álgebra max-plus ($a \otimes b = a+b$, $a \oplus b = \max(a,b)$).

B. Descomposición del Operador de Alcanzabilidad

El operador de alcanzabilidad hacia atrás de un paso, $\Upsilon(E)$, se descompone en tres operadores elementales:

1. Operador Inverso ($A^{-1}$): Maneja la dinámica autónoma del sistema.
2. Operador Inverso Existencial ($\gamma_U$): Maneja la existencia de una entrada de control ($\exists u \in U$).
3. Operador Inverso Universal ($\phi_W$): Maneja la universalidad sobre las perturbaciones ($\forall w \in W$).

La relación es: $\Upsilon = A^{-1} \circ \gamma_U \circ \phi_W$.

C. Hipótesis de Representación

El núcleo de la propuesta es asumir que el conjunto objetivo $E$, el conjunto de control $U$ y el conjunto de perturbación $W$ están representados como poliedros tropicales. Un poliedro tropical se define como la intersección de un número finito de semiespacios tropicales (o equivalentemente, generado por un conjunto finito de vectores).

3. Contribuciones Clave y Resultados Técnicos

Preservación de la Estructura Poliedral

La contribución teórica más importante es demostrar que los operadores $A^{-1}$, $\gamma_U$ y $\phi_W$ preservan la estructura de poliedro tropical. Esto significa que si el conjunto objetivo es un poliedro tropical, el conjunto alcanzable hacia atrás resultante también lo es. Esto permite realizar cálculos iterativos dentro del mismo marco algebraico sin perder la compacidad de la representación.

Algoritmos Computacionales Específicos

1. Para $A^{-1}$ y $\gamma_U$:

   • Se demuestra que estas operaciones pueden reformularse como proyecciones de conos tropicales en espacios de dimensión superior.
   • Se derivan métodos constructivos para obtener la representación externa (M-form) o interna (V-form) del conjunto resultante mediante matrices aumentadas.

2. Para $\phi_W$ (El caso más complejo):

   • Simplificación: Se utiliza la descomposición de un poliedro tropical en un cono tropical (cono de recesión) y un poliedro acotado. Se demuestra que si el cono de recesión de las perturbaciones está contenido en el cono de recesión del conjunto objetivo, el cálculo se reduce al caso de perturbaciones acotadas.
   • Semiespacios Pseudo-Tropicales: El operador universal se reformula como la intersección de "semiespacios pseudo-tropicales".
   • Generación de Vectores: Se propone un algoritmo inductivo (basado en el Teorema 1) para calcular el conjunto generador de la intersección de estos semiespacios. El algoritmo combina vectores que satisfacen la condición con aquellos que no, calculando un factor de escala $\rho$ máximo para mantener la pertenencia al conjunto.
   • Filtrado de Puntos Extremos: Se incorpora un procedimiento de filtrado de puntos extremos (basado en grafos hiperdirigidos) para reducir la complejidad computacional eliminando generadores redundantes en cada iteración.

4. Estudio de Caso

El artículo incluye un ejemplo numérico (Sección VII) que ilustra el proceso completo:

• Se define un sistema 2D con una matriz de estado $A$, entrada $B$ y perturbación $C$.
• El conjunto de seguridad $S$ y el conjunto de perturbaciones $W$ se definen como poliedros tropicales.
• Se calcula paso a paso:
  1. $\phi_W(S)$: El conjunto de estados seguros ante todas las perturbaciones.
  2. $\gamma_U(\cdot)$: El conjunto de estados desde los cuales se puede elegir un control para mantenerse en el conjunto anterior.
  3. $A^{-1}(\cdot)$: El conjunto final de estados alcanzables hacia atrás.
• Los resultados se visualizan geométricamente, mostrando cómo el conjunto alcanzable se contrae o expande según las restricciones de seguridad y perturbación.

5. Significado y Conclusión

• Nueva Perspectiva Geométrica: El trabajo ofrece una alternativa robusta a los métodos probabilísticos y a los enfoques basados en intervalos o DBMs para el análisis de sistemas max-plus inciertos.
• Herramienta Algebraica: Proporciona herramientas algebraicas y geométricas concretas para la verificación de seguridad y la síntesis de controladores en sistemas de eventos discretos.
• Escalabilidad Potencial: Al preservar la estructura de poliedro tropical, el método evita la explosión combinatoria que a menudo sufren los métodos de discretización de espacios de estado, aunque los autores reconocen que la eficiencia computacional sigue siendo un desafío para sistemas de muy alta dimensión.
• Aplicabilidad: Es particularmente relevante para sistemas de transporte, fabricación y planificación donde la sincronización es crítica y las perturbaciones son deterministas pero desconocidas dentro de un rango acotado.

En resumen, el artículo establece un marco teórico y computacional riguroso para resolver problemas de control seguro en sistemas max-plus inciertos, demostrando que la geometría tropical es el lenguaje natural para manejar la interacción entre dinámicas lineales, control y perturbaciones en este contexto.