# Control de Modelos Max Plus Lineales con Restricciones Temporales

Carolina Cárdenas, Juan Cardillo, Claude Martinez, Jean-Jacques Loiseau

► To cite this version:

Carolina Cárdenas, Juan Cardillo, Claude Martinez, Jean-Jacques Loiseau. Control de Modelos Max Plus Lineales con Restricciones Temporales. Revista Iberoamericana de Automática e Informática Industrial RIAI, 2016, 13 (4), pp.438 - 449. 10.1016/j.riai.2016.07.001. hal-01364596

HAL Id: hal-01364596

https://hal.science/hal-01364596

Submitted on 13 Sep 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
Control de Modelos Max Plus Lineales
con Restricciones Temporales

C. Cárdenas<sup>a,1,*</sup>, J. Cardillo<sup>b</sup>, J. J. Loiseau<sup>a</sup>, C. Martinez<sup>a</sup>

<sup>a</sup>LUNAM Université, IRCCyN UMR CNRS 6597, 1 rue de la Noë, BP 92101, 44321 Nantes cedex 03, France.

<sup>b</sup>LaSDAI, Departamento de Computación, Universidad de los Andes. Av. Tulio Febres Cordero, Mérida 5101, Venezuela

**Abstract**

Este artículo trata del control de sistemas de eventos discretos sujetos a sincronización y fenómenos de retraso, descritos por un modelo max plus lineal. Definimos y caracterizamos el conjunto de condiciones iniciales admisibles, las cuales originan soluciones no decrecientes. Restricciones temporales son impuestas al espacio de estado del sistema. Estas restricciones son descritas en el cono max plus definido por la imagen de la estrella de Kleene de la matriz asociada a las restricciones temporales. Propiedades geométricas de este cono max plus, para garantizar que la evolución del sistema en lazo cerrado satisface las restricciones, son estudiadas. Condiciones suficientes concernientes a la existencia y cálculo de una retroalimentación de estado son presentadas. Para ilustrar la aplicación de este enfoque, dos problemas de control son discutidos, para los cuales un controlador es diseñado con el objetivo de garantizar la satisfacción de las restricciones temporales.

**Keywords:**

Sistemas de Eventos Discretos (SED), Grafos de Eventos Temporizados (GETs), Algebra Max Plus, Restricciones Temporales.

# 1. Introducción

El Algebra max plus, denotada por $\mathbb{R}_{max}$, es un semi-anillo idempotente conmutativo. Esta estructura algebraica es particularmente adecuada para representar sistemas de eventos discretos (SED) que son sujetos a fenómenos de sincronización y retardos, debido a que la descripción del comportamiento dinámico de estos sistemas puede ser expresada por ecuaciones lineales en el contexto max plus. La sincronización puede ser modelada usando las operaciones de maximización, esto es, una nueva operación comienza tan pronto como todas las operaciones precedentes han sido finalizadas, y la operación de la adición corresponde a la duración de las actividades, esto es, el tiempo de finalización de una operación es igual al tiempo de inicio de la operación mas el tiempo de duración de la misma. Esta clase de sistemas es llamada SED max plus lineales. Dentro de estos sistemas encontramos los sistemas de producción, las redes ferroviarias, las redes de tráfico urbano, los sistemas de colas, entre otros (Baccelli et al., 1992). Los grafos de eventos temporizados (GETs) han sido usados para modelar los SED max plus lineales. Los GETs forman una subclase de las redes de Petri, en los cuales todos los nodos lugares tienen un único nodo transición de entrada y un único nodo transición de salida.

Este artículo aborda el problema de control para sistemas max plus lineales, modelados por GETs y sujetos a restricciones de tiempo que deben ser respetadas. Este tipo de problema se encuentra en algunos sistemas de producción donde la duración de tareas particulares dentro de un proceso, están sujetas a

restricciones de tiempo. Por ejemplo, en (Atto et al., 2011) los autores consideran una planta industrial especializada en la fabricación de tubos de caucho para la industria automotriz. Las restricciones de tiempo son impuestas en la zona de calentamiento, para evitar la pérdida de piezas. Para ello, modifican la ecuación de estados max plus lineales del sistema en la forma de una ecuación de estados restrictiva, para obtener un supervisor que respete las restricciones. Problemas de restricciones temporales se encuentran también en la producción de obleas de silicio en la industria de semiconductores (Wu et al., 2008; Kim et Lee, 2003).

Nuestro objetivo es encontrar una ley de control por retroalimentación de estado que asegure que el estado del sistema evoluciona sin violar un conjunto de restricciones temporales impuestas al sistema. En (Maia et al., 2011) trabajan sobre el semi-anillo idempotente $\mathbb{Z}_{max}$ y proponen una estrategia de control basada en la teoría de residuación, que asegura que el estado del sistema evoluciona satisfaciendo algunas restricciones predefinidas, usando únicamente propiedades algebraicas de las matrices del sistema. (Katz, 2007) presenta como una aplicación el estudio de una red ferroviaria, la cual evoluciona de acuerdo a un conjunto de restricciones de tiempo descritas en un cono max plus, llamado la especificación. Este cono max plus es definido en términos de una matriz E y usando un vector de estado extendido. El diseño del control viene del cálculo del máximo invariante controlable contenido en la especificación. Este cálculo se garantiza para una clase particular de conos max plus en $\mathbb{Z}_{max}^n$, basado en condiciones de finitud sobre la especificación.

En contraste al enfoque presentado en esta contribución, el cual es basado en el control geométrico, (Amari et al., 2012)

<footnote>*Autor en correspondencia.</footnote>

<footnote>Email address: Carolina.Cardenas@irccyn.ec-nantes.fr (C. Cárdenas)</footnote>
proponen un enfoque algebraico para la síntesis de una ley de control causal de GETs sujetos a restricciones de tiempo. Es- tas restricciones son representadas por desigualdades en álge- bra max plus. La existencia y cálculo de la ley de control se muestra bajo la hipótesis de condiciones iniciales canónicas.

Apoyados en los trabajos de (Amari et al., 2012) y (Katz, 2007), presentamos una formulación alternativa de nuestro pro- blema de control en términos de invarianza controlable e inva- rianza por retroalimentación de estado, derivada de propiedades geométricas, y consideramos condiciones iniciales admisibles generales de sistemas lineales max plus. El problema de las res- tricciones temporales es introducido por medio de una matriz C sobre el semi-anillo max plus. Resumimos estas restricciones en el cono max plus definido por la imagen de la estrella de Kleene C*. Este cono max plus resulta ser invariante controla- ble en si mismo, evitando así el cálculo del máximo cono max plus invariante controlable incluido en una especificación dada. El procedimiento para este cálculo puede resultar difícil pues depende de la convergencia del algoritmo de punto fijo extendi- do en el contexto max plus (Katz, 2007). El diseño del control viene del estudio de una condición geométrica. La matriz de control es construida a partir del cálculo de sistemas de gene- radores de poliedros max plus (Allamigeon et al. 2010, 2012) que involucran componentes de las matrices del sistema asocia- das con lugares del GET donde se han impuesto restricciones temporales.

Este artículo es organizado como sigue: Sección 2, después de una breve introducción al semi-anillo max plus, se introdu- cen algunos conceptos relevantes de la teoría de convexidad max plus, y el control geométrico es discutido. En la Sección 3, los GETs son recordados, y una caracterización geométrica de las condiciones iniciales admisibles generales es propuesta. La Sección 4 se inicia con la definición de restricciones tem- porales, se define el cono max plus $Cx(k) \le x(k)$, donde C es la matriz que resume las restricciones temporales, luego el problema de encontrar una ley de control por retroalimentación de estados, que satisfaga las restricciones de tiempo impuestas al sistema es formulado y algunos resultados teóricos sobre la existencia de una matriz de control son presentados. Sección 5, son desarrollados dos ejemplos ilustrativos, y por último las conclusiones son dadas en la sección 6.

## 2. Preliminares

### 2.1. Algebra max plus

El Algebra max plus es un semi-anillo idempotente (o dioi- de), denotado por $\mathbb{R}_{\max}$, y definido como el conjunto $\mathbb{R} \cup \{-\infty\}$, equipado con dos operaciones, la adición $x \oplus y := \max(x, y)$ y la multiplicación $x \otimes y := x + y$. La operación $\oplus$ es asociativa, conmutativa e idempotente, esta es, $a \oplus a = a$, $\forall a \in \mathbb{R}_{\max}$, y tie- ne un elemento cero $\epsilon := -\infty$. La operación $\otimes$ es asociativa, y tiene un elemento unidad $e := 0$. Además el elemento cero $\epsilon$ es absorbente, es decir, para cualquier $x \in \mathbb{R}_{\max}$, $\epsilon \otimes x = x \otimes \epsilon = \epsilon$. En algunas situaciones el símbolo “$\otimes$” será omitido como en el álgebra convencional, esto es, $a \otimes b = ab$. Un orden natural es definido sobre $\mathbb{R}_{\max}$: $x \le y \Leftrightarrow x \oplus y = y$, ver por ejem- plo (Baccelli et al., 1992). Las operaciones $\oplus$ y $\otimes$ son extendi-

das de forma natural a vectores y matrices sobre el semi-anillo max plus: $(A \oplus B)_{ij} = A_{ij} \oplus B_{ij}$, $(A \otimes B)_{ij} = \bigoplus_{k=1}^{n} A_{ik} \otimes B_{kj}$ y $(\lambda \otimes A)_{ij} = \lambda \otimes A_{ij}$, para toda $i, j$, donde A y B son matrices de dimensiones adecuadas y $\lambda \in \mathbb{R}_{\max}$. Para $p, q \in \mathbb{N}$, denota- mos por $\mathbb{R}_{\max}^{p \times q}$, el conjunto de todas las matrices de orden $p \times q$ sobre el semi-anillo max plus. Denotemos por $e^k \in \mathbb{R}_{\max}^n$, el k- ésimo vector unidad, es decir, el vector definido por $(e^k)_k := e$ y $(e^k)_h := \epsilon$ si $h \ne k$. Denotemos el conjunto $\{1, 2, \dots, n\}$ por $\tilde{n}$, y definamos para todo vector $x \in \mathbb{R}_{\max}^n$, el soporte de $x$ por $\sup(x) = \{i \in \tilde{n} \mid x_i \ne \epsilon\}$. Diremos que $x \in \mathbb{R}_{\max}^n$ tiene soporte pleno si $\sup(x) = \tilde{n}$. Usualmente denotaremos un vector nulo, o una matriz nula de cualquier dimensión por $\epsilon$, como el elemen- to neutro de la adición, y denotaremos por $\mathbb{I}$ la matriz identidad max plus, esto es, la matriz cuadrada definida por $\mathbb{I}_{ij} = e$ si $i = j$ y $\mathbb{I}_{ij} = \epsilon$ en caso contrario. Para una matriz $A \in \mathbb{R}_{\max}^{p \times q}$, denota- remos la imagen de A por Im A, definida por $\{Ax \mid x \in \mathbb{R}_{\max}^q\}$. Dados dos subconjuntos $S_1$ y $S_2$ de $\mathbb{R}_{\max}^n$, la suma de Minkows- ki $S_1 \oplus S_2$ es definida como el conjunto $\{x \oplus y \mid (x, y) \in S_1 \times S_2\}$. Finalmente, diremos también que para $x, y \in \mathbb{R}_{\max}^n$, $x \ge y$, si $x_i \ge y_i$, para $i = 1, \dots, n$.

Dada una matriz $C \in \mathbb{R}_{\max}^{n \times n}$, su estrella de Kleene, definida por

$$C^* = \bigoplus_{k \in \mathbb{N}} C^k,$$

está bien definida en el dioide completo $\tilde{\mathbb{R}}_{\max} = \mathbb{R} \cup \{-\infty\} \cup \{+\infty\}$. En nuestro estudio $C^*$ tiene entradas en $\mathbb{R}_{\max}$.

**Proposición 2.1.** (Libeaut et al., 1995) Dada una matriz cuadrada $C \in \mathbb{R}_{\max}^{n \times n}$, y un vector $x \in \mathbb{R}_{\max}^n$. Las siguientes afirmaciones son equivalentes:

(i) $C \otimes x \le x$,

(ii) $x = C^* \otimes x$,

(iii) $x \in \mathrm{Im} C^*$.

### 2.2. Sistemas max plus lineales

Los sistemas de eventos discretos con sincronización y no concurrencia pueden ser descritos por un modelo de la forma (Baccelli et al., 1992):

$$x(k) = A \otimes x(k-1) \oplus B \otimes u(k), \quad (1)$$

$$y(k) = C \otimes x(k). \quad (2)$$

El índice *k* es llamado contador de eventos. Las componentes del estado $x(k)$ son los instantes de tiempo en los cuales los eventos internos ocurren para el *k*-ésimo instante, las componentes de la entrada $u(k)$ son los instantes de tiempo en los cuales los eventos de entrada ocurren para el *k*-ésimo instante, y las componentes de la salida $y(k)$ son los instantes de tiempo en los cuales los eventos de salida ocurren para el *k*-ésimo instante. Las matrices A, B y C son llamadas las matrices del sistema con $A \in \mathbb{R}_{\max}^{n \times n}$, $B \in \mathbb{R}_{\max}^{n \times q}$ y $C \in \mathbb{R}_{\max}^{p \times n}$, donde *q* es el número de entradas y *p* es el número de salidas. Los SED que pueden ser descritos por este modelo serán llamados sistemas de eventos discretos max plus lineales o simplemente sistemas max plus lineales.
## 2.3. Poliedros y conos max plus

Debido a que nuestro problema de control conlleva el cálculo de sistemas generadores de conjuntos de la forma $Mx \le Nx$, usando un algoritmo de eliminación general (Método de doble descripción tropical), (Allamigeon et al. 2010), a continuación introduciremos nociones generales y conceptos principales de la teoría de convexidad max plus, tal como poliedros y conos poliédricos max plus; y describiremos una relación entre estos conjuntos basados en la técnica de homogenización.

**Definición 2.1.** Los poliedros max plus (o tropicales) de $\mathbb{R}_{\max}^n$ son definidos como la intersección de un número finito de semi-espacios tropicales, los cuales son conjuntos formados por las soluciones $x = (x_i) \in \mathbb{R}_{\max}^n$ de una desigualdad de la forma:

$$ \bigoplus_{1 \le i \le n} m_i x_i \oplus m_0 \le \bigoplus_{1 \le i \le n} n_i x_i \oplus n_0, \quad (3) $$

donde $m_i, n_i \in \mathbb{R}_{\max}$ para todo $i = 0, \dots, n$.

Luego, un poliedro tropical $\mathcal{P}$ se expresa como:

$$ \mathcal{P} = \{ x \in \mathbb{R}_{\max}^n \mid Mx \oplus r \le Nx \oplus s \}, $$

donde $M, N \in \mathbb{R}_{\max}^{p \times n}$, $r, s \in \mathbb{R}_{\max}^n$ y $p > 0$.

**Definición 2.2.** Los conos max plus (o tropicales) de $\mathbb{R}_{\max}^n$ son definidos en forma similar sólo que en (3) los coeficientes $m_0$ y $n_0$ son omitidos. Luego, un cono max plus $C$ se expresa como:

$$ C = \{ x \in \mathbb{R}_{\max}^n \mid Mx \le Nx \}, $$

donde $M, N \in \mathbb{R}_{\max}^{p \times n}$, y $p > 0$.

Dado un subconjunto $S \subset \mathbb{R}_{\max}^n$, el envolvente convexo max plus de $S$, denotado $co(S)$, es definido como el conjunto de las combinaciones convexas max plus $\alpha_1 x_1 \oplus \cdots \oplus \alpha_p x_p$ donde, $p \ge 1$, $x_1, \dots, x_p \in S$, $\alpha_1, \dots, \alpha_p \in \mathbb{R}_{\max}$ y $\alpha_1 \oplus, \dots \oplus \alpha_p = e$.

Para un subconjunto $S \subset \mathbb{R}_{\max}^n$, el cono max plus generado por $S$, denotado por $cone(S)$, es el conjunto de las combinaciones max plus lineales $\alpha_1 x_1 \oplus \cdots \oplus \alpha_p x_p$ donde, $p \ge 1$, $x_1, \dots, x_p \in S$, $\alpha_1, \dots, \alpha_p \in \mathbb{R}_{\max}$.

Gaubert y Katz han establecido un análogo tropical del teorema de Minkowski-Weyl en (S. Gaubert., Katz, R., 2007) y (S. Gaubert., Katz, R., 2009), donde se demuestran los siguientes teoremas.

**Teorema 2.1.** Los poliedros max plus de $\mathbb{R}_{\max}^n$ son precisamente los conjuntos de la forma $co(P) \oplus cone(R)$, donde $P$ y $R$ son subconjuntos finitos de $\mathbb{R}_{\max}^n$.

**Teorema 2.2.** Los conos max plus de $\mathbb{R}_{\max}^n$ son precisamente los conjuntos de la forma $cone(G)$ donde $G$ es un subconjunto finito de $\mathbb{R}_{\max}^n$.

Los subconjuntos $P$ y $R$ constituyen un sistema de generadores de $\mathcal{P}$, $(P, R)$ es llamada una representación generadora de $\mathcal{P}$, y el conjunto $G$ constituye un sistema de generadores de $C$.

Los poliedros max plus de $\mathbb{R}_{\max}^n$ pueden ser representados como conos max plus de $\mathbb{R}_{\max}^{n+1}$, agregando una dimensión adicional a este último para representar la componente afín del poliedro max plus. En el sentido clásico, este método es conocido como homogenización. En el sentido max plus este fue introducido en (Gaubert et al., 2007).

**Definición 2.3.** Sea $\mathcal{P} = \{ x \in \mathbb{R}_{\max}^n \mid Mx \oplus r \le Nx \oplus s \}$ un poliedro max plus no vacío ($M, N \in \mathbb{R}_{\max}^{p \times n}$, $r, s \in \mathbb{R}_{\max}^p$). El cono homegenizado $\hat{\mathcal{P}}$ es el cono max plus dado por:

$$ \hat{\mathcal{P}} = \{ z \in \mathbb{R}_{\max}^{n+1} \mid (M r) z \le (N s) z \}. $$

Cuando $x \in \mathbb{R}_{\max}^n$ y $\alpha \in \mathbb{R}_{\max}$, el elemento $(x, \alpha)$ se refiere al vector de $\mathbb{R}_{\max}^{n+1}$ cuyas $n$ primeras coordenadas coinciden con $x$, y la última coordenada es igual a $\alpha$. Existe una relación entre las representaciones generadoras de los poliedros max plus y su cono homogenizado, ver (Allamigeon et al., 2012) para más detalles. Si $G$ es un sistema de generadores del cono max plus $\hat{\mathcal{P}}$, tenemos que $\hat{\mathcal{P}} = \text{cone}(G)$. Después de multiplicar (en el sentido max plus) cada elemento de $G$ por un escalar no nulo, podemos asumir que la última coordenada de cada elemento de $G$ es $e \circ \epsilon$. Definiendo $P = \{x | (x, \epsilon) \in G\}$ y $R = \{x | (x, \epsilon) \in G\}$, se puede mostrar que $(P, R)$ forma una representación generadora de $\mathcal{P}$, y por tanto $\mathcal{P} = \text{co}(P) \oplus \text{cone}(R)$.

Para encontrar un sistema de generadores del cono homogenizado $\hat{\mathcal{P}}$ puede ser usado el Método de doble descripción tropical, (Allamigeon et al., 2010). Este método es una técnica incremental basada en una sucesiva eliminación de inecuaciones.

**Ejemplo 2.1.** Consideremos el poliedro max plus $\mathcal{P}$, definido por:

$$ \left[ \begin{array}{cc} 1 & e \\ 2 & 1 \end{array} \right] \left[ \begin{array}{c} x_1 \\ x_2 \end{array} \right] \oplus \left[ \begin{array}{c} 1 \\ 2 \end{array} \right] \le \left[ \begin{array}{cc} 1 & \epsilon \\ 2 & 1 \end{array} \right] \left[ \begin{array}{c} x_1 \\ x_2 \end{array} \right]. \quad (4) $$

Por la Definición 2.3, el cono homogenizado asociado a $\mathcal{P}$, denotado por $\hat{\mathcal{P}}$ es definido como el conjunto solución de,

$$ \left[ \begin{array}{ccc} 1 & e & 1 \\ 2 & 1 & 2 \end{array} \right] \left[ \begin{array}{ccc} z_1 \\ z_2 \\ z_3 \end{array} \right] \le \left[ \begin{array}{ccc} 1 & \epsilon & \epsilon \\ 2 & 1 & \epsilon \end{array} \right] \left[ \begin{array}{ccc} z_1 \\ z_2 \\ z_3 \end{array} \right]. \quad (5) $$

Resolviendo la primera desigualdad del sistema homogéneo (5), un sistema de generadores que la satisfaga, es el conjunto $G = \{(e \in \epsilon)^T, (e \in \epsilon)^T, (1 \in \epsilon)^T\}$. Multiplicando a la derecha y a la izquierda la segunda desigualdad por la matriz $G$ ($G$ es la matriz cuyas columnas son los vectores del sistema $G$), obtenemos la desigualdad $[2 \ 2 \ 3]y \le [2 \ 2 \ 3]y$, la cual tiene como un sistema de generadores a $H = \{e^1, e^2, e^3\}$. Los vectores $Gh^1, Gh^2$ y $Gh^3$ forman un sistema de generadores del conjunto solución del sistema homogéneo. Luego el poliedro max plus es $\mathcal{P} = \text{co}(\{(e \epsilon)^T\}) \oplus \text{cone}(\{(e \epsilon)^T, (e 1)^T\})$.

## 2.4. Control por invarianza en max plus

El enfoque geométrico en la teoría de los sistemas dinámicos lineales ha proporcionado soluciones a muchos problemas de control (Wonham, 1985), lo que ha motivado el intento de extender el enfoque geométrico y en particular el concepto de subespacio $(A, B)$-invariante controlables en la teoría de sistemas dinámicos lineales sobre el semi-anillo max plus, (Katz, 2007).

**Definición 2.4.** Consideremos el sistema descrito por (1).

(a) Un cono max plus $\mathcal{X} \subset \mathbb{R}_{\max}^n$ es $(A, B)$-invariante o inviante controlable si $A\mathcal{X} \subset \mathcal{X} \ominus \text{Im } B$, donde $\mathcal{X} \ominus \text{Im } B = \{x \in \mathbb{R}_{\max}^n | \exists b \in \text{Im } B, x \oplus b \in \mathcal{X}\}$.
(b) Un cono max plus $\mathcal{X} \subset \mathbb{R}_{\max}^n$ es invariante por retroalimentación de estado, si existe una matriz $F \in \mathbb{R}_{\max}^{q \times n}$ tal que el cono max plus $\mathcal{X}$ sea invariante por el operador $A \oplus BF: (A \oplus BF)\mathcal{X} \subset \mathcal{X}$.

Desde el punto de vista dinámico, dado el sistema (1), y un cono max plus $\mathcal{X} \subset \mathbb{R}_{\max}^n$ diremos que:

(a) $\mathcal{X}$ es (A, B)-invariante o invariante controlable si para cada condición inicial $x(1)$ en $\mathcal{X}$, existe un control $u(k)$ tal que la solución del sistema (1) satisface que $x(k) \in \mathcal{X}$, para $k \ge 1$.

(b) $\mathcal{X}$ es invariante por retroalimentación de estado, si existe una retroalimentación $u(k) = Fx(k-1)$, donde $F \in \mathbb{R}_{\max}^{q \times n}$ tal que cada trayectoria del sistema en lazo cerrado, $x(k) = (A \oplus BF)x(k-1)$, esta completamente contenida en $\mathcal{X}$ cuando su estado inicial este en $\mathcal{X}$.

Obviamente, todo cono max plus invariante por retroalimentación de estado es en particular (A, B)-invariante. Esta propiedad es una consecuencia directa de la definición.

La síntesis de una ley de control dentro del enfoque geométrico en la teoría de sistemas dinámicos lineales constituye dos etapas fundamentales: encontrar un cono max plus (A, B)-invariante y una matriz de control $F$. En el caso del semi-anillo $\mathbb{Z}_{max} = (\mathbb{Z} \cup \{-\infty\}, \text{máx}, +)$, el cálculo del máximo cono max plus (A, B)-invariante contenido en una especificación dada a el sistema, depende de la convergencia de una secuencia no decreciente de cono max plus definida en términos del algoritmo clásico de punto fijo extendido al caso max plus. Desafortunadamente la secuencia no necesariamente converge en un número finito de pasos, esta dificultad viene del hecho que $\mathbb{Z}_{max}^n$ no es Artiniano. Sin embargo, la secuencia se estabiliza bajo algunas condiciones de finitud, limitando el estudio de esta variedad de problemas a una familia particular de cono max plus con volumen finito en $\mathbb{Z}_{max}^n$, ver (Katz, 2007) para más detalles.

En la Sección 4, el problema de satisfacer las restricciones temporales se formula en términos de una especificación que es un cono max plus contenido en $\mathbb{R}_{\max}^n$, definida por la imagen de la estrella de Kleene de una matriz $C$, que tiene entradas en $\mathbb{R}_{\max}$. Dicha especificación resulta ser un cono max plus (A, B)-invariante, evitándonos la dificultad que se presenta en la primera etapa de la síntesis de una ley de control, como lo es el cálculo del máximo cono max plus (A, B)-invariante contenido en la especificación dada.

### 3. GETs como modelos max plus lineales

Los grafos de eventos definen una subclase de las redes de Petri, donde cada nodo lugar tiene exactamente un nodo transición de entrada y un nodo transición de salida. Una importante propiedad de los grafos de eventos, es que para cualquier circuito, el número de marcas es constante, por tanto, si todos los circuitos son no vacíos, el grafo de evento es vivo, (Murata, 1989).

Un GET es obtenido asociando retardos a los nodos lugares o a los nodos transiciones de un grafo de eventos dado, con peo de arcos igual a 1. Un nodo transición es habilitado si cada

nodo lugar de entrada al nodo transición contiene al menos una marca. El disparo de un nodo transición habilitado remueve de cada nodo lugar anterior a dicho nodo transición una marca y agrega a cada nodo lugar posterior al nodo transición una marca. Los retardos o tiempos de espera en cada nodo lugar significan que las marcas deben esperar al menos este tiempo en el nodo lugar antes de contribuir a habilitar el disparo del nodo transición de salida. Sin pérdidas de generalidad supongamos que los tiempos de espera son asociados solamente a los nodos lugares, y los tiempos de disparo de los nodos transiciones son instantáneos después de ser habilitados. El modo de evolución considerado para GETs es el tiempo más rápido de funcionamiento, ver (Cohen, 2001). Este tipo de grafo permite modelar SED max plus lineales.

#### 3.1. Ecuación de estado

Consideremos $\mathcal{G}$ un GET con $\mathcal{L}$ el conjunto de nodos lugares y $\mathcal{T}$ el conjunto de nodos transiciones. Sean $t_1^u, \dots, t_q^u$ los nodos transiciones que no tienen algún nodo lugar de entrada asociado, estos nodos transiciones son llamados nodos transiciones fuente. Sean $t_1, \dots, t_n$ los nodos transiciones que tienen al menos un nodo lugar de entrada, nodos transiciones internos. Acá consideraremos que los nodos lugares que siguen de unndo transición fuente no poseen marcas iniciales. Para $t_i, t_j \in \mathcal{T}$, el único nodo lugar entre $t_j$ y $t_i$ es $p_{ij}$, si existe, su retraso correspondiente es denotado por $\tau_{ij}$ y su marcación inicial es denotada por $m_{ij}$. Un camino $\alpha$ desde el nodo transición $t_s$ al nodo transición $t_i$ es una secuencia de nodos transiciones y nodos lugares, de la forma $t_s, p_{k_1s}, t_{k_1}, \dots, p_{ik_j}, t_i$, donde $p_{k_1s}, \dots, p_{ik_j}$ son nodos lugares de $\mathcal{L}$ y $t_s, t_{k_1}, \dots, t_{k_i}, t_i$ son nodos transiciones de $\mathcal{T}$. Denotamos por $m_\alpha$, la suma de las marcas a lo largo del camino $\alpha$, esto es: $m_\alpha = m_{k_1s} \otimes \dots \otimes m_{ik_j}$. Un nodo transición $t_j$ se dice que es controlable si existe un camino desde un nodo transición $t_s^u$ al nodo transición $t_j$. Supongamos que las marcas iniciales del nodo lugar $p_{ij}$ están disponibles en un tiempo $\omega_j(k)$, $\omega_j(k) \ge 0$, estos tiempos iniciales no pueden exceder el tiempo de espera $\tau_{ij}$ asociado al nodo lugar $p_{ij}: \omega_j(k) \le \tau_{ij}, j = 1, \dots, |\mathcal{L}|$, $1 \le k \le m_{ij}$. (Puede ocurrir que las marcas del marcado inicial estén listas para usar en tiempo $-\infty$, en este caso se habla entonces de condiciones iniciales canónicas (Baccelli et al., 1992)). Denotamos por $\bullet t_i$ el conjunto de los nodos lugares de entrada al nodo transición $t_i$, y $\bullet p_{ij}$ el conjunto de nodos transiciones de entrada al nodo lugar $p_{ij}$, el cual es un conjunto unitario.

Para representar el comportamiento dinámico de $\mathcal{G}$, definamos los tiempos asociados con cada nodo transición: $u_j(k)$, $k \ge 1$, se interpreta como el instante en el cual ocurrirá el k-ésimo disparo del nodo transición $t_j^u$, debido a alguna acción externa, para $j = 1, \dots, q$. Las variables de estado $z_i(k)$, $i = 1, \dots, |\mathcal{L}|$, con $k \ge 1$ representan el instante en el cual el nodo transición $t_i$ es disparado para el k-ésimo tiempo. Desde el inicio de la evolución del GET, los disparos sucesivos de un nodo transición son numerados de manera secuencial, a partir de un origen universal, generalmente cero, aunque podría ser negativo. Luego, la función $k \to z_i(k)$ es no decreciente, debido a que varios disparos pueden ocurrir simultáneamente, ver (Cohen, 2001).
Debido a la dinámica del GET, el k-ésimo disparo, $k \ge 1$, del nodo transición $t_i$ ocurre cuando, para todo $j$ tal que $p_{ij} \in \bullet t_i$, la k-ésima marca de $p_{ij}$ contribuya a habilitar $t_i$.

Para $k > m_{ij}$, esta k-ésima marca es producida por el $(k-m_{ij})$ disparo del nodo transición $t_j$, con $t_j \in \bullet p_{ij}$, note que $t_j$ puede ser un nodo transición de control, $t_j^u$, así que el instante cuando esta marca contribuye a habilitar $t_i$ es, $\tau_{ij} \otimes z_j(k-m_{ij}) \circ \tau_{ij} \otimes u_j(k)$. Por lo tanto;

$$z_i(k) = \max_{j | p_{ij} \in \bullet t_i \lor t_j^u \in \bullet p_{ij}} (\tau_{ij} + z_j(k - m_{ij}), \tau_{ij} + u_j(k)), \quad (6)$$

$$\text{para} \qquad k \ge (\max_{j | p_{ij} \in \bullet t_i} m_{ij}) + 1.$$

Para $k \le m_{ij}$, este evento toma lugar en el instante $\omega_j(k)$, que corresponde al instante cuando la k-ésima marca inicial del nodo lugar $p_{ij}$ contribuye a habilitar el nodo transición $t_i$, similarmente al caso anterior, tenemos que los tiempos $z_i(k)$ satisfacen las ecuaciones de evolución siguientes:

$$z_i(k) = \max_{\substack{j | p_{ij} \in \bullet t_i \lor t_j^u \in \bullet p_{ij}, \\ m_{ij} < k}} (\tau_{ij} + z_j(k - m_{ij}), \tau_{ij} + u_j(k)) \\ \oplus \max_{j | p_{ij} \in \bullet t_i, m_{ij} \ge k} (\omega_j(k)), \qquad (7)$$

$$\text{para} \qquad 1 \le k \le \max_{j | p_{ij} \in \bullet t_i} m_{ij}.$$

**Proposición 3.1.** Si un GET es vivo, y los tiempos iniciales $\omega_j(k)$ son no decrecientes y no negativos para $j = 1, \dots, |\mathcal{L}|$ y $1 \le k \le m_{ij}$, entonces $z_i(k)$, con $k \ge 1$ es no decreciente y no negativa para toda entrada de control $u(k)$ no decreciente y no negativa.

*Demostración.* Es claro de (6) y (7) que si los tiempos $\omega_j(k)$ en los cuales las marcas iniciales del nodo lugar $p_{ij}$ están disponibles, son ordenados en forma no decreciente para $j$ tal que $m_{ij} \ge 1$, esto es: $\omega_j(1) \le \omega_j(2) \le \dots \le \omega_j(m_{ij})$ y además no exceden el tiempo de espera $\tau_{ij}$ asociado al nodo lugar $p_{ij}$: $\omega_j(k) \le \tau_{ij}$, $j = 1, \dots, |\mathcal{L}|$, $1 \le k \le m_{ij}$, y $\omega_j(1) \ge 0$, entonces podemos garantizar que la secuencia $z_i(k)$ es no decreciente para toda entrada $u$ no decreciente y no negativa: $u(k+1) \ge u(k)$, $u(k) \ge 0$, para todo $k \ge 1$.

Por otro lado, veamos cuando $z_i(k)$ es no negativa para $k \ge 1$. Tomando en cuenta que la secuencia $z_i(k)$ es no decreciente, basta ver que $z_i(1) \ge 0$. Si existe al menos una marca en algún nodo lugar de entrada del nodo transición considerado $t_i$, digamos $p_{ij}$, entonces de (7), deducimos que $z_i(1) \ge \omega_j(1) \ge 0$, luego los $z_i(k)$ toman valores no negativos. En caso contrario, como no hay marcas en los nodos lugares de entrada al nodo transición $t_i$, podemos afirmar a partir de (6):

$$z_i(1) \ge \tau_{ij} + z_j(1) \quad \text{ó} \quad z_i(1) \ge \tau_{ij} + u_j(1), \qquad (8)$$

para cada nodo lugar de entrada $p_{ij}$ al nodo transición $t_i$, y cada nodo transición de entrada $t_j$ al nodo lugar $p_{ij}$. Luego iterando (8), deducimos que $z_i(1)$ es no negativo, si existe un camino en el grafo desde un nodo transición de control o un camino desde el nodo transición de entrada de un nodo lugar marcado hasta el nodo transición $t_i$, esto debido a que $z_i(1)$ resulta ser mayor o igual a la suma de todos los retardos presentes en dicho camino.

Por tanto si $j$ es asociado a un nodo transición de control o al nodo transición de entrada a un nodo lugar marcado, de donde sale un camino hasta $t_i$, tenemos que $z_i(1) \ge u_j(1)$ ó $z_i(1) \ge \omega_j(1)$, y en consecuencia la secuencia $z_i(k)$ es no negativa para $k \ge 1$. □

De las ecuaciones (6) y (7) podemos expresar el comportamiento dinámico del GET en forma matricial como sigue:

$$z(k) = \bigoplus_{m \ge 0} [\bar{A}_m \otimes z(k-m) \oplus \bar{B} \otimes u(k)] \oplus v(k), \quad (9) \\ \text{con } M = \max_{p_{ij} \in \mathcal{L}} m_{ij}, \quad v_j(k) = \max_{j | p_{ij} \in \bullet t_i, m_{ij} \ge k} (\omega_j(k)),$$

donde $v_j(k)$ es definido para $k = 1, \dots, M$ y es igual a $\epsilon$ en cualquier otro caso. La secuencia $z_i(k) = \epsilon$ y $u_j(k) = \epsilon$ para toda $k \le 0$. La matriz $\bar{A}_m \in \mathbb{R}_{\max}^{n \times n}$, su entrada $\bar{A}_{m_{ij}}$ es igual a $\tau_{ij}$, si existe un nodo lugar $p_{ij}$ conteniendo $m_{ij}$ marcas, de lo contrario $\bar{A}_{m_{ij}}$ es igual a $\epsilon$. Similarmente $\bar{B} \in \mathbb{R}_{\max}^{n \times q}$ corresponde a los retrasos de los nodos lugares seguidos de los nodos transiciones fuentes.

Para la transformación de esta ecuación en una forma canónica, la primera etapa tiene como objetivo la eliminación de la parte implícita $\bar{A}_0 \otimes z(k)$. Por definición de $\bar{A}_0$, hay un número de nodos transiciones internos tal que $\bar{A}_0$ puede ser escrita en forma triangular inferior, y se garantiza que $\bar{A}_0^*$ esta bien definida, $(\bar{A}_0^*)_{ij} < +\infty$. Luego (9) se expresa como siguiente ecuación explícito:

$$z(k) = \bigoplus_{m>0} [\bar{A}_0^* \bar{A}_m \otimes z(k-m) \oplus \bar{A}_0^* \bar{B} \otimes u(k)] \oplus \bar{A}_0^* v(k), \quad (10)$$

La siguiente etapa en la manipulación de esta ecuación tiene como objetivo la obtención de la forma matricial canónica, la cual es obtenida extendiendo la dimensión del vector de estado. Esta etapa es clásica en la teoría de sistemas y no será necesario describir los detalles aquí, ver (Cohen et al., 1999). No introducimos una nueva notación para la dimensión del vector de estado extendido, denotado por $x$.

**Teorema 3.1.** El comportamiento dinámico del GET con tiempo más rápido de funcionamiento es dado por el modelo lineal:

$$x(k) = A \otimes x(k-1) \oplus B \otimes u(k), \quad k \ge 2, \qquad (11)$$

con condición inicial

$$x(1) = B \otimes u(1) \oplus w,$$

donde $w$ es un vector que depende de los tiempos $\omega_i(k)$ de evolución de las marcas iniciales, (ver (9)). Las matrices $A \in \mathbb{R}_{\max}^{n \times n}$ y $B \in \mathbb{R}_{\max}^{n \times q}$, $x(k) \in \mathbb{R}_{\max}^n$ es el vector de estado, $u(k) \in \mathbb{R}_{\max}^q$ es el vector de entrada de control, ambos definidos para $k \ge 1$.

## 3.2. Condiciones iniciales admisibles para grafos de eventos temporizados

Como vimos en la parte previa, cada evolución posible de un GET satisface el sistema lineal (11), pero la inversa no es necesariamente cierta. Nosotros estamos interesados en que el comportamiento dinámico del GET coincida con las soluciones no decrecientes del sistema (1). Para ello es necesario tomar en
cuenta las condiciones iniciales apropiadas, puesto que puede
ocurrir que a partir de un estado inicial y una entrada de con-
trol no decreciente, la secuencia x(k) resulte ser decreciente. A
continuación, proveemos una caracterización geométrica de las
condiciones iniciales admisible de sistemas lineales max plus.

**Definición 3.1.** Dado el sistema (11) sobre $\mathbb{R}_{\max}^n$, diremos que la condición inicial $w$ es admisible, si para toda secuencia de entrada no decreciente $u(k)$, el estado $x(k)$ es no decreciente también.

**Teorema 3.2.** Dado el sistema (11) sobre $\mathbb{R}_{\max}^n$, el conjunto de condiciones iniciales admisibles, $\mathcal{W}$ es definido por

$$
\mathcal{W} = \{w \in \mathbb{R}_{\max}^{+n} \mid Aw \geq w\}, \quad (12)
$$

donde $\mathbb{R}_{\max}^{+n} := \mathbb{R}^{+} \cup \{-\infty\}$.

Demostración. Queremos caracterizar el conjunto de condiciones iniciales $w$, las cuales conduzan a soluciones no decrecientes, esto es, $x(k+1) \geq x(k) = Ax(k-1) \oplus Bu(k)$, para $k \geq 1$ y toda entrada de control $u$ no decreciente.

Supongamos que $w$ es una condición inicial admisible, luego en particular se cumple que la solución correspondiente a la entrada de control $u(k) = -\infty$, es no decreciente y esta solución se escribe $x(1) = w$, $x(2) = Ax(1) = Aw, \dots$, y como $x(k+1) \ge x(k)$ para $k \ge 1$, se tiene que $x(2) = Aw \ge x(1) = w$, por tanto $Aw \ge w$.

Reciprocamente, sea $w \in \mathcal{W}$, luego $Aw \ge w$, y en consecuencia para toda entrada de control $u$ no decreciente se cumple en particular que $u(2) \ge u(1)$, así $Bu(2) \ge Bu(1)$, y por tanto $x(2) = Ax(1) \oplus Bu(2) = A(Bu(1) \oplus w) \oplus Bu(2) = ABu(1) \oplus Aw \oplus Bu(2) \ge Aw \oplus Bu(2) \ge w \oplus Bu(1) = x(1)$, en forma más general tenemos:

$$
x(k + 1) = Ax(k) \oplus Bu(k + 1) = A^k w \oplus \bigoplus_{i=1}^{k+1} A^{k+1-i} Bu(i),
$$

como $Aw \ge w$, se tiene que $A^k w \ge A^{k-1} w$, y por tanto para toda
entrada de control $u(k)$ no decreciente se cumple lo siguiente:

$$
\begin{align*}
x(k+1) &\ge A^{k-1}w \oplus \bigoplus_{i=1}^{k+1} A^{k+1-i}Bu(i), \\
&\ge A^{k-1}w \oplus \bigoplus_{i=2}^{k+1} A^{k+1-i}Bu(i), \\
&\ge A^{k-1}w \oplus \bigoplus_{i=2}^{k+1} A^{k-i}Bu(i-1), \quad u(i) \ge u(i-1), \\
&= A^{k-1}w \oplus \bigoplus_{i=1}^{k} A^{k-i}Bu(i), \\
&= x(k). \quad \square
\end{align*}
$$

Por tanto, las evoluciones posible de un GET coinciden exac-
tamente con las trayectorias del sistema lineal (1) en $\mathbb{R}_{\max}$ cuan-
do el conjunto de condiciones iniciales es limitado a satisfacer
la condición $w \in \mathcal{W}$. Esta caracterización será tomada en cuen-
ta en la Proposición 4.2 y el Corolario 4.3.

4. Problema de control con restricciones temporales

En esta sección el problema de control es presentado y pro-
ponemos condiciones suficientes para la existencia y el cálculo
de un controlador.

4.1. Restricciones Temporales

Las temporizaciones asociadas con nodos lugares en un GET
corresponden a un tiempo mínimo de espera de las marcas en
el nodo lugar. Sin embargo, las marcas pueden permanecer más
del tiempo mínimo en el nodo lugar. Para un nodo lugar con res-
tricción de tiempo, un tiempo de estadía máximo es fijado. Esta
limitación de un tiempo máximo de estadía aparece como una
restricción adicional que debe ser respetada. Por tanto, un inter-
valo de tiempo [$\tau_z, \tau_z^{max}$] es asociado a este nodo lugar, donde
$\tau_z$ es el tiempo mínimo de estadía y $\tau_z^{max}$ es el tiempo máximo,
(ver Fig. 1).

<figure><img src="image_2.png" /><figcaption>Figura 1: Restricción Temporal</figcaption></figure>

Esta restricción de tiempo es expresada por la siguiente de-
sigualdad:

$$
x_z'(k) \leq \tau_z^{\text{max}} \otimes x_z(k - m_z), \quad \forall k > m_z. \quad (13)
$$

**Definición 4.1.** Dado un GET modelado por el sistema max plus lineal (1), y sujeto a un conjunto de restricciones temporales, se define la matriz $C \in \mathbb{R}_{\max}^{n \times n}$ asociada a estas restricciones por:

$$
C_{zz'} = \begin{cases} -\tau_z^{\text{max}} & \text{si hay una restricción temporal entre } t_z \text{ y } t_{z'} \\ \epsilon & \text{en otro caso.} \end{cases} \tag{14}
$$

Tomando en cuenta la Proposición 2.1, se cumple el si-
guiente corolario.

**Corolario 4.1.** El conjunto de vectores de estados que satisfacen las restricciones temporales con $m_z = 0$, es igual al cono max plus definido por la imagen de la estrella de Kleene de la matriz $C$, Im $C^*$, cuando $C^*$ exista. Esto es Im $C^* = \{x \in \mathbb{R}_{\max}^n | C \otimes x \le x\}$.

4.2. Problema de control

Consideremos un GET sin circuitos sin marcas iniciales,
con $q$ nodos transiciones fuentes, denotados $t_i^u, i = 1, \dots, q$,
($q \ge 1$) y con $Z$ nodos lugares con restricciones temporales.
Estos nodos lugares son denotados por $p_{z_i}$, para $i = 1, \dots, Z$.
Para cada nodo lugar $p_{z_i}$, denotemos $m_{z_i}, \tau_{z_i}$ y $\tau_{z_i}^{\text{max}}$ la marca-
ción inicial y los retardos mínimo y máximo, respectivamente.
Además $t_{z_i}$ y $t_{z'_i}$ denotan respectivamente el nodo transición de
entrada y el nodo transición de salida del nodo lugar $p_{z_i}$, para
$i = 1, \dots, Z$. Sean $x_{z_i}$ y $x_{z'_i}$ los tiempos de disparo correspon-
dientes a los nodos transiciones $t_{z_i}$ y $t_{z'_i}$ respectivamente, y sea
$m_{\alpha_i}$ la marcación acumulada a lo largo del camino $\alpha_i$, definido
desde algún nodo transición de entrada hasta el nodo transición $t_{zi}$.

Supongamos que todos los nodos lugares con restricciones temporales tienen marcación inicial igual a cero, esto es, $m_{zi} = 0$ para todo $i = 1, \dots, Z$. Luego las restricciones temporales serán expresadas como sigue;

$$x'_{zi}(k) \le \tau_{zi}^{max} \otimes x_{zi}(k), \quad k \ge 1. \qquad (15)$$

El comportamiento dinámico del GET es expresado por el modelo max plus lineal:

$$x(k) = A \otimes x(k-1) \oplus B \otimes u(k), \quad \text{para } k \ge 2. \qquad (16)$$

con condiciones iniciales $x(1) = Bu(1) \oplus w$, donde $A \in \mathbb{R}_{\max}^{n \times n}$ y $B \in \mathbb{R}_{\max}^{n \times q}$, $x(k) \in \mathbb{R}_{\max}^n$ es el vector de estado, $u(k) \in \mathbb{R}_{\max}^q$ es el vector de entrada de control, ambos definidos para $k \ge 1$, y $w$ es un vector que depende de los tiempos de evolución de las marcas iniciales. Asumimos que las condiciones iniciales son admisibles, esto es $w \in \mathcal{W}$, donde $\mathcal{W}$ es definido por (12).

Definamos el cono max plus:

$$\mathcal{D} = \{v \in \mathbb{R}_{\max}^q | CBv \le Bv\}. \qquad (17)$$

Note que $\mathcal{D}$ es no vacío, ya que contiene al menos la solución trivial.

Bajo las condiciones anteriores, nuestro problema de control se define como sigue. Dado el sistema max plus lineal (16), y un conjunto de restricciones temporales de la forma (15), buscamos una ley de control que asegure que el estado del sistema evoluciona satisfaciendo la condición $C \otimes x(k) \le x(k)$ para $k \ge 1$.

Inspirados por el caso de sistemas sobre cuerpos, y siguiendo la literatura sobre sistemas sobre semi-anillos, el enfoque propuesto consiste en buscar una ley de control por retroalimentación de estado, definida en términos de una matriz F con la relación $u(k) = Fx(k-1)$ para $k \ge 2$, y para $k = 1$, al contrario de sistemas sobre un cuerpo, esta relación debe ser completada para definir el valor inicial del control, $u(1)$, tal que garantice que $x(k) \in \text{Im } C^*$ para $k \ge 1$.

Con este control, usando la ecuación (16), el sistema en lazo cerrado se expresa como:

$$x(k) = (A \oplus B \otimes F) \otimes x(k-1), \quad \forall k \ge 2, \qquad (18)$$

$$\text{con } x(1) = B \otimes u(1) \oplus w.$$

Para abordar nuestro problema requerimos de los siguientes fundamentos.

**Proposición 4.1.** Dadas dos matrices $A \in \mathbb{R}_{\max}^{n \times n}$ y $B \in \mathbb{R}_{\max}^{n \times q}$, y un cono max plus de $\mathbb{R}_{\max}^n$, definido por la imagen de la estrella de Kleene de una matriz C. Los siguientes enunciados son equivalentes:

(i) $\text{Im } A \subset \text{Im } C^* \ominus \text{Im } B$,

(ii) Existe $F \in \mathbb{R}_{\max}^{q \times n}$ tal que $\text{Im } (A \oplus B \otimes F) \subset \text{Im } C^*$,

(iii) Existe $F \in \mathbb{R}_{\max}^{q \times n}$ tal que $C \otimes (A \oplus B \otimes F) \le A \oplus B \otimes F$.

*Demostración.* Sea $\{e^1, \dots, e^n\}$ la base canónica de $\mathbb{R}_{\max}^n$ y $C \in \mathbb{R}_{\max}^{n \times n}$ la matriz dada que define a $\text{Im } C^*$. Supongamos que $\text{Im } A \subset \text{Im } C^* \ominus \text{Im } B$, luego $Ae^i \in \text{Im } C^* \ominus \text{Im } B$, por lo que existe

$b \in \text{Im } B$ tal que $Ae^i \oplus b \in \text{Im } C^*$, lo que significa que para $i = 1, \dots, n$, existen vectores $u^i \in \mathbb{R}_{\max}^q$ tal que $Ae^i \oplus Bu^i \in \text{Im } C^*$. Luego definiendo una retroalimentación de estado $F$ por $F \otimes e^i = u^i$ se garantiza que $\text{Im } (A \oplus B \otimes F) \subset \text{Im } C^*$. Claramente (ii) implica (iii) por Proposición 2.1. Finalmente si existe $F$ tal que $C \otimes (A \oplus B \otimes F)e^i \le (A \oplus B \otimes F)e^i$, se sigue que existe $b = BFe^i$ tal que $Ae^i \oplus b \in \text{Im } C^*$, y en consecuencia $Ae^i \in \text{Im } C^* \ominus \text{Im } B$, con lo cual se concluye la prueba.

□

La Proposición 4.1 permite, para los cono max plus definidos por la imagen de la estrella de Kleene de una matriz C, estudiar propiedades geométricas que implican las propiedades de (A,B)-invarianza e invarianza por retroalimentación de estado. Esta clase particular de conos max plus, aparece como la especificación dada para el espacio de estado de un sistema de la forma (16), y si estos conos max plus satisfacen las propiedades equivalentes de la Proposición 4.1, entonces, desde el punto de vista dinámico se tiene que a partir de cualquier estado del sistema, es posible encontrar una ley de control por retroalimentación de estado que garantice que la trayectoria en lazo cerrado del sistema se mantenga incluida en el cono max plus, lo cual resulta útil en muchos problemas prácticos.

Entonces una solución a nuestro problema de control existe si y sólo si la desigualdad $C(A \oplus BF)x(k) \le (A \oplus BF)x(k)$ se satisface para $k \ge 1$, esto es $Cx(k+1) \le x(k+1)$; y además la condición inicial $x(1)$ esta en $\text{Im } C^*$. Por tanto, podemos obtener condiciones que aseguren la existencia y el cálculo de una solución si $C \otimes (A \oplus B \otimes F) \le A \oplus B \otimes F$ se cumple y $x(1) \in \text{Im } C^*$.

El lema siguiente nos permitirá demostrar nuestro resultado principal.

**Definición 4.2.** Diremos que las restricciones temporales son admisibles al control si toda fila nula de la matriz B, implica que la fila correspondiente de la matriz C es nula.

Esta definición equivale a decir que para cada restricción temporal $i = 1, \dots, Z$, existe un $l_i \in \tilde{q}$ tal que $B_{zi l_i} \neq \epsilon$.

**Lema 4.1.** Si las restricciones temporales son admisibles al control, siempre es posible encontrar una matriz F tal que se cumpla $CA \le BF$.

*Demostración.* Esta propiedad se debe al hecho de que si las restricciones temporales son admisibles al control, existe para cada $i = 1, \dots, Z$, un $l_i \in \tilde{q}$ tal que $B_{zi l_i} \neq \epsilon$, y por tanto se puede escoger $F_{li r} \ge A'_{zi r} - \tau_{zi}^{max} - B_{zi l_i}$ tal que $(CA)_{zi r} \le (BF)_{zi r}$. En efecto:

$$ \begin{align*} (BF)_{zi r} &\ge \bigoplus_{k=1}^{q} B_{zi k} F_{kr} \ge B_{zi l_i} F_{li r}, \\ &\ge B_{zi l_i} + A'_{zi r} - \tau_{zi}^{max} - B_{zi l_i} = A'_{zi r} - \tau_{zi}^{max}, \\ &\qquad = (CA)_{zi r}. \quad \square \end{align*} $$

En el siguiente teorema damos condiciones para la existencia de una ley de control por retroalimentación de estado que asegura la satisfacción de las restricciones temporales definidas por (15).

**Teorema 4.1.** Dado el cono max plus $\mathcal{D}$ definido por (17). Si las restricciones temporales son admisibles al control y existe
$v \in \mathcal{D}$ tal que $\sup(v) = \bar{q}$, entonces, existe una matriz $F \in \mathbb{R}_{\max}^{q \times n}$ tal que $\mathrm{Im}(A \oplus BF) \subset \mathrm{Im} C^*$.

**Demonstración.** Para probar el teorema, debido a la Proposición 4.1, es suficiente mostrar que existe una matriz $F \in \mathbb{R}_{\max}^{q \times n}$ tal que las siguientes desigualdades se cumplen,

$$ CA \leq BF \quad \text{y} \quad CBF \leq BF. \tag{19} $$

En efecto, note en primer lugar que si existe $v$ en $\mathcal{D}$, se sigue que $CBv \leq Bv$ se satisface.

Por otro lado, debido al Lema 4.1, es posible encontrar una matriz $F$ tal que $CA \leq BF$, con $F_{lr} \geq A'_{z'_l r} - \tau_{z_l}^{\max} - B_{z_l l_i}$. Además como todos los elementos del vector solución $v$ son no nulos, en particular $v_{l_i}$ es no nulo, tenemos que existe $\alpha$ tal que $\alpha + v_{l_i} \geq A'_{z'_l r} - \tau_{z_l}^{\max} - B_{z_l l_i}$. Luego, podemos escoger $F_{kr} = \alpha_r + v_k$ con $\alpha_{l_i} \geq A'_{z'_l r} - \tau_{z_l}^{\max} - B_{z_l l_i} - v_{l_i}$, tal que las desigualdades expresadas en (19) se cumplan, con lo cual concluye la prueba. $\square$

**Observación 4.1.** Note que la prueba que precede es usada para construir una matriz de control $F$ no nula tal que sus vectores columnas verifiquen:

$$ \left[ \begin{array}{c|c|c} B'_{z'_1} & \otimes & F_{1r} \\ \vdots & \vdots & \vdots \\ B'_{z'_Z} & \otimes & F_{qr} \end{array} \right] \oplus \left[ \begin{array}{c|c} A'_{z'_l r} & \otimes \\ \vdots & \vdots \\ A'_{z'_Z r} & \otimes \end{array} \right] \le \left[ \begin{array}{c|c} \tau_{z_1}^{\max} \otimes B_{z_1} & \otimes \\ \vdots & \vdots \\ \tau_{z_Z}^{\max} \otimes B_{z_Z} & \otimes \end{array} \right] \left[ \begin{array}{c|c} F_{1r} & \otimes \\ \vdots & \vdots \\ F_{qr} & \otimes \end{array} \right]. \tag{20} $$

La matriz $F$ puede contener algunas columnas nulas, ya que el vector nulo, también satisface (20). Este hecho se puede presentar por ejemplo, cuando $A'_{z'_l r} = \epsilon$, para toda $i = 1, \dots, Z$, luego $F_r = \epsilon$.

La condición $C(A \oplus BF) \leq A \oplus BF$ permite constatar que una retroalimentación de estado adecuado para que $x(k)$ se mantenga en $\mathrm{Im} C^*$, para $k \geq 2$ puede ser tal que satisfaga (20), evidentemente la solución $F$ no es necesariamente única, debido a que (20) define un poliedro max plus. Un sistema de generadores para este conjunto solución, puede ser explícitamente calculado usando el procedimiento descrito en la sección 2.3, debido a (Allamigeon et al, 2010), y en consecuencia siempre es posible conocer todas las leyes de control que pueden ser aplicadas para satisfacer las restricciones temporales para $k \geq 2$.

Además, si bien es cierto que la solución particular $F$ encontrada en el Teorema 4.1, no es óptima desde el punto de vista práctico, puesto que la matriz $F$ posee columnas con todas las entradas no nulas, es posible a partir de un sistema generador de (20), construir otras soluciones más sencillas que permitan sintetizar la ley de control considerando criterios adicionales. Una solución posiblemente más sencilla a realizar es tal que cada columna $F_r$ tenga a lo más una entrada no nula, este hecho es posible, si para los $i$ tales que $A'_{z'_l r} \neq \epsilon$, las filas de la matriz $B$ asociadas a los nodos transiciones de entrada de las restricciones $i$, satisfacen que la componente $B_{z_l i}$ es no nula, luego se tendría que $F_{lr} \neq \epsilon$ y $F_{kr} = \epsilon$ en cualquier otro caso. Una propiedad muy importante en aplicaciones es la causalidad de la ley de control, que permite su implementación en línea.

**Definición 4.3.** Se dice que una matriz $F$ es causal si $F \in (\mathbb{R}^+ \cup \{-\infty\})^{q \times n}$.

**Corolario 4.2.** Bajo las condiciones del Teorema 4.1, se puede escoger la matriz $F$ en el conjunto de matrices causales tal que $\mathrm{Im}(A \oplus BF) \subset \mathrm{Im} C^*$ se cumpla.

Por otro lado, se puede ver que las condiciones del Teorema 4.1, son suficientes para la existencia de un control que garantice la satisfacción de las restricciones expresadas en (15), para $k \geq 2$. Para el disparo inicial, $k = 1$, se debe completar la ley de control de tal que la condición inicial $x(1)$ esté en $\mathrm{Im} C^*$, considerando un vector $u(1)$ que satisfaga (21)-(22), esto es;

$$ \bigoplus_{k=1}^{q} B'_{z'_k} u_k(1) \le \bigoplus_{k=1}^{q} \tau_{z_k}^{\max} \otimes B_{z_k} u_k(1), \tag{21} $$

$$ w'_{z'_i} \le \bigoplus_{k=1}^{q} \tau_{z_k}^{\max} \otimes B_{z_k} u_k(1). \tag{22} $$

La existencia de esta ley de control viene en parte de las hipótesis del Teorema 4.1 como veremos en la siguiente proposición, y además se muestra que la condición inicial $x(1)$ está en el cono max plus $\mathrm{Im} C^*$, independientemente del vector $w$ tomado en el conjunto de condiciones iniciales admisibles definido en (12).

**Proposición 4.2.** Si las hipótesis del Teorema 4.1 son satisfechas y además las condiciones iniciales son admisibles, entonces $x(1) \in \mathrm{Im} C^*$.

**Demonstración.** En efecto, supongamos que las hipótesis del Teorema 4.1 se cumplen, luego existe una matriz $F \in \mathbb{R}_{\max}^{q \times n}$ tal que (19) se satisface, así para cualquier vector $w$ se cumple desde (19) que $CAw \leq BFW$ y $CBFW \leq BFW$, tomando $u(1) = Fw$ tenemos $CAw \leq Bu(1)$ y $CBu(1) \leq Bu(1)$. Además, considerando que las condiciones iniciales son admisibles, esto es $Aw \geq w$, se tiene que $Cw \leq CAw \leq Bu(1)$. Así se concluye que $Cx(1) = C(Bu(1) \oplus w) = Cw \oplus CBu(1) \leq Bu(1) \leq Bu(1) \oplus w = x(1)$, y por tanto $x(1) \in \mathrm{Im} C^*$. $\square$

En conclusión, la Proposición 4.2 complementa el Teorema 4.1, y hemos llegado a una solución completa del problema de invarianza que procede de las restricciones temporales impuestas a un sistema dinámico max plus lineal.

**Corolario 4.3.** Si las hipótesis del Teorema 4.1 son satisfechas y además las condiciones iniciales son admisibles, entonces existe una retroalimentación de estado definida por $u(k) = Fx(k-1)$, $k \geq 2$, y $u(1) = Fw$, tal que el estado del sistema en lazo cerrado satisface las restricciones, $x(k) \in \mathrm{Im} C^*$, para $k \geq 1$.

## 5. Aplicación a casos de estudio

Para ilustrar una aplicación del enfoque propuesto en este artículo, presentamos dos casos de estudio. El primer caso de corte académico para describir el método y un segundo donde el método propuesto es aplicado a un proceso de la industria de semiconductores.
## 5.1. Primer caso

Consideremos el GET de la figura 2, tomado de (Amari, 2012). Este grafo contiene dos nodos transiciones fuentes modelando los controles $u_1(k)$ y $u_2(k)$ respectivamente. Dos restricciones temporales adicionales son asignadas a los nodos ligares $p_1$ y $p_2$ de este grafo, y son expresadas respectivamente por las desigualdades $x_2(k) \le 1 \otimes x_1(k)$ y $x_3(k) \le 1 \otimes x_2(k)$.

<figure><img src="image_3.png" /><figcaption>Figura 2: GET con dos restricciones temporales en $p_1$ y $p_2$.</figcaption></figure>

Estamos interesados en calcular una matriz de control $F \in \mathbb{R}_{\max}^{2 \times 5}$ tal que garantice que los estados del sistema en lazo cerrado evolucionan satisfaciendo el conjunto de restricciones temporales resumidas en el cono max plus Im $C^*$, esto es $x(k) \in \text{Im } C^*$, para $k \ge 2$, y además describir el conjunto de condiciones iniciales admisibles tal que $x(1) \in \text{Im } C^*$. La matriz $C \in \mathbb{R}_{\max}^{5 \times 5}$ es la matriz asociada a las restricciones temporales satisfaciendo que $C_{12} = C_{23} = -1$ y $C_{ji} = \epsilon$ en cualquier otro caso, y la ecuación de estado asociada con este GET es:

$$x(k) = \begin{bmatrix} \epsilon & \epsilon & \epsilon & \epsilon & \epsilon \\ \epsilon & \epsilon & 1 & \epsilon & 1 \\ \epsilon & \epsilon & 2 & 1 & 2 \\ \epsilon & \epsilon & 5 & 4 & 5 \\ \epsilon & \epsilon & \epsilon & \epsilon & \epsilon \end{bmatrix} \otimes x(k-1) \oplus \begin{bmatrix} e & \epsilon \\ 1 & e \\ 2 & 1 \\ 5 & 4 \\ \epsilon & \epsilon \end{bmatrix} \otimes u(k). \quad (23)$$

Note que las restricciones temporales son admisibles al control, ya que existen $B_{1r} \ne \epsilon$ y $B_{2r} \ne \epsilon$, ver Definición 4.2, luego debido al Teorema 4.1, la existencia de una matriz $F$ tal que la propiedad deseada $\text{Im}(A \oplus \text{BF}) \subset \text{Im} C^*$ se satisfaga, se garantiza si además, el cono max plus $\mathcal{D}$, definido a continuación posee una solución $u$ tal que $\sup(u) = \bar{2}$.

$$\begin{bmatrix} 1 & e \\ 2 & 1 \end{bmatrix} \otimes v \le \begin{bmatrix} 1 & \epsilon \\ 2 & 1 \end{bmatrix} \otimes v. \quad (24)$$

En efecto, aplicando el Método de doble descripción tropical (Allamigeon, 2010), obtenemos para el cono max plus $\mathcal{D}$ el sistema generador $G = \{e^1, (e1)^T\}$, así todo elemento de $\mathcal{D}$ es generado por los elementos de $G$ y por tanto existe por lo menos $u = (e1)^T$ en $\mathcal{D}$ tal que $\sup(u) = \bar{2}$. Por tanto, existe $F$ tal que la propiedad deseada se cumple, y cada columna de la matriz $F$ satisface:

$$\begin{bmatrix} 1 & e \\ 2 & 1 \end{bmatrix} \begin{bmatrix} F_{1r} \\ F_{2r} \end{bmatrix} \oplus \begin{bmatrix} A_{2r} \\ A_{3r} \end{bmatrix} \le \begin{bmatrix} 1 & \epsilon \\ 2 & 1 \end{bmatrix} \begin{bmatrix} F_{1r} \\ F_{2r} \end{bmatrix}. \quad (25)$$

Para calcular $F$, primero para cada $r$, construimos el poliedro tropical $\mathcal{P}_r$ definido como el conjunto solución de (25), luego, podemos representar $\mathcal{P}_r$ como proyecciones de conos max plus de $\mathbb{R}_{\max}^{2+1}$, debido a la Definición 2.3. El cono homogenizado asociado a $\mathcal{P}_r$, es denotado por $\hat{\mathcal{P}}_r$ y definido como el conjunto solución de:

$$\begin{bmatrix} 1 & e & A_{2r} \\ 2 & 1 & A_{3r} \end{bmatrix} \begin{bmatrix} z_1 \\ z_2 \\ z_3 \end{bmatrix} \le \begin{bmatrix} 1 & \epsilon & \epsilon \\ 2 & 1 & \epsilon \end{bmatrix} \begin{bmatrix} z_1 \\ z_2 \\ z_3 \end{bmatrix}. \quad (26)$$

Para construir la matriz $F$ si bien es cierto que basta con conocer por lo menos un elemento de cada $\mathcal{P}_r$, nosotros seremos algo más generales, y para ello buscaremos un sistema de generadores del cono max plus $\hat{\mathcal{P}}_r$, ya que a partir de este sistema podemos encontrar un sistema de generadores del poliedro max plus $\mathcal{P}_r$, y en consecuencia podemos conocer todas las posibles leyes de control que pueden ser aplicadas para satisfacer las restricciones temporales.

Note que las componentes $A_{i1}$ y $A_{i2}$ son todas nulas para $i = 2, 3$, luego basta tomar las columnas $F_1 = F_2 = \epsilon$, ver Observación 4.1. Para $r = 3$, $\mathcal{P}_3 = \text{cone}((e \epsilon)^T, (e 1)^T)$, (ver Ejemplo 2.1). Luego podemos tomar $F_3 = (e \epsilon)^T$. Para $r = 4$, consideremos el sistema (25) y el sistema homogéneo asociado, donde $A_{24} = \epsilon$ y $A_{34} = 1$. Resolviendo la primera desigualdad del sistema homogéneo, un sistema de generadores para este es $G = \{(e \epsilon)^T, (e \epsilon)^T, (e 1)^T\}$. Multiplicando a la derecha y a la izquierda la segunda desigualdad por la matriz $G$ ($G$ es la matriz cuyas columnas son los vectores del sistema $G$), obtenemos la desigualdad $(2 \ 1 \ 2) \le (2 \ \epsilon \ 2)\epsilon$, la cual tiene como un sistema de generadores a $H = \{e^1, e^3, (1 \ 2 \epsilon)^T, (\epsilon 2 \ 1)^T\}$. Los vectores $Gh^1, Gh^2$ y $Gh^3$ forman un sistema de generadores del conjunto solución del sistema homogéneo, $\{e^1, (e 1 \epsilon)^T, (1 \epsilon 2)^T, (1 \ 2 \ 2)^T\}$.

Por tanto $\mathcal{P}_4 = \text{cone}((e \epsilon)^T, (-1 \epsilon)^T) \oplus \text{cone}((e \epsilon)^T, (e 1)^T)$. Un criterio que se puede tomar en cuenta para la elección de un elemento de $\mathcal{P}_4$, es que la matriz $F$ sea causal, ver Corolario 4.2. Así que tomaremos $F_4 = (e \epsilon)^T \oplus (-1 \epsilon)^T = (e \epsilon)^T$. (Otras opciones simples pueden ser $F_4 = (e \epsilon)^T \oplus (-1 \epsilon)^T = (e \epsilon)^T$ o $F_4 = (e \epsilon)^T \oplus (-1 \epsilon)^T = (e 1)^T$), la elección dependerá de los criterios adicionales considerados para sintetizar la ley de control. Para $r = 5$, se procede como antes y se tiene que $\mathcal{P}_5 = \text{cone}((e \epsilon)^T) \oplus \text{cone}((e \epsilon)^T, (e 1)^T)$. Luego podemos tomar $F_5 = (e \epsilon)^T$.

Por tanto, una matriz de control $F$ que satisfaga que la trayectoria del sistema en lazo cerrado se mantenga en $\text{Im } C^*$ para $k \ge 2$ es dada por:

$$F = \begin{bmatrix} \epsilon & \epsilon & e & e & e \\ \epsilon & \epsilon & \epsilon & \epsilon & \epsilon \end{bmatrix}. \quad (27)$$

Falta ahora encontrar una ley de control $u(1)$ tal que $x(1) \in \text{Im } C^*$, para ello debido al Proposición 4.2, es necesario que $x(1) = \text{Bu}(1) \oplus w$ satisfaga la condición $w \le \text{Aw}$. Aplicando nuevamente el Método de doble descripción tropical al sistema $\mathbb{I}w \le \text{Aw}$, encontramos que un sistema generador para este, es $G = \{e^3, e^4, (e 1 \epsilon \epsilon)^T\}$. Luego,

$$\mathcal{W} = \{w | w \le \text{Aw}\} = \text{cone}(G) \cap \mathbb{R}_{\max}^{+5}.$$

Note que $e^4 \notin \text{Im } C^*$.

Para que la condición inicial $x(1)$ este en $\text{Im } C^*$, basta tomar $u(1) = Fw$, con $w \in \mathcal{W}$, ver demostración de Proposición 4.2, luego el control obtenido usando $w = e^4$ es $u(1) = e^1$, y en este caso la condición inicial es $x(1) = (e 1 \ 2 \ 5 \epsilon)^T$, y por tanto $x(1) \in \text{Im } C^*$, luego la evolución del sistema asociada a esta condición inicial y a la secuencia de controles no decreciente
$u(1) = (e \epsilon)^T, u(2) = (5 \epsilon)^T, u(3) = (10 \epsilon)^T, \dots$, es dada por:

$$ \begin{bmatrix} e \\ 1 \\ 2 \\ 5 \\ \epsilon \end{bmatrix}, \begin{bmatrix} 5 \\ 6 \\ 7 \\ 10 \\ \epsilon \end{bmatrix}, \begin{bmatrix} 10 \\ 11 \\ 12 \\ 15 \\ \epsilon \end{bmatrix}, \begin{bmatrix} 15 \\ 16 \\ 17 \\ 20 \\ \epsilon \end{bmatrix}, \dots, \quad (28) $$

la cual claramente satisface las restricciones impuestas al sistema.

Si un control no es aplicado, tenemos la siguiente trayectoria del sistema comenzando en el mismo estado inicial:

$$ \begin{bmatrix} e \\ 1 \\ 2 \\ 5 \\ \epsilon \end{bmatrix}, \begin{bmatrix} \epsilon \\ 3 \\ 6 \\ 9 \\ \epsilon \end{bmatrix}, \begin{bmatrix} \epsilon \\ 6 \\ 10 \\ 13 \\ \epsilon \end{bmatrix}, \dots $$

la cual no satisface las restricciones impuestas al sistema, por ejemplo la restricción 1 jamás puede ser satisfecha para cualquier $\tau_1^{max}$.

**Observación 5.1.** La retroalimentación de estado obtenida bajo este enfoque difiere de la matriz de control encontrada en (Amari, 2012) para este mismo ejemplo, la cual es:

$$ F = \begin{bmatrix} \epsilon & \epsilon & e & e & e \\ \epsilon & \epsilon & e & e & e \end{bmatrix}. $$

Desde el punto de vista práctico podría resultar más sencillo implementar el control obtenido en nuestros resultados, ya que tiene menos elementos no nulos.

## 5.2. Control de robots en cluster-tools

Consideremos el GET de la figura 3, el cual es una variación del ejemplo tratado en (Atto, 2011). Este GET representa el comportamiento de un cluster tool equipado con un brazo único, herramienta de uso frecuente en la industria de semiconductores. El cluster tool es un dispositivo integrado de procesamiento de obleas de silicio, que consiste de varios módulos de procesamiento, un robot de manipulación, y un almacén para la carga y descarga de obleas de silicio. En este ejemplo, las obleas de silicio son procesadas en dos etapas, el cluster tool tiene tres PMs, dos son dedicados a la primera etapa y el tercero a la segunda etapa, ver (N. Wu et al., 2008). El cluster tool tiene restricciones estrictas sobre el tiempo de residencia que una oblea de silicio puede permanecer en una PM. Despúes que una oblea de silicio es procesada, esta debería ser descargada con un tiempo limitado. De lo contrario, su superficie sufre severos problemas de calidad.

El comportamiento dinámico del GET es dado por la ecuación de estados (16), donde $x(k)=(x_1(k),...,x_{12}(k))^T$ es el vector de estado, $u(k)=(u_1(k),...,u_4(k))^T$ es el vector de control, la matriz A satisface que todas sus columnas $A_j$ son nulas salvo las columnas $A_4$ y $A_7$: $A_4=(28\ 28\ 228\ 250\ e\ 79\ 153\ \epsilon\ 103\ 125\ 125\ 204)^T$ y $A_7=(\epsilon\ \epsilon\ 254\ 26\ \epsilon\ \epsilon\ 179\ e\ 129\ 151\ 151\ \epsilon)^T$, y la matriz B es como sigue,

<figure><img src="image_4.png" /><figcaption>Figura 3: GET con 4 restricciones temporales en $p_2, p_5, p_8$ y $p_{11}$.</figcaption></figure>

$$ B = \begin{bmatrix} \epsilon & \epsilon & \epsilon & \epsilon \\ e & \epsilon & \epsilon & \epsilon \\ 129 & 228 & 254 & 103 \\ 151 & 250 & 276 & 125 \\ \epsilon & e & \epsilon & \epsilon \\ \epsilon & 79 & \epsilon & \epsilon \\ \epsilon & 153 & 179 & \epsilon \\ \epsilon & \epsilon & e & \epsilon \\ \epsilon & 103 & 129 & \epsilon \\ \epsilon & 125 & 151 & \epsilon \\ \epsilon & 125 & 151 & e \\ \epsilon & 204 & 230 & 79 \end{bmatrix} $$

Cuatro restricciones temporales adicionales son asignadas a los nodos lugares $p_2, p_5, p_8$ y $p_{11}$ de este grafo. En el nodo lugar $p_i$ con $i=2, 8$, una oblea de silicio comienza a ser procesada (etapa 1) y espera. El tiempo de permanencia en la PM no puede superar $\tau_1^{max}$. En el nodo lugar $p_i$ con $i=5, 11$, se lleva a cabo la etapa 2, la cual no puede superar el tiempo $\tau_2^{max}$. Estas restricciones son expresadas respectivamente por la siguientes desigualdades:

$$ \begin{cases} i = 1: \text{ es asociada a la restricción } x_3(k) \le \tau_1^{\max} \otimes x_2(k), \\ i = 2: \text{ es asociada a la restricción } x_6(k) \le \tau_2^{\max} \otimes x_5(k), \\ i = 3: \text{ es asociada a la restricción } x_9(k) \le \tau_3^{\max} \otimes x_8(k), \\ i = 4: \text{ es asociada a la restricción } x_{12}(k) \le \tau_4^{\max} \otimes x_{11}(k), \end{cases} \quad (29) $$

$$ \text{donde } \tau_1^{\max} = \tau_3^{\max} = 149 \text{ y } \tau_2^{\max} = \tau_4^{\max} = 94. $$

Note que las restricciones temporales son admisibles al control, ver Definición 4.2. Así como en el caso anterior, nuestro interés es calcular una matriz de control $F \in \mathbb{R}_{\max}^{4 \times 12}$ tal que garantice que los estados del sistema en lazo cerrado evolucionen satisfaciendo las restricciones (29), resumidas en el cono max plus Im C*, esto es $x(k) \in \text{Im } C^*$, para $k \ge 2$, y además describir el conjunto de condiciones iniciales admisibles tal que satisfagan que $x(1) \in \text{Im } C^*$. La matriz C $\in \mathbb{R}_{\max}^{12 \times 12}$ es la matriz asociada a las restricciones temporales satisfaciendo que $C_{23} = C_{89} = -149$, $C_{56} = C_{11,12} = -94$ y $C_{ji} = \epsilon$ en cualquier otro caso.

La existencia de una matriz $F \in \mathbb{R}_{\max}^{4 \times 12}$ tal que la propiedad deseada $\text{Im}(A \oplus BF) \subset \text{Im } C^*$ se verifique, se debe a que además
el cono max plus $\mathcal{D}$, definido por:

$$ \begin{bmatrix} 129 & 228 & 254 & 103 \\ \epsilon & 79 & \epsilon & \epsilon \\ \epsilon & 103 & 129 & \epsilon \\ \epsilon & 204 & 230 & 79 \end{bmatrix} \otimes_{\mathcal{V}} \begin{bmatrix} 149 & \epsilon & \epsilon & \epsilon \\ \epsilon & 94 & \epsilon & \epsilon \\ \epsilon & \epsilon & 149 & \epsilon \\ \epsilon & 219 & 245 & 94 \end{bmatrix} \otimes_{\mathcal{V}}, $$

posee una solución $\mathcal{V}$ tal que $\sup(\mathcal{V}) = \bar{4}$. En efecto, aplicando el Método de doble descripción tropical (Allamigeon, 2010), un sistema generador para el conjunto solución $\mathcal{D}$ es:

$$ \{e^1, (254 \epsilon 149 \epsilon)^T, (103 \epsilon 149)^T, (506 \epsilon 298 \epsilon)^T\}, $$

luego, existe por ejemplo $\mathcal{V} = (506 \ 298 \ 401 \ 149)$ en $\mathcal{D}$ tal que $\sup(\mathcal{V}) = \bar{4}$.

Así, existe $F$ tal que la propiedad deseada se cumple y cada columna de $F$ satisface lo siguiente:

$$ \begin{bmatrix} 129 & 228 & 254 & 103 \\ \epsilon & 79 & \epsilon & \epsilon \\ \epsilon & 103 & 129 & \epsilon \\ \epsilon & 204 & 230 & 79 \end{bmatrix} \begin{bmatrix} F_{1r} \\ F_{2r} \\ F_{3r} \\ F_{4r} \end{bmatrix} \oplus \begin{bmatrix} A_{3r} \\ A_{6r} \\ A_{9r} \\ A_{12,r} \end{bmatrix} \le \begin{bmatrix} 149 & \epsilon & \epsilon & \epsilon \\ \epsilon & 94 & \epsilon & \epsilon \\ \epsilon & \epsilon & 149 & \epsilon \\ \epsilon & 219 & 245 & 94 \end{bmatrix} \begin{bmatrix} F_{1r} \\ F_{2r} \\ F_{3r} \\ F_{4r} \end{bmatrix}. \quad (30) $$

Para calcular $F$, primero para cada $r$, consideraremos el poliedro tropical $\mathcal{P}_r$ definido como el conjunto solución de (30), luego, podemos representar $\mathcal{P}_r$ como proyecciones de conos poliédricos max plus de $\mathbb{R}_{\max}^{4+1}$, debido a la Definición 2.3. Luego, el cono homogenizado asociado a $\mathcal{P}_r$, es denotado por $\tilde{\mathcal{P}}_r$ y definido como el conjunto solución de (31).

Como vimos antes, si encontramos un sistema de generadores del cono max plus $\tilde{\mathcal{P}}_r$, podemos encontrar un sistema de generadores del poliedro max plus $\mathcal{P}_r$, y en consecuencia podemos conocer todas las posibles leyes de control que pueden ser aplicadas para satisfacer que la condición $x(k) \in \text{Im } \mathcal{C}^*$, para $k \ge 2$.

$$ \begin{bmatrix} 129 & 228 & 254 & 103 & A_{3r} \\ \epsilon & 79 & \epsilon & \epsilon & A_{6r} \\ \epsilon & 103 & 129 & \epsilon & A_{9r} \\ \epsilon & 204 & 230 & 79 & A_{12,r} \end{bmatrix} \begin{bmatrix} z_1 \\ z_2 \\ z_3 \\ z_4 \\ z_5 \end{bmatrix} \le \begin{bmatrix} 149 & \epsilon & \epsilon & \epsilon & \epsilon \\ \epsilon & 94 & \epsilon & \epsilon & \epsilon \\ \epsilon & \epsilon & 149 & \epsilon & \epsilon \\ \epsilon & 219 & 245 & 94 & \epsilon \end{bmatrix} \begin{bmatrix} z_1 \\ z_2 \\ z_3 \\ z_4 \\ z_5 \end{bmatrix}. \quad (31) $$

Note que en la columna $r$, $r = 1, 2, 3, 5, 6, 8, 9, 10, 11, 12$, las componentes $A_{ir}$ son nulas para $i = 1, \dots, 4$, así que basta tomar $F_r = \epsilon$ es estos casos, ver Observación 4.1.

Para $r = 4$, consideremos el sistema de desigualdades (31) y el sistema homeogéneo asociado, donde $A_{34} = 228$, $A_{64} = 79$, $A_{94} = 103$ y $A_{12,4} = 204$. Un sistema de generadores del conjunto solución del sistema homeogéneo es:

$$ \left\{ e^1, \begin{bmatrix} e \\ \epsilon \\ -105 \\ \epsilon \\ \epsilon \end{bmatrix}, \begin{bmatrix} -46 \\ \epsilon \\ \epsilon \\ e \\ \epsilon \end{bmatrix}, \begin{bmatrix} e \\ -79 \\ -125 \\ \epsilon \\ \epsilon \end{bmatrix}, \begin{bmatrix} e \\ -94 \\ -125 \\ \epsilon \\ -79 \end{bmatrix} \right\}. $$

Por tanto, $\mathcal{P}_4 = \text{co}(\{(79 - 15 - 46 \epsilon)^T\}) \oplus \text{cone}(\{e^1, (-46 \epsilon \epsilon e)^T, (e \epsilon - 105 \epsilon)^T, (e - 79 - 125 \epsilon)^T\})$. Considerando como criterio adicional que la matriz $F$ sea causal, podemos tomar $F_4 = (79 - 15 - 46 \epsilon)^T \oplus 125 \otimes (e - 79 - 125 \epsilon)^T = (125 46 e \epsilon)^T$.

Para $r = 7$, se procede como antes y se tiene que $\mathcal{P}_7 = \text{co}((105 \epsilon - 15 \epsilon)^T, (105 \epsilon - 20 136)^T, (105 11 - 15 \epsilon)^T) \oplus \text{cone}(\{e^1, (e \epsilon - 105 \epsilon)^T, (-46 \epsilon \epsilon e)^T, (e - 79 - 125 \epsilon)^T\})$. Luego podemos tomar $F_7 = (105 \epsilon e \epsilon)^T$.

Por tanto, una matriz de control $F$ que satisfaga las restricciones temporales para $k \ge 2$ es dada por:

$$ F = \begin{bmatrix} \epsilon & \epsilon & \epsilon & 125 & \epsilon & \epsilon & 105 & \epsilon & \epsilon & \epsilon & \epsilon \\ \cdot & \cdot & \cdot & 46 & \cdot & \cdot & \epsilon & \cdot & \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot & e & \cdot & \cdot & e & \cdot & \cdot & \cdot & \cdot \\ \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon \end{bmatrix}. \quad (32) $$

Ahora encontremos el conjunto de condiciones iniciales admisibles tal que $x(1) \in \text{Im } \mathcal{C}^*$. Como la condición inicial $x(1)$ está en $\text{Im } \mathcal{C}^*$ independientemente del $w$ elegido, siempre que $w$ satisfaga: $w \le Aw$ y $w \in \mathbb{R}_{\max}^{+12}$, tomaremos $w$ con todas sus entradas iguales a $e$. (Aplicando nuevamente el Método de doble descripción podemos encontrar un conjunto generador para el sistema $\mathbb{I}w \le Aw$). Luego, una ley de control $u(1) \in \mathbb{R}_{\max}^4$ tal que la condición inicial este en $\text{Im } \mathcal{C}^*$ es $u(1) = Fw = (125 46 e \epsilon)$, en este caso $x(1) = (e 125 274 296 46 125 199 e 149 171 171 250)^T$, la cual satisface las restricciones temporales, y por tanto esta en $\text{Im } \mathcal{C}^*$. Luego, si el control $F$ definido por (32) es aplicado. La trayectoria $x(k)$ del sistema asociada a esta condición inicial y a la secuencia de controles no decreciente:

$$ \begin{bmatrix} 125 \\ 46 \\ e \\ \epsilon \end{bmatrix}, \begin{bmatrix} 421 \\ 342 \\ 396 \\ \epsilon \end{bmatrix}, \begin{bmatrix} 717 \\ 638 \\ 592 \\ \epsilon \end{bmatrix}, \begin{bmatrix} 1013 \\ 934 \\ 888 \\ \epsilon \end{bmatrix}, \dots, $$

obtenida en este caso es:

$$ \begin{bmatrix} e \\ 125 \\ 274 \\ 296 \\ 46 \\ 125 \\ 199 \\ e \\ 149 \\ 171 \\ 171 \\ 250 \end{bmatrix}, \begin{bmatrix} 324 \\ 421 \\ 570 \\ 592 \\ 342 \\ 421 \\ 495 \\ 296 \\ 445 \\ 467 \\ 467 \\ 546 \end{bmatrix}, \begin{bmatrix} 620 \\ 717 \\ 866 \\ 888 \\ 638 \\ 717 \\ 791 \\ 592 \\ 741 \\ 763 \\ 763 \\ 842 \end{bmatrix}, \begin{bmatrix} 916 \\ 1013 \\ 1162 \\ 1184 \\ 934 \\ 1013 \\ 1087 \\ 888 \\ 1037 \\ 1059 \\ 1059 \\ 1138 \end{bmatrix}, \dots $$

la cual claramente satisface las restricciones (29) impuestas al sistema. Si un control no es aplicado, comenzando en el mismo
estado inicial, tenemos la siguiente trayectoria:

<table><tr><td>e</td><td>324</td><td>574</td><td>824</td></tr><tr><td>125</td><td>324</td><td>574</td><td>824</td></tr><tr><td>274</td><td>524</td><td>754</td><td>1024</td></tr><tr><td>296</td><td>546</td><td>796</td><td>1046</td></tr><tr><td>46</td><td>296</td><td>546</td><td>796</td></tr><tr><td>125</td><td>375</td><td>625</td><td>875</td></tr><tr><td>199</td><td>449</td><td>699</td><td>949</td></tr><tr><td>e</td><td>219</td><td>449</td><td>699</td></tr><tr><td>149</td><td>399</td><td>649</td><td>899</td></tr><tr><td>171</td><td>421</td><td>671</td><td>921</td></tr><tr><td>171</td><td>421</td><td>671</td><td>921</td></tr><tr><td>250</td><td>500</td><td>750</td><td>1000</td></tr></table>

Note que a partir de la misma condición inicial tomada en el cono max plus Im C*, se tiene que al evolucionar el sistema sin un control, la trayectoria del mismo, no se mantiene dentro del cono max plus que resume las restricciones temporales dados por (29), por ejemplo la restricción 1 no se satisface.

## 6. Conclusiones

En este artículo, el problema de control de grafos de eventos temporizados sujeto a restricciones temporales, fue trata-
do usando un enfoque geométrico. Las restricciones temporales impuestas al espacio de estado del sistema, se describieron en el cono max plus definido por la imagen de la estrella de Kleene de la matriz asociada a estas restricciones. En consecuencia, el problema de determinar un control que fuerza la satisfacción de las restricciones temporales, se formula en términos de la inva-
rianza de este cono. Establecimos condiciones suficientes para la existencia de una solución a este problema. Nuestra propues-
ta permite el diseño de un control satisfactorio, de la forma de una retroalimentación estática de estado. Podemos subrayar que nuestra solución toma en cuenta dos aspectos que son la inicia-
lización de la ley de control, y su causalidad, importantes para su implementación. Para ilustrar la aplicación de este enfoque, dos problemas de control fuerón presentados.

## English Summary

### Control Problem in Max Plus Linear Model with Temporal Constraints

### Abstract

This article deals with the control of discrete event systems subject to synchronization and delay phenomena, described by a plus max linear model. The temporal constraints are imposed on the state space of the system. These constraints are described in the max plus cone defined by the image of the Kleene

star of the matrix associated with the temporal constraints. In consequence, the problem of determining a control that force the satisfaction of time constraints, is formulated in terms of the invariance of the cone. Sufficient conditions for the existence of a solution to this problem have been established. Our approach allows the design of a satisfactory control of the form of a static state feedback. We emphasize that our solution takes into account two aspects which are the initialization of the control law, and its causality, important for its implementation. To illustrate the application of this approach, two control problems are presented.

### Keywords:

### Discrete Event Systems, Timed Event Graphs, Max Plus Algebra, Temporal Constraints.

Allamigeon, X., Gaubert, S., Goubault, É., 2010. "The tropical double description method", in Proc. Symp. Theor. Aspects Comp. Sci., Nancy, France, pp. 47-58.

Allamigeon, X., Gaubert, S., Goubault, É., 2012. Computing the vertices of tropical polyhedra using directed hypergraphs, Discrete Comput. Geom.

Amari, S., Demongodin, I., Loiseau, J. J., Martinez, C., 2012. Max-plus control design for temporal constraints meeting in timed event graphs, IEEE Trans. Automatic Control, Vol. 57, No. 2, pp. 462-467.

Atto A., Martinez C., Amari S., 2011. Control of discrete event systems with respect to strict duration: supervision of an industrial manufacturing plant. Comput Inf Syst 61(4):1149-1159.

Baccelli, F., Cohen, G., Olsder, G.-J., Quadrat, J.-P., 1992. Synchronization and Linearity. John Wiley & Sons, New York.

Cohen, G., Gaubert, S., Quadrat, J. P., 1999. "Max-plus algebra and system theory: where we are and where to go now," Annu. Rev. Control, vol. 23, pp. 207-219.

Cohen, G., 2001. Análisis y Control de sistemas de eventos discretos: De redes de Petri temporizadas. Argentina: ENPC & INRIA (Francia).

Gaubert, S., Katz, R., 2007. The Minkowski theorem for max-plus convex sets. Linear Algebra and Appl., 421:356-369.

Gaubert, S., Katz, R., 2009. The tropical analogue of polar cones. Linear Algebra and Appl., 431:608-625.

Gaubert, S., Katz, R., 2011. Minimal half-spaces and external representation of tropical polyhedra, Journal of Algebraic Combinatorics 33, no. 3, 325-348.

Katz, R. D., 2007. Max-plus (A,B)-invariant spaces and control of timed discrete-event systems, IEEE Trans. Automatic Control, Vol. 52, No. 2, pp. 229-241.

Kim, J. H., Lee, T. E. 2003. Schedule stabilization and robust timing control for time-constrained cluster tools. In IEEE international conference on robotics and automation, pp. 1039-1044. Taipei, Taiwan.

Libeaut, L., Loiseau, J., 1995. Admissible initial conditions and control of timed event graphs, 34th Conference on Decision and Control, New Orleans, Louisianna.

Maia, C., Andrade, C., Hardouin, L., 2011. On the control of max plus linear system subject to state restriction. Automatica 47(5): 988-992.

Murata, T., 1989. Petri nets: Properties, analysis and applications. IEEE, Proc 77(4), 541-580.

Wonham, W. M., Linear Multivariable Control: A Geometric Approach, 3rd ed. New York: Springer-Verlag.

Wu, N., Chu, C., Chu, F., Zhou, M. 2008. A Petri net method for schedulability and scheduling problems in single-arm cluster tools with wafer residency time constraints, IEEE Trans. Semiconduct. Manuf., vol. 21, pp. 224-237.