# 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. Introduction 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 sup@(E) can be seen that some restriction arises in supervisor designed by widened. 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.(yanwj658@mail.hz.zj.cn) 161 Y. Wenjm and S.Weinong subset C, suchthat 0 0 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 observable. 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 @AdW/GkE. 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 . 162 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 nLm(G) 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' where 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 B2L. 1. B is prefix closed. Take Since YG) SO E B .T h e n s a E L(G) and is prefur closed,sEL(G). Also we have se(C*C,-M)C*. Thus,s E B ,i.e. B is prefvr closed. 2. B is controllable. Take SO E t(G),LT E C,, ,s E B, Furthermore, since SLT e 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, then SLT B SLT E L(G) . If o E xu,,,then (C'C, - M I;If LT E C, ,then L = E L 3sc E L n Z SO E p-lp(EonZ) 163 Y. Wenjun and S. Weinong =,so e (C' C,- M ) M (By definition of ). In both cases above, so e (C'C, -M) . Moreover, since so E L(G) by z. 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 SOEB. Case 1: ~EC,,,, then we claim if that s o e ( C * C,-M) is true since so e C' C, .Therefore so e (C*C, - M ) c * . Case 2: if CT E 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 nZ) tc E B 3 p-lP(EonE)= soE M 3 so e (C*C, -M) =j 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 saeK. Case 1: Q EC , =j SQ Case 2: QE AS E EK KC, AS^ E L(G) nL(G)3so E C, ASD E B 3 so e(C'C, = a s E K A Q E C, so E L(G) A SQ e (C' C, - M ) C * -M) 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 164 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 easily. 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 c L(G)- C' 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 examples. 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+/?' 4 Pa$ 92 G 93 Figure 1. Simple system and its legal language. 165 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 ~, infCO(A) + 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 . Conclusions 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. References 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. 166

1/--страниц