Publicación Cuatrimestral. Vol. 7, No. Especial, Diciembre, 2022, Ecuador (p. 239 -255). Edición continua
https://revistas.utm.edu.ec/index.php/Basedelaciencia/index
revista.bdlaciencia@utm.edu.ec
Universidad Técnica de Manabí
DOI: https://doi.org/10.33936/revbasdelaciencia.v7iESPECIAL.4598.
UNA REVISIÓN DE CONTROL EN SISTEMAS DINÁMICOS DE EVENTOS
DISCRETOS
Carla Estefanía Demera Reyna
1∗
, Guelvis Enrique Mata Díaz
2
1
Instituto de Posgrado Universidad Técnica de Manabí, Portoviejo, Ecuador.
Email: carlaestefaniademera@gmail.com
2
Facultad de Ciencias, Departamento de Matemáticas, Universidad de Los Andes, Mérida,
Venezuela. Email: gematad2017@gmail.com
∗
Autor para correspondencia: carlaestefaniademera@gmail.com
Recibido: 27-05-2022/ Aceptado: 13-12-2022/ Publicación: 27-12-2022
Editor Académico: Carmen Judith Vanegas
RESUMEN
A partir de los años ochenta es propuesta una teoría para el control de una clase de sistemas, llamados sistemas de
eventos discretos. Tal teoría es referida en general como control supervisorio y es una herramienta potencial para la
minimización o eliminación del bloqueo en la clase de sistemas antes mencionada. Aquí los resultados teóricos son
establecidos naturalmente en el dominio de los lenguajes formales, mientras la síntesis y los resultados computacionales
son dados en el campo de los autómatas finitos determinísticos. Esto es crucial pues apertura una extensión a sistemas
de gran escala. En este trabajo se considera una revisión y discusión de la teoría de control supervisorio, estableciendo
para esto un marco referencial que abarca los conceptos más relevantes desde su inicio hasta la actualidad, que permiten
demostrar que el concepto de bloqueo en sistemas de eventos discretos es intrínsecamente monolítico (global). En verdad,
este no puede ser tratado en general de una forma modular.
Palabras clave: Control, planificación, sistemas de eventos discretos.
A REVIEW OF CONTROL IN DISCRETE EVENT DYNAMICAL SYSTEMS
ABSTRACT
Starting in the 1980s, a theory was proposed for the control of a class of systems, called discrete event systems. Such
a theory is generally referred to as supervisory control and is a potential tool for minimizing or eliminating blocking
in the aforementioned class of systems. Here the theoretical results are naturally established in the domain of formal
languages, while the synthesis and computational results are given in the field of deterministic finite automata. This is
crucial as it opens an extension to large-scale systems. In this paper, a review and discussion of supervisory control
theory is considered, establishing for this a referential framework that encompasses the most outstanding concepts from
its beginning to the present day, which allow us to demonstrate that the concept of blocking in discrete event systems is
intrinsically monolithic (global). In truth, this cannot be treated in general in a modular way.
Keywords: control, discrete event systems, planning.
Demera, C. and Mata, G.
UMA REVISÃO DE CONTROLE EM SISTEMAS DINÁMICOS DE EVENTOS
DISCRETOS
RESUMO
A partir da década de 1980, foi proposta uma teoria para o controle de uma classe de sistemas, denominados sistemas a
eventos discretos. Tal teoria é geralmente referida como controle supervisório e é uma ferramenta potencial para minimizar
ou eliminar bloqueios na classe de sistemas acima mencionada. Aqui os resultados teóricos são estabelecidos naturalmente
no domínio das linguagens formais, enquanto os resultados de síntese e computacionais são dados no campo dos autômatos
finitos determinísticos. Isso é crucial, pois abre uma extensão para sistemas de grande escala. Neste artigo, é feita uma
revisão e discussão da teoria do controle supervisório, estabelecendo para isso um referencial que engloba os conceitos
mais destacados desde o seu início até os dias atuais, o que nos permite demonstrar que o conceito de bloqueio em
sistemas a eventos discretos é intrinsecamente monolítico (global). Na verdade, isso não pode ser tratado em geral de
forma modular.
Palavras chave: controle, planejamento, sistemas de eventos discretos.
Citación sugerida: Demera, C. and Mata, G. Una revisión de control en sistemas dinámicos de eventos
discretos. Revista Bases de la Ciencia, Vol. 7, No. Especial, Diciembre, 2022, Ecuador (p. 239 -255).
DOI: https://doi.org/10.33936/revbasdelaciencia.v7iESPECIAL.4598
1. INTRODUCCIÓN
Tal como es expuesto en Branicky (1995), un sistema de eventos discretos (SED) puede ser des-
crito como un espacio discreto de estados (configuraciones físicas del sistema en el tiempo) donde
los cambios entre estos son producidos por la ocurrencia de eventos (acciones); en consecuencia,
entre los tiempos de ocurrencias de cualesquiera dos eventos consecutivos no se expresan cambios
en las condiciones lógicas del sistema. Las redes de comunicación, sistemas químicos, distribuidos,
logísticos y de transporte, entre otros, son SED, Aldaniyazov (2018), Hopcroft y cols. (2008).
Un problema de control en SED es la supervisión. Esta es incluida para asegurar el flujo ordenado
de eventos que garantice que los procesos concluyan tareas colectivas y minimicen el bloqueo del
sistema: objetivo de control. Este formalismo fue iniciado por Whonham y Ramadge en la década de
los 80 y actualmente es estudiado extensivamente usando teoría de autómatas y lenguajes, Eilemberg
(1974), Alfonseca y cols. (2007), Giró y cols. (2015). La revisión y discusión de la teoría de control
supervisorio considerada aquí solo resalta un subconjunto de resultados que se han desarrollado en
este campo de investigación: control por realimentación dinámica, lenguajes controlables y no con-
trolables, problemas de control con sus soluciones y control modular. La mayoría de estos resultados
pueden ser encontrados en Mata (2017), Ramadge y Wonham (1987) y pueden ser reforzados en
Sengupta y Lafortune (1988), Tsitsik (1989) y Wonham y Ramadge (1985). Finalmente, aunque no
son tratados aquí, vale la pena enfatizar la investigación sobre el control bajo observación parcial:
situación donde el controlador S (supervisor) no vé todos los eventos del sistema A , sino solo un
subconjunto adecuado de eventos observables; control descentralizado y la extensión de control su-
pervisorio a SED temporales, junto al control en línea con políticas de anticipación limitadas, Kumar
(1991), Lin y Wonhan (1988).
2. CONCEPTOS Y RESULTADOS BÁSICOS EN TEORÍA DE CONTROL
El control supervisorio es establecido para satisfacer un conjunto de condiciones cualitativas sobre
los lenguajes generado y marcado por el sistema. La premisa es, por razones funcionales del sistema,
que algún subconjunto de la dinámica es no admisible, y por lo tanto debe ser eliminado. Así, el
control es añadido para reducir el conjunto de sucesiones de eventos que el sistema puede generar a un
subconjunto de la dinámica sujeto a condiciones. Más aún, el control también es ejercido para eliminar
o minimizar el bloqueo en algunos SED. Esto se logra con algunos resultados básicos de la teoría de
control supervisorio focalizados sobre la no controlabilidad, pero con énfasis en la realimentación
dinámica.
2.1. Producto y composición paralela entre autómatas determinísticos
El producto y la composición paralela son modelos para la representación global de un sistema de
eventos discretos que contienen el aspecto de sincronización. En efecto, en el producto las transiciones
de los autómatas están siempre sincronizadas por un evento común; mientras que, en la composición
paralela un evento común puede ser llevado a cabo si los autómatas dados ejecutan dicho evento
simultáneamente. Los otros eventos no están sujetos a esta condición y por lo tanto siempre pueden
ser ejecutados, mientras sea posible.
Demera, C. and Mata, G.
Definición 2.1. Sean A
1
= (Q
1
,Σ
1
,δ
1
,E
1
,q
01
,Q
m1
) y A
2
= (Q
2
,Σ
2
,δ
2
,E
2
,q
02
,Q
m2
) dos autómatas
determinísticos, entonces
(i) Se llama autómata producto de A
1
y A
2
al autómata determinístico, A
1
× A
2
, definido por:
A
1
× A
2
:= A
a
(Q
1
× Q
2
,Σ
1
∩ Σ
2
,δ ,E ,(q
01
,q
02
),Q
m1
× Q
m2
),
donde A
a
es la parte accesible,
δ ((q
1
,q
2
),α) =
(
(δ
1
(q
1
,α),δ
2
(q
2
,α)), si α ∈ E
1
(q
1
) ∩ E
2
(q
2
)
indefinido, en otro caso
y E ((q
1
,q
2
)) = E
1
(q
1
) ∩ E
2
(q
2
).
(ii) Se llama composición paralela de A
1
y A
2
al autómata determinístico, A
1
||A
2
, definido por
A
1
||A
2
:= A
a
(Q
1
× Q
2
,Σ
1
∪ Σ
2
,δ ,E ,(q
01
,q
02
),Q
m1
× Q
m2
),
donde
δ ((q
1
,q
2
),α) =
(δ
1
(q
1
,α),δ
2
(q
2
,α)) si α ∈ E
1
q
1
) ∩ E
2
(q
2
)
(δ
1
(q
1
,α),q
2
) si α ∈ E
1
(q
1
) \ Σ
2
(q
1
,δ
2
(q
2
,α)) si α ∈ E
2
(q
2
) \ Σ
1
indefinido, en otro caso
y E ((q
1
,q
2
)) = (E
1
(q
1
) ∩ E
2
(q
2
)) ∪ (E
1
(q
1
) \ Σ
2
) ∪ (E
2
(q
2
) \ Σ
1
).
Se puede probar sin dificultad que L (A
1
× A
2
) = L (A
1
) ∩ L (A
2
) y
L
m
(A
1
× A
2
) = L
m
(A
1
) ∩ L
m
(A
2
).
Por otro lado, las proyecciones naturales π
i
: (Σ
1
∪ Σ
2
)
∗
−→ Σ
∗
i
, i = 1,2, son dadas por π
i
(θ) = θ,
π
i
(α) =
(
α, si α ∈ Σ
i
θ, si α ̸∈ Σ
i
,
π
i
(sα) = π
i
(s)π
i
(α), s ∈ (Σ
1
∪ Σ
2
)
∗
, α ∈ Σ
1
∪ Σ
2
; y los correspondientes mapeos inversos son dados
por π
−1
i
(t) = {s ∈ (Σ
1
∪ Σ
2
)
∗
: π
i
(s) = t}, π
−1
i
: Σ
∗
i
−→ (Σ
1
∪ Σ
2
)
∗
, i = 1,2. Finalmente, π
i
y π
−1
i
,
i = 1,2, son extendidas a lenguajes como sigue:
Para L ⊆ (Σ
1
∪ Σ
2
)
∗
, π
i
(L ) = {t ∈ Σ
∗
i
/∃s ∈ L ,π
i
(s) = t} ; y para L
i
⊆ Σ
∗
i
,
π
−1
i
(L
i
) = {s ∈ (Σ
1
∪ Σ
2
)
∗
: ∃t ∈ L
i
,π
i
(s) = t}.
Por lo tanto,
L (A
1
||A
2
) = π
−1
1
(L (A
1
)) ∩ π
−1
2
(L (A
2
))
y
L
m
(A
1
||A
2
) = π
−1
1
(L
m
(A
1
)) ∩ π
−1
2
(L
m
(A
2
)).
Ahora bien, si Σ
1
= Σ
2
entonces la composición paralela es el producto. En efecto, todas las tran-
siciones son forzadas a ser sincronizadas. Si Σ
1
∩Σ
2
= /0 entonces no hay transiciones sincronizadas y
en consecuencia A
1
||A
2
es el comportamiento concurrente de A
1
y A
2
. Esto último es referido como
el shuffle de A
1
y A
2
.
Finalmente, el producto y la composición paralela pueden ser extendidos naturalmente al caso de
un número finito de autómatas.
En efecto, si {A
i
}
n
i=1
es una colección finita de autómatas determinísticos con
A
i
= (Q
i
,Σ
i
,δ
i
,E
i
,q
0i
,Q
mi
), i = 1,...,n
entonces el producto de los A
i
, denotado por
n
"
i=1
A
i
es dada por
n
"
i=1
A
i
= A
a
n
"
i=1
Q
i
,
n
\
i=1
Σ
i
,δ ,E ,(q
01
,...,q
0n
),
n
"
i=1
Q
mi
!
,
donde
δ ((q
1
,q
2
,...,q
n
),α) =
(δ
1
(q
1
,α),...,δ
n
(q
n
,α)), si α ∈
n
\
i=1
E
i
(q
i
)
indefinda, en otro caso
y E ((q
1
,q
2
,...,q
n
)) =
n
\
i=1
E
i
(q
i
).
Por su parte, la composición paralela de los A
i
, denotada
n
| |
i=1
A
i
, es dada por
n
| |
i=1
A
i
= A
a
n
"
i=1
Q
i
,
n
[
i=1
Σ
i
,δ ,E ,(q
01
,...,q
0n
),
n
"
i=1
Q
mi
!
,
donde
δ ((q
1
,q
2
,...,q
n
),α) =
(δ
1
(q
1
,α),...,δ
n
(q
n
,α)), si α ∈
n
\
i=1
E
i
(q
i
)
(P
1
,P
2
,...,P
n
), con P
i
= δ
i
(q
i
,α), y P
j
= q
j
, si α ∈
\
i
E
i
(q
i
) \
[
j: j̸=i
Σ
j
indefinida, en otro caso
Además,
L
n
"
i=1
A
i
=
n
\
i=1
L
i
(A
i
),
L
m
n
"
i=1
A
i
=
n
\
i=1
L
m
i
(A
i
)
y
L
n
| |
i=1
A
i
!
=
n
\
i=1
π
−1
i
(L (A
i
)),
L
m
n
| |
i=1
A
i
!
=
n
\
i=1
π
−1
i
(L
m
(A
i
))
Demera, C. and Mata, G.
donde, los π
i
:
n
[
i=1
Σ
i
!
∗
→ Σ
∗
i
, i = 1,...,n son las proyecciones naturales.
2.2. Control en sistemas de eventos discretos
Suponga dado un SED, y sea Σ el conjunto de eventos admitidos en el sistema. A un nivel de
abstracción lógico, sea L = L el lenguaje físicamente posible generado por el SED y sea L
m
⊆ L
el lenguaje que representa las completaciones de tareas o logros de objetivos en el SED.
Sea A un autómata determinístico que representa al par de lenguajes L y L
m
: L = L (A ) y
L
m
(A ) = L
m
. En este sentido, se hace referencia al SED como A .
Se particiona a Σ en dos subconjuntos Σ = Σ
c
∪ Σ
nc
, donde Σ
c
denota al conjunto de eventos
controlables; es decir, eventos que pueden ser inhabilitados por un controlador externo; y Σ
nc
denota
al conjunto de eventos no controlables; es decir, eventos cuyas ocurrencias no pueden ser inhabilitadas
por control (eventos imposibles de controlar, eventos que no pueden ser inutilizados, entre otros).
Ahora, suponga que la función δ : Q × Σ → Q de A es controlada por un mecanismo externo, lo
cual significa que los eventos en Σ
c
podrían ser prevenidos o no en su ocurrencia. Entonces, el autóma-
ta determinístico A puede ser acoplado a un controlador o supervisor S en un lazo de realimentación
dinámica (Ver figura 1).
Figura 1. Un proceso de realimentación dinámica
Formalmente,
Definición 2.2. Sea A = (Q,Σ,δ ,E ,q
0
,Q
m
) un autómata determinístico, y sea Σ = Σ
c
∪ Σ
nc
una
partición de Σ. Un supervisor S para A es cualquier función S : L (A ) → Γ := {γ ∈ 2
Σ
: Σ
nc
⊆ γ}.
Para acoplar el controlador o supervisor externo S al autómata determinístico A se establece lo
siguiente:
Si s ∈ L (A ), entonces S(s) ∩ E (δ (q
0
,s)) es el conjunto de eventos permitidos que A puede
llevar a cabo en el estado δ (q
0
,s), bajo el supervisor S; esto significa que A no puede ejecutar un
evento si simultáneamente este no pertenece a su conjunto de eventos activos y a S(s).
Se llama a S(s) patrón de control en s. Por definición, Σ
nc
⊆ S(s) = γ ∈ Γ. Esto asegura que el
controlador S no puede inhabilitar a los eventos en Σ
nc
. En fín, se obtiene un proceso de realimentación
dinámica, expresando con esto que el dominio de S es L (A ) y no el conjunto de estados de A . En
consecuencia, se puede obtener una variación de los patrones de control a través del paso por los
estados en la evolución del sistema A . Luego, el acoplamiento final de A es denotado S/A .
Definición 2.3. Sea A un autómata determinístico con Σ = Σ
c
∪ Σ
nc
una partición de Σ. Sea S un
supervisor para A . El lenguaje generado por S/A es dado recursivamente por:
(i) θ ∈ L (S/A );
(ii) Para s ∈ Σ
∗
y α ∈ Σ se tiene que: s ∈ L (S/A ), sα ∈ L (A ), α ∈ S(s) ⇐⇒ sα ∈ L (S/A ).
El lenguaje marcado por S/A es dado por L
m
(S/A ) = L (S/A ) ∩ L
m
(A ).
Desde la definición 2.3, L (S/A ) ⊆ L (A ) es cerrado. Además, /0 ⊆ L
m
(S/A ) ⊆ L
m
(S/A ) ⊆
L (S/A ) ⊆ L (A ). En adelante, si S/A es bloqueado entonces se dice que el supervisor S para A
es bloqueado. Así, por definición de L
m
(S/A ) se tiene que sus elementos son aquellos en L
m
(A )
que preservan las completaciones de tareas bajo el control de S. Entonces, el bloqueo expresa que
S/A no finaliza la ejecución de alguna tarea.
2.3. Planificación
Dado un SED A y sus correspondientes lenguajes generado y marcado L (A ) y L
m
(A ) res-
pectivamente, referidos como lenguajes no controlados, se hace referencia a un par de lenguajes
L
p
⊆ L (A ) (lenguaje de planificación admisible) y L
p
m
⊆ L
m
(A ) (lenguaje de planificación ad-
misible marcado) para justificar la inclusión de un supervisor o controlador S. L
p
y L
p
m
son con-
dicionamientos sobre el sistema; es decir, establecen los requerimientos impuestos sobre el SED A .
En general, estos requerimientos se expresan a través de uno o más lenguajes, posiblemente marca-
dos, L
Ei
, i = 1,2,...,n. Si los lenguajes L
Ei
⊈ L (A ) (respectivamente L
Ei
⊈ L
m
(A )), entonces se
puede escribir apropiadamente
L
p
= L (A ) ∩
m
\
i=1
L
Ei
!
respectivamente L
p
m
= L
m
(A ) ∩
m
\
i=1
L
Ei
!!
.
Se asume que la planificación L
p
o L
p
m
es dada.
2.4. Lenguajes controlables
Se quiere saber bajo que condiciones un lenguaje de planificación L
p
es ejecutable por un super-
visor S.
Definición 2.4. Dado un SED A con Σ
nc
⊆ Σ su conjunto de eventos no controlables. Sea K ⊆ L (A ),
K ̸= /0.
(i) K es llamado L
m
(A )–cerrado si K = K ∩ L
m
(A );
(ii) K es llamado controlable con respecto a L (A ) y Σ
nc
si KΣ
nc
∩ L (A ) ⊆ K.
Observación 2.1. En la definición 2.4 se enfatiza el concepto básico y fundamental del control su-
pervisorio. En efecto, (ii) expresa que un lenguaje puede ser ejecutado de manera controlada, si y
solo si, toda palabra de dicho lenguaje concatenada con un evento no controlable que determina
una nueva palabra físicamente posible sigue estando en el lenguaje original. Adicionalmente, K es
controlable ⇔ K es controlable.
Demera, C. and Mata, G.
Teorema 2.1. (Teorema principal)
Sea K ⊆ L
m
(A ), K ̸= /0. Sea Σ
nc
⊆ Σ el conjunto de eventos no controlables de A . Existe un supervi-
sor no bloqueado S para A tal que K = L
m
(S/A ), si y solo si, K es L
m
(A )–cerrado y controlable
con respecto a L (A ) y Σ
nc
.
Demostración. Suponga que existe un supervisor no bloqueado S para A tal que K = L
m
(S/A ).
Por definición de L (S/A ), L (S/A )Σ
nc
∩ L (A ) ⊆ L (S/A ). Luego, del no bloqueo de S se
sigue que L
m
(S/A )Σ
nc
∩ L (A ) ⊆ L
m
(S/A ); es decir, KΣ
nc
∩ L (A ) ⊆ K. Por otro lado,
K = L
m
(S/A ) = L (S/A ) ∩ L
m
(A ) = L
m
(S/A ) ∩ L
m
(A ) = K ∩ L
m
(A ).
Recíprocamente, suponga que K es L
m
(A )–cerrado y controlable con respecto a L (A ) y Σ
nc
.
Sea S el supervisor para A definido por S(s) = Σ
nc
∪ {α ∈ Σ
c
: sα ∈ K}.
Afirmación: K = L (S/A ). En efecto, por definición de S y controlabilidad de K es claro que
L (S/A ) ⊆ K. Para la otra dirección se procede por inducción sobre la longitud de la palabra. Sea
s ∈ K, con |s| = 1; es decir, s = α para algún α ∈ Σ, entonces s ∈ L (S/A ). Dado un lenguaje L ⊆ Σ
∗
,
sea L
i
:= {s ∈ L : |s| = i}, i = 0,1,2,... Claramente L =
∞
[
i=0
L
i
.
Suponga que L
i
(S/A ) = K
i
, i = 0,1,...,n (hipótesis de inducción). Sea s ∈ L
n
(S/A ) y consi-
dere la palabra sα ∈ L (A ), α ∈ Σ. Si sα ∈ K entonces α ∈ S(s); de donde, sα ∈ L (S/A ). Por lo
tanto, L
n+1
(S/A ) = K
n+1
. Luego, K ⊆ L (S/A ). En consecuencia, K = L (S/A ).
Finalmente, desde la afirmación y que K es L
m
(A )–cerrado se sigue que
K = K ∩ L
m
(A ) = L (S/A ) ∩ L
m
(A ) = L
m
(S/A )
y
L (S/A ) = K = K ∩ L
m
(A ) = L (S/A ) ∩ L
m
(A ) = L
m
(S/A ).
Corolario 2.1. Sean K ⊆ L (A ), K ̸= /0, y sea Σ
nc
⊆ Σ el conjunto de eventos no controlables de A .
Existe un supervisor S para A tal que K = L (S/A ), si y solo si, K es cerrado y controlable con
respecto a L (A ) y Σ
nc
.
Demostración. suponga que existe un supervisor S para A tal que K = L (S/A ), entonces obvia-
mente K = K; es decir, K es cerrado. También, por definición de L (S/A ), L (S/A )Σ
nc
∩ L (A ) ⊆
L (S/A ); es decir, KΣ
nc
∩ L (A ) ⊆ K. Así, K es controlable con respecto a L (A ) y Σ
nc
.
Recíprocamente, si K es controlable con respecto a L (A ) y Σ
nc
, y K = K, entonces tomando el
supervisor S definido en la prueba del teorema 2.1 y procediendo de manera análoga se obtiene que
K = L (S/A ) = K.
Corolario 2.2. Sea K ⊆ L
m
(A ), K ̸= /0, y sea Σ
nc
⊆ Σ el conjunto de eventos no controlables del
SED A . Existe un supervisor S para A tal que K = L (S/A ), si y solo si, K es controlable con
respecto a L (A ) y Σ
nc
.
Demostración. Análoga a la demostración del colorario 2.1
Observación 2.2. Si A es un SED y Σ
nc
es el conjunto de eventos no controlables, entonces K = /0 y
K = L (A ) son controlables con respecto a L (A ) y Σ
nc
. De hecho, aunque estos son por definición
controlables, ellos corresponden a los casos triviales de controlabilidad: K = /0 puede ser interpreta-
do como que el sistema nunca es inicializado y K = L (A ) no juega ningún papel importante.
Dados un SED A y K ⊆ L
m
(A ), se tiene que K es un lenguaje controlable en relación a L (A ) y
Σ
nc
siempre que exista un controlador S para A , con K = L (S/A ). En lo que sigue se hace referencia
a un lenguaje controlable con respecto a L (A ) y Σ
nc
como controlable. Más aún, si el no bloqueo es
de interés y K es L
m
(A )-cerrado, entonces K = L
m
(S/A ), con S no bloqueado.
Por razones de implementación es necesario establecer una representación del supervisor S a
través de un autómata determinístico. Dicho autómata es llamado una realización del supervisor o
controlador S. Si los lenguajes L (A ),L
m
(A ) y K son regulares, entonces la realización del contro-
lador S es un autómata finito determinístico, y por lo tanto implementable. En consecuencia, se puede
leer en tiempo real el patrón de control de la sucesión de eventos que está siendo ejecutada.
Formalmente, sin perder generalidad suponga que S : L (S/A ) → Γ.
Sea R = (X,Σ,δ
R
,E
R
,x
0
,X) un autómata determinístico limpio, con K = L (R) = L
m
(R). En-
tonces, para el autómata producto A × R se tiene
L (A × R) = L (R) ∩ L (A ) = K ∩ L (A ) = K = L (S/A )
y
L
m
(A × R) = L
m
(R) ∩ L
m
(A ) = K ∩ L
m
(A ) = L (S/A ) ∩ L
m
(A ) = L
m
(S/A ).
La lectura de lo antes expuesto es que una vez excluidos de S(s) los eventos en Σ
nc
que no están
en E (δ (q
0
,s)), el patrón de control S(s) permanece incluido en la estructura de transición de R. Es
decir,
S(s) ∩ E (δ (q
0
,s)) = E
A ×R
(δ
A ×R
((q
0
,x
0
),s)) = E
R
(δ
R
(x
0
,s)),
donde E
A ×R
(δ
A ×R
((q
0
,x
0
),s)) = E
R
(δ
R
(x
0
,s)) se sigue de
K ⊆ L (A ).
Note que A ×R está bien determinado sin hacer consideraciones de ningún argumento de control;
pero, desde un punto de vista práctico se tiene la siguiente interpretación: Sea s ∈ L (S/A ), y sean q
y x los estados alcanzados luego de la ejecución de s. Si α ∈ E (q) ocurre en A , se tiene igualmente
que α ∈ E
R
(x). Luego, el evento α también ocurre en R como observador pasivo. Sean q
′
= δ (q
0
,α)
y x
′
= δ
R
(x
0
,α) los estados alcanzados en A y R respectivamente por la ocurrencia de α, entonces
el conjunto de eventos activos de A por sα es el mismo de R en x
′
. Por lo tanto, si K es un lenguaje
regular, entonces se ha construido un autómata finito determinístico que representa al controlador S.
2.5. Lenguajes no controlables.
En general, los lenguajes de planificación L
p
y L
p
m
son no controlables. Por lo tanto, es necesario
considerar operaciones sobre esta clase de lenguajes, junto con algunas estructuras matemáticas que
nos permita garantizar la controlabilidad óptima.
Teorema 2.2. Sea {K
i
}
i∈I
una familia arbitraria de lenguajes, K
i
⊆ L (A ) para todo i ∈ I.
(i) Si los K
i
son controlables, entonces
[
i∈I
K
i
es controlable.
Demera, C. and Mata, G.
(ii) Si los K
i
son controlables y cerrados, entonces
\
i∈I
K
i
es controlable y cerrado
Demostración. (i) Si
K
i
Σ
nc
∩ L (A ) ⊆ K
i
para todo i ∈ I, entonces
[
i∈I
K
i
!
Σ
nc
∩ L (A ) =
[
i∈I
K
i
!
Σ
nc
∩ L (A ) =
[
i∈I
(K
i
Σ
nc
)
!
∩ L (A )
=
[
i∈I
(K
i
Σ
nc
∩ L (A )) ⊆
[
i∈I
K
i
=
[
i∈I
K
i
.
Por lo tanto,
[
i∈I
K
i
es controlable.
(ii) Si K
i
= K
i
para todo i ∈ I, entonces
\
i∈I
K
i
=
\
i∈I
K
i
=
\
i∈I
K
i
. Así,
\
i∈I
K
i
es cerrado.
Adicionalmente, si K
i
Σ
nc
∩ L (A ) ⊆ K
i
para todo i ∈ I, entonces
\
i∈I
K
i
Σ
nc
∩ L (A ) =
\
i∈I
K
i
!
Σ
nc
∩ L (A ) ⊆ K
j
Σ
nc
∩ L (A ) ⊆ K
j
para todo j ∈ I; luego,
\
i∈I
K
i
Σ
nc
∩ L (A ) ⊆
\
i∈I
K
i
=
\
i∈I
K
i
.
Por lo tanto,
\
i∈I
K
i
es controlable.
Sea K ⊆ L (A ) y considere los conjuntos
C
⊂
(K) := {L ⊆ K : L Σ
nc
∩ L (A ) ⊆ L }
y
C
⊃
(K) := {L : K ⊆ L ⊆ L (A ),L =
L ,L Σ
nc
∩ L (A ) ⊆
L }.
Claramente C
⊂
(K) y C
⊃
(K) son no vacíos ( /0 ∈ C
⊂
(k) y L (A ) ∈ C
⊃
(K)). Más aún, C
⊂
(K) es un
conjunto ordenado parcialmente por ⊆. Luego, por la parte (i) del teorema 2.2 se tiene que C
⊂
(K)
posee como supremo único a K
sup
=
[
L ∈C
⊂
(K)
L .
Definición 2.5. Sea K ⊆ L (A ). K
sup
es llamado el sublenguaje controlable supremo de K.
Notese que si K es controlable, entonces K
sup
= K. Ahora, K
sup
no necesariamente es cerrado. Por
lo tanto, se incluye el teorema siguiente.
Teorema 2.3. (i) Si K ⊆ L (A ) es cerrado, entonces K
sup
es cerrado;
(ii) Si K ⊆ L
m
(A ) es L
m
(A )–cerrado, entonces K
sup
es L
m
(A )–cerrado.
(iii) K
sup
⊆ K
sup
.
Demostración. (i) Suponga que K = K. Entonces, L ∈ C
⊂
(K), si y solo si, L ⊆ K y L Σ
nc
∩
L (A ) ⊆ L , si y solo si, L ⊆ K = K y L Σ
nc
∩ L (A ) ⊆ L , si y solo si, L ∈ C
⊂
(K). Luego,
K
sup
=
[
L ∈C
⊂
(K)
L =
[
L ∈C
⊂
(K)
L =
[
L ∈C
⊂
(K)
L = K
sup
(ii) Suponga que K ⊆ L
m
(A ) es L
m
(A )–cerrado. Entonces, L ∈C
⊂
(K) implica que L ∩L
m
(A ) ⊆
K ∩ L
m
(A ) = K y L es controlable. Como L ∩ L
m
(A ) ⊆ L entonces
K
sup
∩ L
m
(A ) =
[
L ∈C
⊂
(K)
(L ∩ L
m
(A )) ⊆ K
sup
⊆ K
sup
∩ L
m
(A )
(recuerde que K
sup
⊆ K ⊆ L
m
(A )). Luego, K
sup
= K
sup
∩L
m
(A ). Así, K
sup
es L
m
(A )–cerrado.
(iii) L ∈ C
⊂
(K) =⇒ L ⊆ K, L Σ
nc
∩ L (A ) ⊆ L =⇒ L ⊆ K, L Σ
nc
∩ L (A ) ⊆ L =⇒ L ∈
C
⊂
(K). Luego, K
sup
=
[
L ∈C
⊂
(K)
L ⊆
[
P∈C
⊂(K)
P = K
sup
.
Ahora, C
⊃
(K) es un conjunto ordenado parcialmente por ⊆. Luego, del teorema 2.2 se sigue que
C
⊃
(K) posee como ínfimo único a K
´
ınf
=
\
L ∈C
⊃
(K)
L .
Definición 2.6. Sea K ⊆ L (A ). El lenguaje K
´
ınf
es llamado el superlenguaje cerrado y controlable
ínfimo de K.
Observe que K
´
ınf
= K siempre que K sea controlable.
Se puede verificar desde las definiciones que /0 ⊆ K
sup
⊆ K ⊆ K ⊆ K
´
ınf
⊆ L (A ).
3. ALGUNOS PROBLEMAS DE CONTROL
Los argumentos teóricos dados en las secciones precedentes permiten sintetizar los controladores
que simplifican la existencia y construcción de las realizaciones requeridas, según sea el problema de
control a resolver.
Problema básico de Control
Dados un SED A , el conjunto de eventos no controlables Σ
nc
⊆ Σ de A y una planificación
L
p
= L
p
⊆ L (A ), construir un supervisor S para A tal que:
(i) L (S/A ) ⊆ L
p
;
(ii) Si S
′
es otro controlador para A con L (S
′
/A ) ⊆ L
p
, entonces L (S
′
/A ) ⊆ L (S/A ).
Demera, C. and Mata, G.
Solución:
Como L
p
es cerrado entonces (L
p
)
sup
es cerrado (ver teorema 2.3, (i)). Luego, (L
p
)
sup
⊆ L (A )
es cerrado y controlable. Así, desde el corolario 2.1 se sigue que existe un supervisor S para A tal que
L (S/A ) = (L
p
)
sup
⊆ L
p
. Más aún, si S
′
es tal que L (S
′
/A ) ⊆ L
p
entonces L (S
′
/A ) ∈ C
⊂
(L
p
);
pero (L
p
)
sup
es el más grande de estos. Por lo tanto, L (S
′
/A ) ⊆ L (S/A ). En consecuencia, para
la solución del problema básico de control supervisorio, basta tomar S tal que L (S/A ) = (L
p
)
sup
siempre que (L
p
)
sup
̸= /0. Finalmente, si L (S/A ) = (L
p
)
sup
es un lenguaje regular entonces se puede
construir una realización del supervisor S, la cual es un autómata finito determinístico (AFD) que
representa a (L
p
)
sup
.
Problema de control sin bloqueo
Dados un SED A , Σ
nc
⊆ Σ y un lenguaje marcado L
p
m
⊆ L
m
(A ) L
m
(A )–cerrado, construir un
supervisor no bloqueado S tal que:
(i) L
m
(S/A ) ⊆ L
p
m
;
(ii) Si S
′
es otro controlador no bloqueado con L
m
(S
′
/A ) ⊆ L
p
m
, entonces L (S
′
/A ) ⊆ L (S/A ).
Solución:
Como en el problema anterior, usando los resultados de las secciones precedentes la solución es
seleccionar S tal que L (S/A ) = (L
p
m
)
sup
, siempre que (L
p
m
)
sup
̸= /0. Es importante notar que bajo el
supuesto que L
p
m
es L
m
(A )–cerrado, (L
p
m
)
sup
es igualmente L
m
(A )–cerrado. Esto garantiza que
la elección de S resulta en un sistema S/A no bloqueado (ver teorema 2.1). Ahora, si (L
p
m
)
sup
es
regular entonces S puede ser realizado por construcción de una representación AFD de (L
p
m
)
sup
.
Problema de control dual
Dados un SED A , Σ
nc
⊆ Σ y un lenguaje requerido mínimo L
m
´
ın
⊆ L (A ), construir un supervisor
S tal que:
(i) L
m
´
ın
⊆ L (S/A );
(ii) Si S
′
es otro controlador con L
m
´
ın
⊆ L (S
′
/A ), entonces L (S/A ) ⊆ L (S
′
/A ).
Solución
Por el teorema 2.2, (ii), y la definición de C
⊃
(L
m
´
ın
) tenemos que (L
m
´
ın
)
´
ınf
es controlable y cerrado.
Así, desde el corolario 2.1 se sigue que existe un supervisor S para A tal que L (S/A ) = (L
m
´
ın
)
´
ınf
⊇
L
m
´
ın
. Por otro lado, si S
′
es otro supervisor para A tal que L
m
´
ın
⊆ L (S
′
/A ) entonces L (S
′
/A ) ∈
C
⊃
(L
m
´
ın
); pero (L
m
´
ın
)
´
ınf
es el más pequeño de estos, de donde L (S/A ) = (L
m
´
ın
)
´
ınf
⊆ L (S
′
/A ).
Luego, los requerimientos (i) y (ii) son satisfechos por S. Por lo tanto, para la solución óptima del
problema de control supervisorio dual basta tomar S tal que L (S/A ) = (L
m
´
ın
)
´
ınf
. Note que si L
m
´
ın
⊆
L
m
(A ), entonces
L
m
´
ın
⊆ L
m
´
ın
∩ L
m
(A ) ⊆ (L
m
´
ın
)
´
ınf
∩ L
m
(A )) = L
m
(S/A ).
Sin embargo, nada asegura que S es no bloqueado. De hecho, la versión sin bloqueo del problema de
control supervisorio dual posee dificultades técnicas puesto que la propiedad de controlabilidad no se
preserva bajo intersección.
Problema de control con tolerancia
Dados un SED A ,Σ
nc
⊆ Σ, un lenguaje marcado deseado L
d
⊆ L
m
(A ) y una planificación de
tolerancia L
t
= L
t
⊆ L (A ), donde L
d
⊆ L
t
; construir un supervisor S para A tal que:
(i) L (S/A ) ⊆ L
t
;
(ii) Si K es un lenguaje cerrado y controlable con K ⊆ L
t
, entonces K ∩ L
d
⊆ L (S/A ) ∩ L
d
;
(iii) Si K es un lenguaje cerrado y controlable con K ⊆ L
t
y K ∩ L
d
= L (S/A ) ∩ L
d
, entonces
L (S/A ) ⊆ K.
Solución:
Sea S tal que L (S/A ) = ((L
t
)
sup
∩L
d
)
in f
(la existencia de S está garantizada desde los resultados
de las secciones previas).
Ahora, como (L
t
)
sup
es cerrado y controlable, y (L
t
)
sup
∩ L
d
⊆ (L
t
)
sup
entonces ((L
t
)
sup
∩
L
d
)
in f
⊆ (L
t
)
sup
⊆ L
t
. Por otro lado, si K ⊆ L
t
es cerrado y controlable entonces K ⊆ (L
t
)
sup
; de
donde K ∩L
d
⊆ (L
t
)
sup
∩L
d
; luego, K ∩L
d
⊆ L (S/A ). En consecuencia, K ∩L
d
⊆ L (S/A )∩L
d
.
Finalmente, en adición a las hipótesis establecidas para K, si K ∩ L
d
= L (S/A ) ∩ L
d
entonces
(L
t
)
sup
∩ L
d
⊆ L (S/A ) implica que (L
t
)
sup
∩ L
d
⊆ L (S/A ) ∩ L
d
= K ∩ L
d
⊆ K. Por lo tanto,
L (S/A ) ⊆ K. Luego, S es solución del problema de control supervisorio con tolerancia. Para fina-
lizar, el supervisor S no necesariamente es no bloqueado. De hecho, la versión sin bloqueo de este
problema no posee en general una solución óptima y tiene muchas dificultades técnicas.
4. CONTROL MODULAR
El control modular hace referencia a la situación donde la acción de control del supervisor S es
dada por alguna combinación de acciones de control de dos o más supervisores. Aquí se discute la
conjunción entre supervisores.
Definición 4.1. Dados S
1
,S
2
,··· ,S
n
, n ≥ 2, supervisores definidos para un sed A . Se llama supervi-
sor modular al supervisor S
mod
: L (A ) → Γ dado por S
mod
(s) =
n
\
i=1
S
i
(s).
Proposición 4.1. El supervisor modular S
mod
de los S
i
, i = 1,2,··· ,n es tal que L (S
mod
/A ) =
n
\
i=1
L (S
i
/A ) y L
m
(S
mod
/A ) =
n
\
i=1
L
m
(S
i
/A ).
Dadas las realizaciones estándar R
i
de los S
i
, i = 1,2,··· ,n, la realización estándar de S
mod
puede
se construida como R =
n
"
i=1
R
i
. Pero se trata precisamente de no construir dicha realización, sino más
bien utilizar la existencia de las R
i
, i = 1, 2, · · · ,n, y realizar la acción de control S
mod
considerando
Demera, C. and Mata, G.
la intersección de los conjuntos de eventos activos de los R
i
, i = 1,2,·· · ,n; en sus respectivos estados
después de la ejecución de s. Esta realización es llamada la realización modular del supervisor S
mod
, la
cual reduce su tamaño original. En efecto, si R
i
tiene n
i
estados, i = 1,2,··· , n; entonces se necesitan
n
∑
i=1
n
i
estados para esta realización modular en lugar de posiblemente, a lo sumo,
n
∏
i=1
n
i
estados tal
como R. Nótese que se puede interpretar la supervisión de A por S
mod
como el producto R
1
× R
2
×
···× R
n
×A . Esto es un argumento de complejidad similar que motiva la síntesis de un supervisor en
forma modular.
Si el lenguaje de planificación (admisible) L
p
para el problema básico de control supervisorio
puede ser descompuesto como la intersección de n lenguajes cerrados: L
p
= L
p
1
∩ L
p
2
∩ ··· ∩ L
p
n
;
entonces se puede sintetizar S
i
para (L
p
i
)
sup
, i = 1,2,··· ,n y usar estos n supervisores en con-
junción en lugar de hacer el cálculo directo de (L
p
)
sup
. Al utilizar este enfoque modular, la com-
plejidad computacional total para la síntesis de supervisores es reducida desde O(n
1
n
2
···n
n
m) a
O(máx{n
1
,n
2
,··· ,n
n
}m), donde m es el número de estados de A . En fin, este enfoque modular
es muy útil puesto que en el caso de lenguajes cerrados (
n
\
i=1
L
p
i
)
sup
=
n
\
i=1
(L
p
i
)
sup
. Esta discusión es
formalizada en la versión modular siguiente del problema básico de control supervisorio
4.1. Problema básico de control supervisorio modular
Dados un SED A , Σ
nc
⊆ Σ un conjunto de eventos no controlables y un lenguaje de planificación
L
p
=
n
\
i=1
L
p
i
, donde L
p
i
= L
p
i
⊆ L (A ) para i = 1,2,··· ,n, construir un supervisor modular S
mod
tal que:
1. L (S
mod
/A ) ⊆ L
p
;
2. L (S
mod
/A ) es óptimo con respecto a ⊆.
Solución:
Se construyen las realizaciones R
i
de los S
i
, i = 1,2,··· ,n, tales que L (S
i
/A ) = (L
p
i
)
sup
y se
toma el supervisor modular S
mod
, entonces L (S
mod
/A ) = (L
p
1
)
sup
∩ (L
p
2
)
sup
∩ ··· ∩ (L
p
n
)
sup
=
(L
p
1
∩ ··· ∩ L
p
n
)
sup
= (L
p
)
sup
es la solución óptima.
Desafortunadamente, este enfoque modular no puede ser extendido a la versión sin bloqueo del
problema de control supervisorio básico. La razón es que la conjunción de n supervisores no bloquea-
dos, n ≥ 2, no necesariamente es no bloqueada. Sin embargo,
Teorema 4.1. Sean S
i
, i = 1, 2, · · · ,n, supervisores no bloqueados para un SED A . Entonces, S
mod
es no bloqueado, si y solo si,
n
\
i=1
L (S
i
/A ) =
n
\
i=1
L (S
i
/A )
Este resultado tiene la implicación siguiente. Si se considera la versión modular del problema bási-
co de control supervisorio sin bloqueo donde L
p
m
=
n
\
i=1
L
p
m
i
, con L
p
m
i
⊆ L
m
(A ) y L
m
(A )−cerrado,
i = 1,2,··· ,n (lo cual implica que L
p
m
en si mismo es L
p
m
(A )−cerrado), entonces al sintetizar los
S
i
tales que L (S
i
/A ) = (L
p
m
i
)
sup
para i = 1, 2, · · · ,n, se obtiene el supervisor modular S
mod
; por lo
tanto, se tiene
L (S
mod
/A ) =
n
\
i=1
(L
p
m
i
)
sup
;
L
m
(S
mod
/A ) =
n
\
i=1
(L
p
m
i
)
sup
!
∩ L
m
(A )
=
n
\
i=1
(L
p
m
i
)
sup
⊇
n
\
i=1
L
p
m
i
!
sup
= (L
p
m
)
sup
.
Esto significa que el supervisor modular puede ser bloqueado, aunque es admisible en el sentido que
L
m
(S
mod
/A ) ⊆ L
p
m
.
Desde los resultados anteriores, el problema básico de control supervisorio sin bloqueo tiene una
solución modular sin bloqueo, si y solo si,
n
\
i=1
L
m
(S
i
/A ) =
n
\
i=1
L
m
(S
i
/A ) (∗). El problema es
que esta última condición no puede ser verificada antes de hacer los cálculos del operador sup;
sin embargo, para verificar esta condición es necesario examinar simultáneamente a los (L
p
m
i
)
sup
,
i = 1,2,··· , n. A diferencia de un enfoque global, como opuesto a modular, se requiere formar la
intersección
n
\
i=1
L
p
m
i
y luego realizar la operación sup sobre ese resultado, un cálculo que tiene esen-
cialmente la misma complejidad computacional, en el peor caso, que la verificación de la condición
(∗). Más aún, el enfoque global garantiza un no bloqueo global; es decir, L (S/A ) = (L
p
m
)
sup
;
sin embargo, si la solución modular es verdaderamente no bloqueada, entonces como se mencionó
anteriormente, sigue siendo ventajosa desde el punto de vista de la implementación. La conclusión de
esta discusión es que el concepto de bloqueo es intrínsecamente global; este no puede ser tratado en
general de una forma modular.
5. CONCLUSIÓN
Las secciones 3 y 4 demuestran que los problemas de control supervisorio pueden ser resueltos
automáticamente por algoritmos que en el peor caso poseen complejidad computacional cuadrática.
El resultado final es la realización estándar de un supervisor S que resuelve el problema de control de
interés. Los dos ingredientes claves para la aplicación de estos resultados de síntesis son la disponibi-
lidad del autómata que modela el sistema dado y el lenguaje admisible marcado o no. El modelo del
SED A es usualmente obtenido por la composición paralela de los modelos individuales A
i
de los
subsistemas componentes. Las dificultades típicas encontradas en las aplicaciones en SED son:
(i) Seleccionar el nivel de abstracción correcto para el modelo, dadas las especificaciones impues-
tas sobre el sistema;
(ii) Seleccionar el conjunto de eventos comunes entre las componentes del sistema que apropiada-
mente capturen el acoplamiento entre estas;
Demera, C. and Mata, G.
(iii) Lidiar con la complejidad computacional resultante del modelo global, la cual crece exponen-
cialmente como función del número de subsistemas.
El segundo ingrediente clave en la teoría de control supervisorio es el autómata H que reconoce al
lenguaje admisible. Aquí hay que asegurar el diseño para la síntesis en el sentido que las condiciones
o especificaciones en A son convencionalmente dadas en lenguaje natural con respecto a L (A ) y
no inmediatamente como un autómata. Por lo tanto, se debe construir el autómata requerido que lleve
a cabo de forma segura todas las especificaciones o condiciones establecidas para el sistema.
6. DECLARACIÓN DE CONFLICTO DE INTERÉS DE LOS AUTORES
Los autores declaran no tener conflicto de intereses.
7. REFERENCIAS
Aldaniyazov, K. (2018). Main factors for the improvement of a complex system of strategic produc-
tion cost management. Revista Espacios, 39(11), pp. 29.
Alfonseca, E., Alfonseca, M., y Moriyón, R. (2007). Teoría de autómatas y lenguajes formales.
McGraw-Hill.
Branicky, M. (1995). Studies in hibrid systems: Modeling, analysis and control. PhD thesis, Massa-
chusetts inst technol. Cambridge, Dept. Elec. Fng. And computer Sci..
Eilemberg, S. (1974). Automata, languages and machines. Academic Press, New York, Vol. A.
Giró, J., Vázquez, J., Meloni, B., y Constable, L. (2015). Lenguajes formales y teoría de autómatas.
Alfaomega, Buenos Aires, Argentina.
Hopcroft, J., Motwani, R., y Ullman, J. (2008). Teoría de autómatas, lenguajes y computación.
Pearson-Addison-Wesley, USA.
Kumar, R. e. a. (1991). On controllability and normality of discrete event dinamical systems. Systems
and control leters, Vol. 17, pp. 157-168.
Lin, F., y Wonhan, M. (1988). On observability of discrete event systems. Inform. Sci.
Mata, G. (2017, enero-abril). Supervisory control application to solving optimal control problems for
discrete event systems. Revista Ingeniería UC, Vol.24 núm.1, pp. 81-90.
Ramadge, P., y Wonham, W. (1987). Supervisory control of a class of discrete event processes. En:
SIAM Journal on control and optimizaion.
Sengupta, R., y Lafortune, S. (1988). An optimal control theory for diserete event systems. En: SIAM
Journal of control and optimization.
Tsitsik, J. (1989). On the control of discrete events dinamical systems. En: Math. of control signals,
and systems, No. 2, pp. 95-107.
Wonham, W., y Ramadge, P. (1985). On the supremal controllable sublanguage of a given language.
En: SIAM Journal of control and optimization.
CONTRIBUCIÓN DE AUTORES
Autor Contribución
Carla Estefanía Demera Reyna Desarrollo metodológico, redacción del artículo y desarro-
llo de resultados teóricos, el bloqueo es un concepto mono-
lítico no local.
Guelvis Enrique Mata Díaz Revisión conceptual de los argumentos utilizados, dirección
de los contenidos y referencias, el bloqueo es un concepto
monolítico no local.
