вход по аккаунту


Formulae of the Infimal Controllable and Observable Sub-language and Synthesis of Its Supervisor.

код для вставкиСкачать
Dev. Chem. Eng. Mineral Process., 9(1E),pp.161-166,2001.
Formulae of the Infimal Controllable and
Observable Sub-language and Synthesis of
Its Supervisor
Yan Wenjun' and Shentu Weinong'
Institute of Electrical Automation, Zhejiang University, Hangzhou
310027, P.R. China
'HangZhou Broadcast Television College, Hangzhou, P. R. China
The Supervisory Control Theory of Discrete Event Dynamical Systems (DEDS) is one
main approach of studying DEDS in recent years. The existing condition of the
supervision and the synthesizing method under partial controllable and observable
events are investigated. A formula for the infimal prefir closed controllable and
observable sub-language of a given language is presented. The effectiveness of the
method is illustrated with two examples.
The supervisory theory of discrete event plants was first introduced by Ramadge and
Wonham, which is a control policy for Discrete Event Systems (DES) at the logical
layer. The sufficient and necessary condition of the existence of a supervisor is given
[11 when all events are observable, and the sufficient and necessary existing condition
of a supervisor when the events are partially observable and controllable is given [2].
Observability is defined in another form [3], but no deeper results are obtained. When
the expected behavior lies in a given range, the supervisor exists only if the event set
consists of observable events and controllable events, yet the calculation method is
complicated. The theorem presented in this paper not only overcomes those defects
described above, but also leads to a closed form solution to the problem of finding a
complete supervisor. When the minimal accepted behavior A and the maximal legal
behavior E are not closed, the infimal prefix closed controllable and Observable
sublanguage of A ( inf@(A)) still has a closed form solution other than the super
A (sup@(A)
). It can be
can be
seen that some restriction arises in supervisor designed by
In this paper, we adopt the definition of DES model [l] and the definition of the
i n f i i sublanguage [4]. Also, the finite set of events C is partitioned as controllable
subset C, and uncontrollable subset C,, , observable subset C, and unobservable
language of the controllable and observable language of
* Authorfor con-espondence.(
Y. Wenjm and S.Weinong
c = c, uc,, = c, uc,
The Existing Condition for Supervisor
By definition of controllability and observability, Lin and Wonham [2] showed that
the existing conhtion for a supervisor under partial observation was as follows:
Theorem 1: Let a language K E Lm(G), then there exists a proper supervisor
such that Lm(Y / G ) = K,L(Y / G ) = K if and only if K is controllable and
For the prespecified desired behavior A and E ,A E E E C' , where J? is legal
behavior, A is minimal acceptable behavior, C* denotes the set of all finite strings
over c ,plus the empty string E ,we define an new language class as:
CO(L)= {K:K 2 L,K is prefvr closed, controllable and observable
Lemma 1: The language class @ ( L ) is closed under set intersection.
Proof: Let K , , K , c @(L) , then K , , K , is prefix closed, controllable and
observable. Obviously,K , nK , is prefvr closed. From the definition of
controllability, K , nK , is easily proved to be controllable. For the same reason,
K,nK, is observable [2]. So a ( L ) is closed under intersection computation.
Theorem 2: There exists a complete supervisor
such that QkrA_CL(WG))_CE if,
and only if, infCO(A)E E .
Proof: Necessity. Assume there exists a supewisor
such that &A_CL(!WG))_CE.
Then by Theorem 1, L(Y / G ) is whether empty or controllable and observable.
Because the empty set is also controllable and observable, then L(Y!/G) is
controllable and observable. As a result of closure of L(Y /G) and hypothesis, we
have L(Y / G)a A . By definition of i n f @ ( L ) , the result inf @(A) c L( Y / G)
can be obtained. Furthermore, by the initial hypothesis, it is true that
Sufficiency: Suppose i n f a ( A ) E E and K = infCO(L) , then controllability and
observability of K is obvious. By Theorem 1, it is easy to check that K = # or there
exists a supervisor Y! such that Lm(Y / G) = K . If K is empty, then A = 4 , this
conflicts with the hypothesis. So Lm(Y / G ) = K is available. Furhermore, K is
closed by the definition of inf @ ( L ) and it leads to L(Y / G )= K . And by
hypothesis and definition of A , E , K c E and K a A , and A G L(Y / G )E E can
be obtained.
For the problem on supervisory control with partial observation (SCPO),we need
design a supervisor such that 2c L(Y / G ) c B .
Controllable & Observable Sub-language & Synthesis of Its Supervisor
Lemma 2: If A , E is Lm( G) -closed, and 4' ' is one of solutions for SCPO, then
A s L,(Y/G)cE.
Proof: If 'I'is one of solutions for SCPO, then
2nLm(G)G L(Y / G ) nLm(G) c
Since A, E is tm(G) -closed, so A c Lc( Y / G) E .
By Theorem 2 and Lemma 2,it is not difficultto get the following
Theorem 3: There exists a complete supervisor such that A E Lc( Y J G) E E and
2~ L ( Y / G ) c E i f a n d o n l y i f i n f W ( 2 ) G E .
Supervisor Synthesis
The key problem to design a supervisor is to find a solution of i n f a ( L ) .The closed
form solution of inf m(L)is shown as:
Proposition 1: For a given language L c Lm(G) ,L;t-t#, we define a new language as:
B 3 L( G)- (C'
C,-P-'(P(L C,nL))nC' C,) nC'
= L(G)-(c'c, -M)c'
kf = P - ' ( P ( z C , nL))nC' c, ,then B = inf @(L) .
Proof: First we must show that B is prefix closed, controllable, observable and
is prefix closed. Take
E B .T h e n s a E L(G) and
is prefur closed,sEL(G). Also we have
Thus,s E B ,i.e. B is prefvr closed.
B is controllable. Take SO E t(G),LT E C,, ,s E B, Furthermore, since
C' C, -M ,then so e (C' 1,-M)C* . So
SO~L(G)-(C*C,-M)C* ~ S O E B
which implies that
B is controllable.
3. B 2 L . Let (3~)sE C*,o E C,sc E Z,
. If o E
(C'C, - M I;If LT E C, ,then
L = E L 3sc E L n Z SO E p-lp(EonZ)
Y. Wenjun and S. Weinong
=,so e (C'
C,- M )
(By definition of
In both cases above, so e (C'C, -M) . Moreover, since so E L(G) by
hypothesis, then so E B ,which implies that B r,
4. B is observable.
Let s,tEC*,P(s)=P(t),and s,tEB,toEB,saEL(G),we need show that
Case 1:
then we claim
that s o e ( C * C,-M)
is true since
so e C' C, .Therefore so e (C*C, - M ) c * .
Case 2: if
C, ,then
= to e (C' C, -M)C* = to e (c' C, - M I
to E M = to E P-'P(Lo n E)
3 P(tcr)E P(LOnt)
3 P(W) E P(L
tc E B
p-lP(EonE)= soE M
3 so e
so e (C' C, -M)C*
B is prefur
closed, the second condition of observability is obviously satisfied. Exchange
of s and t stillhave B observable.
Together, case 1 to case 4 imply that B E C O ( L ) . Next we prove that B is
As a result of case 1, case 2 and sa E L(G) ,soE B . Since
infimal language containing L .
5. B = inf@(L). Assume K a L and K is prefvr closed, controllable and
observable. Since L # 4 , then K f 4 and K E @ ( L ) . So it is enough to
prove B E K . Contrarily, take K c B but K # B , then since K ,B are
prefix closed and nonempty, there must be some s E C' and o E C such that
s o E B but s o e K .Without loss of generality, we may assume s E K but
Case 1:
=j SQ
Case 2:
AS^ E L(G)
nL(G)3so E
3 so e(C'C,
a s E K A Q E C,
so E L(G) A SQ e (C' C, - M ) C *
so E A4
so E P-'P(LQnL ) ~ ( s aE) P(ZO n1)
(3t)toE tA P ( S )= P(t) (3t)toE K A P ( S ) = p ( t )
By definition of observability, we have so E K .
In both case 1 and case 2, so E K contradicts the assumption, which implies
Controllable & Observable Sub-language & Synthesis of Its Supervisor
that K c B and K f B are incorrect. Therefore, B E K .
Lemma 2: B =(L(G)-C*C , C * ) u ( L ( G ) n P - ' ( P ( z C ,nz))C*)
Proof: Let A , = C*C, C', A, = P-'(P(LC,
nz)),then by Proposition 1,
B = L( G)- ( A , - A, C' nA, ) = L( G)n[ A , ( A , C' nA, )"I'
where (0)' is a cut set of C' .With set computation, the result above can be checked
Proposition 2: If L(G) and L are regular languages, then the algoritbm is effective.
Proof Since the set of regular languages is closed under intersection, concatenation,
union and set difference, and because L(G) and L are regular languages and is
finite, then
L(G)- C' C,
= L(G)n(C'
C, 1')'
is regular. By Lemma 2,we can demonstrate that B is a regular language too. So we
can find a finite state automata to recognize B . Therefore, B is computable.
Illustrative Examples
The correctness of results shown above can be illustrated by the following two
Example 1. Consider the plant G and the minimally adequate language A and legal
language A given in Figure 1, where
all the states can be marked.
In Figure 1, we have:
L(G) = ( a + /?)(a
+ /?)',A
= {a,P,y } ,
c, = {a,y } , c, = { p }, and
- -
&,E = (a/?+ /?a)y+ a 2+/?'
Figure 1. Simple system and its legal language.
Y. Wenjunand S.Weinong
Since the empty string E E A but EB flL(G) P 7 ,so A is uncontrollable. Similarly,
we claim that
A is unobservable. Since A # 9 , infCO(L) is computable. Since
L ( G ) - ( C ' C , - M ) z ' = ~ + a + a p + a p y + ~ + j ? therefore
+ p 2 . It is easy to check that B
A c_ B E E . Moreover, since
B =
is prefur closed, controllable, observable and
4 # A # B # E # L(G)
it indicates that the solution is nonvacuous and there exists a suitable supervisor.
Similarly, the above example serves as a nonvacuous illustration of the results
presented in this paper.
Example 2. If A, E is not prefix closed and A E E c_ Lm(G) . In the above example,
let A = a p y ,E = a p y + a 2 + p 2 , Q m = {q1,q2},then
Lm(G)=a$y+pay+P2+a2 + a 2 y + p 2 y
Obviously, A = 2 nLm( G ) ,E = B nLm( G ) . Therefore,
A c_ infCO(A) c E
By Theorem 3, the supervisor designed in Example 1 meets A c Lc( Y / G ) E E .
The paper deals with the existing condition of the supervision and the synthesizing
method under partial controllable and observable events, which are the extended
results of [4]. Also, the theorem given in this paper leads to a closed form solution,
and in the meantime, inf CO(A) still has a closed form solution other than sup@( A)
7when A ,E is not closed.
1. Ramadge, P.J., and Wonham.W.M.1987. Supewisory Control of A Class Discrete Event Systems,
SLAM J. Control and Optimization, 1(25), 206-230.
2. Lin, F., and Wonham, W.M.1988. On Observability of Discrete Event Systems, Infor Sci, 44, 173198.
3. Cieslak, R,et al. 1988. Supervisory Control of Discrete Event Systems with Partial Observations,
E E E Trans.on AC., 33(3), 249-260.
4. Lafortune, S. & Chen, E.K..1990. The lnfimal Closed Controllable Superlanguage and Its
Application in Supervisory Control, IEEE Trans.On AC., 35(4), 398405.
Received: 20 October 1999; Accepted a#er revision: 15 May 2000.
Без категории
Размер файла
268 Кб
synthesis, supervisors, language, formulas, observables, controllable, infimal, sub
Пожаловаться на содержимое документа