Jin DAI,Hai LIN

Department of Electrical Engineering,University of Notre Dame,Notre Dame,IN 46556,U.S.A.

A learning-based synthesis approach to decentralized supervisory control of discrete event systems with unknown plants

Jin DAI,Hai LIN?

Department of Electrical Engineering,University of Notre Dame,Notre Dame,IN 46556,U.S.A.

In this paper,we consider the problem of automatic synthesis of decentralized supervisor for uncertain discrete event systems.In particular,we study the case when the uncontrolled plant is unknown a priori.To deal with the unknown plants,we first characterize the conormality of prefix-closed regular languages and propose formulas for computing the supremal conormal sublanguages;then sufficient conditions for the existence of decentralized supervisors are given in terms of language controllability and conormality and a learning-based algorithm to synthesize the supervisor automatically is proposed.Moreover,the paper also studies the on-line decentralized supervisory control of concurrent discrete event systems that are composed of multiple interacting unknown modules.We use the concept of modular controllability to characterize the necessary and sufficient conditions for the existence of the local supervisors,which consist of a set of local supervisor modules,one for each plant module and which determines its control actions based on the locally observed behaviors,and an on-line learning-based local synthesis algorithm is also presented.The correctness and convergence of the proposed algorithms are proved,and their implementation are illustrated through examples.

Discrete-event systems;Supervisor synthesis;Regular language learning;Controllability;Decentralized control

1 Introduction

The discrete event system(DES)supervisory control theory initiated by Ramadge and Wonham[1,2]has been widely used to model and control large-scale systems,including multi-agent systems,traffic networks and manufacturing systems,see e.g.,[3,4]and references therein.In[1],the notion of language controllability is introduced to propose the necessary and sufficient condition for the existence of a supervisor that achieves a desired controlled behavior for a given discrete event system under the complete observation of events.Whenthe events are not completely observed by the supervisor,an additional condition of observability introduced by Cieslak et al.[5]is adopted for the existence of the supervisor.Since more and more complex systems built up nowadays are becoming physically distributed and networked,such as multi-agent systems and computer networks,a monolithic(centralized)control design that requires the computation of the global plant often suffers from the so called “state-explosion”problem since this computation grows exponentially as the number of components in the plant grow[6];motivated by this fact,the decentralized control architecture of DESs,in which the specification is achieved through the joint efforts of more than one supervisors,has arisen in the study of supervisory control problems and has attracted many researchers’interest,see e.g.[7–9].

Lots of efforts have been devoted to the research of decentralized supervisory control problems.In[10]a sufficient condition for the existence of decentralized supervisors that the controlled behavior of the system lies in a given range expressed by local specifications was proposed.Cieslak et al.[5]considered the decentralized control where the specification is given as a prefix-closed regular language,and the property of coobservability was introduced in place of observability and the result was then generalized to the case of nonprefix-closed specification by Rudie and Wonham[8].In[11],Willner and Heymann studied the decentralized supervisory control,except that the system they considered were of concurrent nature.They introduced the notion of language separability and under the assumption thatfor all i≠ j,they proved that the separability and controllability of the specification is a necessary and sufficient condition that guarantees that the decentralized control can achieve the optimal behavior achievable by a centralized supervisor.In[12],the authors studied a version of decentralized control problem that is more general than those reported above,and provided a necessary and sufficient condition for the existence of decentralized supervisors for keeping the controlled behavior of the system in a given range.Results of[10]and[11]can be viewed as special cases of[12].

However,most of the existing synthesis algorithms for either monolithic or decentralized supervisors require prior and complete knowledge of the uncontrolled plant.This requirement has been pointed out to be unreasonable[13]in some cases due to the uncertain nature of the plant.The first case is the environment uncertainty,when dealing with online supervisory control problems,it is often impossible to determine when and where the underlined processes are terminated and/or initiated,which implies the time-varying nature of the DES plant to be studied.Second,for large-scale or concurrent systems that are composed of multiple interacting modules,obtaining a precise plant model requires the computation of the compositional behaviors of all the components and hence suffers from the aforementioned state-explosion problem.Third,even though we can obtain a precise DES model before the system is running,if some unknown faults or failures occur during the evolution of the controlled system,which may add unknown transitions and change the controllability and/or observability of the events,we can hardly determine the post-fault modelin an online manner,and then constructing a consistent DES model is impossible.

There have been some studies of the uncertainty of the plant in centralized supervisory control.Lin[14]considered the plant as a set of possible plants and designed robust supervisor applicable for the whole range of plants.In recent years,fault-tolerant control scheme has been proposed to deal with the faults occurring during the evolution of the system.Wen et al.[15]proposed a framework of fault-tolerant supervisory control of DESs,in which the supervisor was designed to ensure the recovery from fault.Liu and Lin[16]investigated the reliable decentralized supervisory control problem of DES under the general architecture,which seek the minimal number of supervisors required for correct functionality of the supervised systems.

This paper differs from the aforementioned work in the sense that we focus on automatic synthesis of decentralized supervisors when the plant is unknown instead of partially known or bounded cases.The contribution of this paper is as follows:first,we propose a sufficient condition for the existence of decentralized supervisor in terms of language controllability and conormality;second,to deal with the uncertain or even unknown nature of the plant,we propose an L?learning based synthesis algorithm where new dynamical membership queries are used instead of static ones in the original learning procedure,and the algorithm can synthesize a sub-optimal decentralized supervisors that are consistent with the supremal controllable and conormal sublanguage of the given prefix-closed specification language;third,wegoonestep further and study the decentralized control problem of concurrent systems,and modular synthesis algorithm for the local supervisors is proposed.

The remainder of this paper is organized as follows.Section 2 briefly reviews the result of decentralized supervisory control theory.The background information about L?learning procedure is presented in Section 3.The discussion about language conormality and the sufficient conditions for the existence of decentralized supervisor based on conormality are given in Section 4.The modified L?learning algorithm for supervisor synthesis is provided in Section 5.Necessary and sufficient conditions for the existence of local supervisors for concurrent discrete event systems are discussed in Section VI,along with the synthesis algorithm for local supervisors.At last we provide concluding remarks and discuss the future work.

2 Notions and preliminaries

This paper discusses the supervisory control framework for discrete event systems that is developed by Ramadge and Wonham[1,2].For the readers’convenience,some background results from the cited references are first provided in this section.For a detailed introduction of the theory,readers may refer to[3,4].

An uncontrolled system,called a plant,is modeled by a deterministic finite automaton(DFA)G=whereis the set of events,Q is the set of states,q0∈Q is the initial state,is the set of marked states,δ is the(partial)transition function.Let Σ?denote the set of all finite strings over Σ plus the null string ∈,then δ can be extended toin the natural way.The language generated by G is given by{is defined}and the language marked by G is given byThe prefix closureˉK of a languageis the set of all prefixes of strings in K.K is called prefix-closed if K=ˉK.

In supervisory control theory,the event set are partitioned into the set of controllable events and the set of uncontrollable events,i.e.,A supervisor S is a pair(R,ψ)where R is a DFA which recognizes a language over the same event set as G,and ψ is a feedback map from the event set and the states of R to the set{enable,disable}.If X denotes the event set of R,thensatisfies ψ(σ,x)=enable if σ ∈ Σuc,i.e.,the supervisor can only disable the occurrences of controllable events.R is considered to be driven by the strings generated by G,and in turn,at each state of R,the control policy ψ(σ,x)makes the decision about the occurrence of event sigma at the corresponding state of G.The behavior of the supervised system(a.k.a.,closed-loop system)is represented by a DFA S/G.The language generated by the closed-loop system is denoted by L(S/G)and its marked languageis given byIt is worth noting that,for regular language cases,the control exercised by such a supervisor for a plant G is equivalent to the behavior of another automaton S that runs in parallel with G and at each state of G disables a subset of the controllable events,if S is a sub-automaton of G.Therefore,L(S/G)=L(S||G)andwhere “||”stands for the parallel composition of two automata[4].Given a non-empty prefix-closed specificationa supervisor S exists such that L(S||G)=K if and only if K is controllable,i.e.,If not,then a supervisor is synthesized to achieve the supremal controllable(also prefix-closed)sublanguage of K,namely,supC(K).

Moreover,the supervisor may also be constrained to observe only events in a specified set of observable events and the event set is then divided in to the subset of unobservable and observable events,i.e.,The presence of partial observation can be captured by the natural projection mappingthat erases the occurrence of all unobservable events.A prefix-closed language K?L(G)is said to be observable if the conditions s,t∈ˉK,σ∈Σ,P(s)=P(t),sσ∈ˉK,and tσ∈L(G)togetherimplytσ∈ˉK[17].Givenanon-empty prefix-closed specification K?L(G),a supervisor S exists such that L(S||G)=K if and only if K is controllable and observable[3].

Fig.1 Decentralized control architecture[3].

Let In(σ)={i ∈ I|σ ∈ Σi,c}denote the index set.A language K?L(G)is said to be

·C&P coobservable with respect to A ? Σc[7]if for any s∈ˉK and any σ∈A such thatthen there exists i∈In(σ)such that:for any

·D&A coobservable with respect toif for anyand any σ∈A such thatthen there exists i∈In(σ)such that:for any

Remark 1The terms“C&P”and“D&A”in the definition of coobservability stands for“conjunctive architecture and permissive decision rule”and “disjunctive architecture and anti-permissive decision rule”,which corresponds to an“AND”and“OR”fusion rule in Fig.1,respectively.In general,we may use “coobservability”when the considered language is either C&P or D&A coobservable.

Let us firstintroduce a motivating example to illustrate the problems to be solved in this paper.

Example 1Consider a multi-robot system that consists of two Pioneer3-DX robots,one with an automated robotic arm and the other is equipped with a gripper,as shown in Fig.2,respectively.

The working procedure of the two robots is depicted in Fig.3.Robot 1 starts from its “home”Home 1,and grabs some parts from Workstation 1,and then transports the parts to Workstation 2 along the Rails 1 and 3.Once the parts are processed by Workstation 2,Robot 2,which starts form Home 2,will pick them up and transport them between Home 2 and Workstations 1 and 2 along the Rails 2 and 3.Rails 1,2 and 3 are all bidirectional.

Fig.2 Robot 1 with a robotic arm and Robot 2 with a gripper.

Fig.3 Multi-robot coordination system.

The control specifications for the two-robot system are

·Robot 2 shall pick up a part delivered by Robot 1 after it has been processed at Workstation 1.

·Since the rails are bidirectional and since Rail 3 is shared by the two robots,the two robots cannot be on Rail 3 at the same time.

For i∈ I={1,2},define αi3and α3ito be the events representing that Robot i is transporting from Rail i to Rail 3 and back from Rail 3 to Rail i,respectively.Then,the local event sets areandWithout loss of generality,we assume that all the local events are locally controllable,i.e.,From above,the specification for the two robots is given byand a DFA that recognizes K is given as follows:each robot is only partially given(with respect to the movement along the given rails),and one possible motion model pair(not unique representation)is given as follows,we have to design decentralized(local)supervision rules for each robot such that K can be fulfilled by the joint work of Robots 1 and 2.

Note that the whole plant model of the motion of

Basedon this example,there arises two problems naturally:first,whether or not we can synthesize the decentralized supervisors for each robot such that the specification is achieved;second,if the answer to the first problem is positive,then whether or not we can compute the local supervisors based only the local events and avoid the computation of the behaviors G1||G2so that the complexity can be reduced.After the discussion in Sections 5 and 6 we will revisit this illustrative example.

Formally,in this paper,we aim at solving the problem that given a non-empty prefix-closed specification K?L(G),find the decentralized supervisors Sisuch thatwith no prior knowledge of G,and we expect to apply a modified L?learning method.

3 L?learning

In this section,we briefly introduce the background information of the L?algorithm for regular language learning,which plays an important role in the derivation of our supervisor synthesis algorithms.The L?learning algorithm introduced by Angluin[18]and improved by Rivest and Schapire[19]learns an unknown regular language U over alphabet Σ and produces a minimal deterministic finite automaton(DFA)that accepts it.The algorithm infers the structure of the DFA by asking an oracle that answers two types of queries.The first type is a membership query,in which L?asks whether a string s∈ Σ?is included in U.The second type is a conjecture,in which L?constructs a conjectured DFA M and asks whether M is such that L(M)=U.If L(M)≠U the oracle returns a counterexample,which is a string s in the symmetric difference of L(M)and U.At any given time,L?has,in order to construct the conjectured DFA M,information about a finite collection of strings over Σ,classified either as members or non-members of U.L?creates an observation table to incrementally record and maintain the information whether strings in Σ?belong to U.The observation table is a three-tuple(S,E,T)consisting of:a non-empty finite set S of prefix-closed languages,a non-empty finite set E of suffix-closed languages and a function T:(S∪SΣ)E → {0,1}which is often referred to as the membership oracle,i.e.,the function T takes strings in s∈(S∪SΣ)onto 0 if they are not in K,otherwise the function T returns 1.

The ith observation table constructed by L?will be denoted as Ti.Each table can be depicted as a 2-dimensional array whose rows are labeled by strings s∈S∪SΣ and whose columns are labeled by symbols σ∈E.The entries in the labeled rows and columns are given by the function value T(sσ).The row function row:(S∪SΣ)→ {0,1}|E|denotes the table entries in the row labeled by string s∈S∪SΣ.

An observation table(S,E,T)is said to be

·closed if for all t∈ SΣ,there exists an s∈ S such that row(t)=row(s);

·consistent if there exist strings s1,s2∈S such that row(s1)=row(s2),and for all σ ∈ Σ,row(s1σ)=row(s2σ);or

·complete if it is closed and consistent.

Once the observation table is complete,a candidate DFA M(S,E,T)=(Q,q0,δ,Qm)over the alphabet Σ is constructed isomorphically by the following rules:

The L?learning algorithm learns the target unknown regular language in the following manner[18]:

Algorithm 1(L?learning algorithm)[18]

Set S= ∈and E= ∈.

Use the membership oracle to form the initial observation table Ti(S,E,T)where i=1,

whileTi(S,E,T)is not completeddo

ifTiis not consistentthen

find s1,s2∈S,σ∈Σande∈Esuchthatrow(s1)=row(s2)

add σe to E;and

extend Tito(S∪SΣ)E using membership queries to the

oracle.

end if

if Tiis not closedthen

find s1∈ S,σ ∈ Σ such that row(s1σ)is different from

row(s)for all s∈S;

add s1σ to S;and

extend Tito(S∪SΣ)E using membership queries to the

oracle.

end if

end while

Once Tiis complete,let Mi=M(Ti)as the conjectured acceptor of K.

Ask the oracle the validity of Mi.

ifthe oracle declares that the conjecture to be false and a counterexample t∈ Σ?is generatedthen

add t and all its prefixes into S;and

extend Tito(S∪SΣ)E using membership queries to the

oracle.

end if

Set i=i+1 and return towhileuntil the oracle declares that the conjecture is true.

returnMi.

The DFA M is presented as a conjecture to the oracle.If the conjecture is correct,i.e.,L(M)=U,then the oracle returns “True”with the current DFA M;otherwise,a counterexampleis generated by the oracle.The L?algorithm analyzes the counterexample cand finds the longest prefix cpof cthat witnesses the difference between L(M)and U.Adding cpto S reflects the difference in next conjecture by splitting states in M.Once cpis added to S,L?iterates the entire process to update M with respect to cp.

The L?algorithm is guaranteed to construct a minimal DFA accepting the unknown regular language U using onlymembership queries and at most n?1 equivalence queries,where n is the number of states in the final DFA and m is the length of the longest counterexample provided by the oracle when answering equivalence queries[18].

4 Decentralized control based on conormality

In this section,we study the decentralized supervisory controlproblem of discrete eventsystems with partial observations,which is first introduced in[10].Furthermore,we generalize the setting of[10]by relaxing the assumption that the local event set Σiis the union of local controllable events Σi,cand local observable events Σi,o,which is clearly restrictive since in many systems,there may exist events that are neither locally controllable nor locally observable.

We start from the notion of language decomposability introduced by Rudie and Wonham[8],which plays an important role in decentralized supervisory control theory.

In general,decomposability is stronger than coobservability,i.e.,a language K is decomposable implies that K is also coobservable.However,under certain conditions of decentralized local control[8],decomposability and coobservability are equivalent.

The following lemma lays the foundation of the necessary and sufficient conditions for the existence of decentralized supervisors in terms of language decomposability.

Lemma1[12]Let G be a plant,Σ be the global event set and Σi? Σ be the local event sets associated with natural projection Pi,i∈I.A language K?L(G)is decomposable(with respect to G and{Pi}i∈I)if and only if there exists a group of languagessuch that

Remark 2If we extend L(G)= Σ?,then the condition for language decomposability in view of Lemma 1 is reduced to the existence ofthat satisfieswhich is exactly the property called language separability in[11],and will be discussed in Section 7.

Based on Lemma 1,the following theorem provides a necessary and sufficient condition for the existence of decentralized supervisors based on language decomposability.

Theorem 1[12] Let G be a plant,Σ be the global event set,and Σi? Σ,i∈ I be the local event sets.Let Pibe the natural projection from Σ to Σi.Then,for a given non-empty,prefix-closed specification languagedecentralized(local)supervisorsexist such thatif and only if

According to Lemma3.2in[11],when the global plant is of concurrent nature,then if the control specification K?L(G)is prefix-closed and controllable(with respect to Σucand L(G)),Pi(K) ? Pi(L(G))and Pi(K)is also prefix-closed,and controllable(with respect to Σi,ucand Pi(L(G))).In general,we can have the following corollary from Theorem 1.

Corollary 1Let G be a plant,Σ be the global event set,and Σi? Σ,i∈ I be the localeventsets.LetPibe the natural projection from Σ to Σi.Then,for a given nonempty,prefix-closed specification language K?L(G),decentralized(local)supervisors{Si,i∈I}exist such thaif and only if K is Σuc-controllable and{Pi}i∈I-decomposable.

When the given specification K is not controllable or decomposable,a supervisor synthesis problem arises that we need to find decentralized supervisors to achieve a controllable and decomposable sublanguage of K.However,it has been pointed out that decomposability is not closed under unions[9],hence it is not guaranteed that the set of controllable and decomposable sublanguages of a given prefix-close language contains a unique supremal element,which implies that no optimal solution(in the sense of maximal permissiveness)exists for the decentralized supervisory control problem.An alternative option to obtain a sub-optimal solution takes advantage of the following conormality property.

The following theorem provides a sufficient condition for the existence of decentralized supervisors in terms of conormality.

Theorem 2Let G be a plant,Σ be the global event set,and Σi? Σ,i∈ I be the local event sets.Let Pibe the natural projection from Σ to Σi.Then,for a given non-empty,prefix-closed specification language K ? L(G),if K is Σuc-controllable and{Pi}i∈I-conormal,then there exist decentralized supervisors{Si,i∈I}such that

ProofSince conormality always implies coobservability[8],then the existence of decentralized supervisors can be further guaranteed by controllability and prefix-closedness.

It is proved that conormality is preserved under arbitrary unions and is a stronger property than coobservability[8,9].Since controllability and prefix-closedness of regular languages are also preserved under union,which implies that the supremal prefix-closed,controllable and conormal sublanguage of a given prefix-closed language K,denoted as supCCN(K),does exist.

Note that for a non-empty,prefix-closed language K?L(G),the supremal normal language of K with respect to L(G)and projection P,denoted as supN(K),can be computed using the following formula[3]:

Based on(1),we propose the following formula for the computation of supremal conormal language of a given language K with respect to{Pi}i∈I,denoted as supCN(K).

Theorem 3For a language K?L(G),the supremal conormal sublanguage of K is given by

ProofThe proof of Theorem 3 follows immediately the proof of the correctness of equation(1)in[3],with

5 Applying L?learning for the synthesis of decentralized supervisors

In the previous work of Yang et al.[20,21],they applied L?-based algorithm for supervisor synthesis,and in their framework,the knowledge of the plant behaviors is confined to a limited lookahead window,which was first introduced by Chung and Lafortune[13].However,this assumption is difficult in realization.Due to this drawback of the limited lookahead windows,in this section,we derive a modified L?learning algorithm to synthesize the supervisor with an totally unknown plant model.

RecallthatalanguageK iscontrollableifˉKΣuc∪L(G)?ˉK,therefore it is difficult to verify the controllability of the given specification language due to lack of knowledge of the plant,hence modification to the existing L?learning procedure is required.We solve this difficulty by using dynamical membership queries that is capable of learning the supremal controllable sublanguage of the given specification(note that since the specification language is prefix-closed,its supremal controllable sublanguage is also prefix-closed),and hence a supervisor is synthesized.

5.1 Learning for controllability

We start from solving the following basic centralized supervisor synthesis problem(BSSP),and next we will take advantage of the results and apply them for decentralized supervisor synthesis.

Problem 1Given non-empty,prefix-closed specification language K?L(G),with the unknown plant G,find a supervisor S such that L(S||G)=supC(K),where supC(K)is the supremal controllable sublanugage of K.

We aim at solving BSSP by modifying the L?membership queries and counterexample classes so that it can learn supC(K)of a given prefix-closed specification K.

A string s generated by G is said to be legal with respect to Kifs∈K,and s is said to beillegal if s ?K.In this paper,the dynamical membership queries presented to the oracle in the modified L?is based on the observed illegal behaviors generated by the system along with the given specification language.A plant behavior st∈ Σ?is said to be uncontrollably illegal if s is legal,and st?K.Let C denote the collection of observed uncontrollably illegal behaviors.We define the operator

for C to represent the collection of the strings formed by discarding the uncontrollable suffixes of strings in C,and let Cidenote the set of uncontrollably illegal behaviors after the ith iteration,then if a new uncontrollably illegal behavior si(a new counterexample)is generated by the oracle,we update Cito.Finally,we propose the following membership oracle Tifor i∈N.For t ∈ Σ?,let T(t)denote the membership Boolean function,initially,

For i＞1,

Note that different from conventional L?discussed in Section 3,the dynamical membership queries used in(3)and(4)are dynamical.

The L?-based synthesis algorithm for BSSP is given as Algorithm 2.

Algorithm 2(L?synthesis algorithm for BSSP)

Set S= ∈and E= ∈.

Use the membership oracle to form the initial observation table Ti(S,E,T)where i=1,

whileTi(S,E,T)is not completeddo

ifTiis not consistentthen

finds1,s2∈S,σ∈Σande∈Esuchthatrow(s1)=row(s2)

but T(s1σe)≠ T(s2σe);

add σe to E;and

extend Tito(S∪SΣ)E using membership queries(3)and(4).

end if

ifTiis not closedthen

find s1∈ S,σ ∈ Σ such that row(s1σ)is different from

row(s)for all s∈S;

add s1σe to S;and

extend Tito(S∪SΣ)E using membership queries(3)and(4).

end if

end while

Once Tiis completed,let Mi=M(Ti)as the acceptor;make the conjecture that Miis the correct supervisor,

ifthe counterexample oracle declares that the conjecture to be false and a counterexample(illegal behavior)t∈ Σ?is generatedthen

add t and all its prefixes into S;

update Tito Ti+1by using the counterexample t;and

extend Tito(S∪SΣ)E using membership queries to the oracle;

end if

Set i=i+1,reset the conjectured supervisor and return towhileuntil the oracle declares that the conjecture is true.

returnMi.

Next,we establish the convergence and correctness properties of the Algorithm 2 by construction.

First,the following lemma is presented to give an iterative method to compute supC(K).

Lemma 2If K and L(G)are regular languages,then supC(K)can be computed iteratively as the following[4]:

If there exists m∈N such that Km+1=Km,then supC(K)=Km.

Compare(5),(6)with the dynamical membership oracle Ti(t)in(3)and(4).Initially,T1(t)is consistent with K1=K;and when the iteration step i≥2,the counterexamples occur and form the set C.We use the operator Du(C)to compute the languages formed by discarding the suffixes made up with uncontrollable events of strings in C,then at the ith step of the iteration,we obtain the result in the form ofOn the other hand,if K is prefix-closed,then Lemma 1 suggests that supC(K)is also prefix-closed,and the iterations(5)and(6)can be reduced to

When the iteration step i goes up until no more counterexamples are generated from the counterexample oracle(provided that the algorithm is convergent),the collection{Ci}will eventually equal to L(G)?K,which is the collection of all the illegal strings and hence the collection of all the potential illegal strings.At the ith step,the result we obtain is

which coincides with the results obtained in(6)and is indeed supC(K).

Next,we will show that by using the L?with the dynamical membership queries given in(3)and(4),the learning procedure will converge within a finite number of iteration steps.To illustrate the finite convergence and correctness of Algorithm 2,we first introduce the following two lemmas.

Lemma 3Assume that the observation table(S,E,T)is closed and consistent and suppose that the corresponding acceptor,M(S,E,T),has n states.Then,for any other acceptor M′that is consistent with T that has n or fewer states,M′is isomorphic to M[18].

Lemma 4Assume that the observation table(S,E,T)is complete and that the corresponding acceptor M(S,E,T)has n states.If a string s∈ Σ?is a counterexample and is added to update M(S,E,T)using Algorithm 1.Assume that the updated and completed observation table is(S′,E′,T′)with the corresponding acceptor M′,then M′must have at least(n+1)states.[20]

There are two kinds of “counterexamples”that are used the modified L?:counterexamples used to complete observation table Tiand counterexamples generated by the counterexample oracle to update the new observation table Ti+1.We denote D as the set of those“counterexamples”that are used to complete Tiafter a new illegal string s is detected and added to update S of the current observation table(S,E,T).

Consider the complete observation table T=(Sj,Ej,Ti)associated with the acceptor M(Sj,Ej,Ti)=M,where Sjand Ejare the pre-defined S and E after the jth counterexample from D has been added to make T complete,and Tidenote the current membership oracle after i times of iterating Algorithm 2.Let nijdenote the number of states of M,nidenotes the number of states of the acceptor of Ti,and n↑denotes the number of states of the acceptor M(supC(K)).Then,by Lemmas 2 and 3,we know that{ni}and{nij}are both monotonically increasing sequences(with respect to i and j,respectively)and nij≤nifor any fixed i and all j∈N.Hence,we can conclude that by using L?learning procedure,the iterations using membership oracle(3)and(4)are convergent.The following theorem summarizes the correctness and convergence properties.

Theorem 4Assume that K?L(G)is prefix-closed,then the modified L?learning procedure using membership queries(3)and(4)converges to a supervisor S,such that L(S||G)=supC(K).Furthermore,this iteration procedure of synthesizing S will be done in a finite number of counterexample tests.

5.2 Learning for conormality

5.2.1 Justification of conormality

We now consider using L?to learn supCCN(K).To compute supCCN(K)using L?learning procedure,we first consider how to deal with the conormality and local observation projections.For j≥1,define recursively

5.2.2 Modi fied membership queries

To capture the illegal behavior generated by the unknown plant under partial observations in the decentral-ized control structure,we modify C in previous section to be

Then,we define the following membership queriesas follows:

The algorithm of supervisor synthesis is summarized as Algorithm 3.

Algorithm 3(L?for learning supCCN(K))

Set S= ∈and E= ∈.

Use the membership oracle to form the initial observation tablewhere j=1,

whileis not completeddo

find s1,s2∈S,σ∈Σoand e∈E such that row(s1)=row(s2)

add σe to E;and

and(13).

end if

ifis not closedthen

find s1∈ S,σ ∈ Σosuch that row(s1σ)is different from

row(s)for all s∈S;

add s1σe to S;and

extend?Tjto(S∪SΣ)E using membership queries(12)

and(13).

end if

end while

ifthe counterexample oracle declares that the conjecture to be false and a counterexample(indistinguishable behavior)is generatedthen

end if

if the counterexample oracle declares that the conjecture to be false and a counterexample(illegal behavior)t∈ Σ?is generatedthen

add P(t)and all its prefixes into S;and

end if

Set i=i+1,reset the conjectured supervisor and return towhileuntil the oracle declares that the conjecture is true.

returnMi.

Let Sibe a DFA over Σisuch that L(Si)=Pi(Mn),then the obtained Si,i∈I are the decentralized supervisors.

5.2.3 Correctness and convergence

The following theorem states the convergence and correctness of the modified L?by using membership queries(12)and(13).

Theorem5LetK?L(G)be a non-empty and prefixclosed specification,then L?with dynamical membership queries(12)and(13)converges to decentralized supervisors Si,i∈ I,such thatFurthermore,this iteration procedure of synthesizing S will be done in a finite number of counterexample tests.

ProofThe convergence property of Algorithm 3 can be shown using the similar approach of Theorem4andis omitted here.We show that the obtained language from Algorithm 3 is supCCN(K).First,we claim that the obtained languageis conormal,which can be proved by contradiction.For the ith step of iteration,assume thatis not conormal,then there exists a stringand another string t∈ L(G)such thatbutthen by the definition of Ccn(K),it is clear to find that s∈Ccn(Ki)and should be eliminated fromThus we get the contradiction andis a conormal and so isNext,we show thatIn fact,by comparing dynamical membership queries(12)and(13)with(3)and(4),respectively,we alternatively compute the supremal conormal sublanguage and the supremal controllable sublanguage in each iteration,hence it is clear to show that the obtained language

5.2.4 Illustrative example

The effectiveness of Algorithm 3 is illustrated through the following simple example.

Example 2Consider the global event set Σ ={α,β,γ}.The local controllable events and observable events are given byand Σ2,o={β},respectively.The specification is given asand the language generated by the plant is Note that L(G)is notknown to the supervisors.Both L(G)and K are depicted as follows:

We start from the first observation table,and set S=E={∈}for Algorithm 1.The first complete observation table with its corresponding acceptor is given as Table 1(note that we only care about the rows whose first entries are 1’s).

Table 1 T1in Example.

We detect that the string αββ ∈ M(T1)?P(K1),hence it is a counterexample and we use Algorithm 1 to update and complete the observation table(shown in Table 2).

Table 2 T2in Example.

We use M(T2)as the supervisor to control the plant behaviors,the stringis a counterexample,then we add the prefixes of αδδδ into S and update the observation table to T3(shown in Table 3).

Table 3 T3in Example.

In this case no more counterexamples are detected,and we can conclude that supthe local(decentralized)supervisors can then be obtained such that Si=Pi(supCCN(K)),i=1,2,which are depicted respectively as follows:

6 Local synthesis of the decentralized supervisors

6.1 Discussion and alternation of Algorithm 3

In the previous section,we discuss the synthesis problem for decentralized supervisors,and Algorithm 3 is proposed to illustrate the learning-based synthesis approach in detail.However,the approach adopted by Algorithm 3 still has some drawbacks,and can be illustrated by revisiting the motivating example mentioned in Section 2.

Example 3(Motivating example revisited) For the specificationsince Σc= Σ ={α13,α31,α23,α32},i.e.,all the events are globally controllable,therefore,a monolithic supervisor that drives the globalsystem to achieveK alwaysexists;however,if the local plant model of Robots 1 and 2 are given by the following,then we can find that,by applying Algorithm 3 one shall fail to get a non-trivial(non-empty)solution.

The drawbacks of Algorithm 3 are twofold:

·centralized synthesis for decentralized supervisors:although the synthesis algorithm returns the DFAs that jointly achieve the supremal controllable and conormal sublanguage of the given non-empty,prefix-closed specification K?L(G),the algorithm itself is of centralized nature and uses the information of controllability and observability of all the global events as if it learns a monolithic supervisor.

·conservativeness of the result:Algorithm 3 provides an approach to actively learn supCCN(K)when prior knowledge of the plant is unaccessible;however,as the following proposition implies,supCCN(K)is conservative in some cases.

Proposition 1If K?L(G)is conormal with respect to Σi,i ∈ I,then K is normal with respect to each Σi,respectively.

ProofThe inclusionis always satisfied for any language K?L(G).Therefore,it is sufficient to prove thatIn fact,K is conormal with respect to Σi,i ∈ I implies thatthus,

Intuitively,Proposition 1 states that,if a language K?L(G)is conormal,then it is normal with all the local observation mappings,i.e.,if there exists i∈I such that K is not normal with respect to Pi,then we can conclude that K is not conormal.This proposition implies that all the decentralized supervisors can pass the authority to any single one of them.The following proposition is an immediate corollary of Proposition 1.

Proposition 2For a non-empty and prefix-closed specification language K?L(G),supCCN(K)?supCNi(K)for all i∈I,where supCNi(K)denotes the supremal controllable(with respect to ΣucandL(G))and normal(with respect to Piand L(G))sublanguage of K).

Propositions 1 and 2 provide some insights on the derivation of an alternative approach to obtain a“better”synthesis solution than supCCN(K),and can be implemented by using the following manner.

Step 1Compute supCNi(K)for each i∈I by using the global uncontrollable event set Σucand the local observable events in Σi,o.

Step 2Find supi(supCNi(K))and return it as the solution for the synthesis problem.

For simplicity,we consider the problem of learning supCNi(K)for a fixed i∈I;and one needs to modify the membership queries(12)and(13)in Algorithm 3 to take normality into account.

The following lemma provides an iterative method of computing the supremal normal sublanguage of a given language.

Lemma 5If K?L(G),then the supremal normal sublanguage of K with respect to Σi,o,denoted as supNi(K),can be obtained using the following iteration[4]:

If there exists m∈N such that Km+1=Km,then Km=supNi(K).

Now that if K is prefix-closed,so is supNi(K).There-fore,the iteration in(14)and(15)can be reduced to

To compute supNi(K)using L?learning procedure,similar to Ccn(·),we define

to denote the collection of “l(fā)ocally indistinguishable”(with respect to Piand K)behaviors generated by the controlled plant.Moreover,we define the modified C to be

Then,for the partial observed plant,we define the following membership queriesas follows:

If t∈Co(Kj),remove t from Kjto obtainthen,

When we use Algorithm 3 as the supervisor synthesis algorithm except that we use membership queries(20)and(21)to replace(12)and(13),respectively,the following theorem guarantees that the resulting learning procedure can still converge to supCNi(K)for a fixed i∈I within a finite number of iterations.

Theorem 6Assume K?L(G)is non-empty and prefix-closed,then the modified L?learning procedure in Algorithm 3 by using membership queries(20)and(21)for each i∈I converges to a local supervisor Si,such that L(Si||G)=supCNi(K).Furthermore,this iteration procedure of synthesizing Siwill be done in a finite number of counterexample tests.

ProofThe proof of Theorem 6 can be performed in exactly the same way as the proof of Theorem 5,and is omitted here.

6.2 Local synthesis for decentralized supervisors:language separability and online control

Although by using Algorithm 3 with membership queries(20)and(21),one can synthesize decentralized supervisors that can achieve less conservative solutions than supCCN(K)when given specification K.However,Algorithm 3 is still of centralized nature when using membership queries(20)and(21)since it requires the global controllability of all the events;furthermore,Algorithm 3 involves partial observation of local supervisors,which increases the computational complexity(as suggested in[22],in the worst case synthesizing a supervisor under partial observation is an NP-complete problem)and therefore,it is difficult to implement the algorithm in an on-line manner.In this section,we go beyond Algorithm 3 and aim to propose a fully decentralized learning-based algorithm to synthesize local supervisors.In particular,in this section,we assume the global plant is a concurrent discrete-event system,i.e.,where Giis the subplant over the local alphabet Σi,andaccording to Proposition 3.1 in[11].Furthermore,we assume that the local supervisor Sican observe all the local events,i.e.,and that any events shared by more than one local plants agree on the status of controllability,i.e.,

which is equivalent to the condition that the local supervisor Sicontrols all the controllable events that are local,i.e.,[12].Thus,we can conclude that.

As mentioned in Remark 2,language separability introduced by Willner and Heymann[11]plays a key role in decentralized supervisory control of concurrent systems,and is formally defined as follows.

The authors of[11]also pointed out that the verification of language separability can be performed by testing the local projection of the language,which states as follows.

We introduce the concept of modular controllability to characterize the properties of the specification required by Theorem 7.

De finition4Consider the local plant language{Li?and the local uncontrollable eventsa language K ? Σ?is said to be modularly controllable if there existssuch thatand Kiis locally controllable with respect to Liand Σi,uc.

Based on Definition 4 and Theorem 7,it is clear that for a concurrent systemand a prefix-closed specification K?L(G),the local supervisors that can achieve K exist if and only if K is modularly controllable.

From Lemma 3.2 in[11]along with Proposition 3,the following proposition claims the relationship between modular controllability and global controllability.

Proposition 4Ifis modularly controllable,then K is globally controllable with respect to L and Σucand K is separable with respect to

Remark 3Proposition 4 states that,modular controllability is a sufficient condition for the combination of separability and global controllability,i.e.,if a specification can be achieved by the joint work of the local supervisors,it can always be achieved by a centralized monolithic supervisor,as we expect.

Under the assumption that shared events have the same controllability status,modular controllability coincides with controllability and separability combined.This is stated as the following corollary.

Corollary 2Considerwhereandthen K is modularly controllable if and only if K is globally controllable with respect to L and Σucand K is{Σi}separable.

Theorem 7 and Corollary 2 shed light on our development of the algorithm for local synthesis of the supervisors.The following steps can help us to implement the local synthesis procedure.

·Local specification generation:Given the non-empty,prefix-closed global specification language K?L(G),let Ki=Pi(K),as suggested by Lemma 3.2 in[11],

·Check the separability of K:Check whether or not K=||i∈IKi,if so,then K is separable from Proposition 3,otherwise,findsuch thatif no suchexists,then find K′? K such that K′is separable.Set

·Local synthesis:With the local specification Kiand the local controllability information Σi,uc,one can use Algorithm 2 to learn a centralized supervisor Sisuch that L(Si||Gi)=supC(Ki).

·Return the solution:Return Sias the decentralized supervisors.

Since the complexity synthesizing a centralized monolithic supervisor Siunder complete observation by using Algorithm 2 is only polynomial with respect to the number of the states of Siand the length of the counterexample queries as mentioned in Section 3,we can conclude that the aforementioned synthesis procedure can be implemented in an on-line manner.

6.3 Illustrative example

We now apply the aforementioned local synthesis procedure for the motivating example proposed in Section 2.

Example 4(Motivating example revisited(cont’d))For i ∈ I={1,2},define αi3and α3ito be the events representing that Robot i is transporting from Rail i to Rail 3 and back from Rail 3 to Rail i,respectively.Then,the local event sets areand.Without loss of generality,we assume that all the local events are locally controllable,i.e.,From above,the specification for the two robots is given byand a DFA that recognizes K is given as follows:

We start from Step 2,and obtain(initial)local specifications as follows:andwhich are depicted,respectively.

However,we find that K≠K1||K2,which requires us to reconfigure K1and K2.

Consider the two-robot scenario,we assume that each robot has adequate sensors to help detect the which rail the other robot is currently located,however,the two robots cannot control the behaviors of the other’s.Accordingly, Σ1and Σ2are augmented to beandrespectively.Moreover,we set thatIn this case,we obtain the local specifications to bein this case we find that K=K1||K2,which permits us to go one step further.

Now,we apply Algorithm 2 in Section 4 for local supervisor synthesis.It can be learnt by using membership queries(3)and(4)that both K1and K2are locally controllable with the corresponding local controllable events.Therefore,we can find the local supervisors S1and S2to help achieve the global specification K.

7 Conclusions

In this paper,the decentralized supervisory control and synthesis problem with no prior knowledge of the plant is investigated.By using the modified membership queries,the L?can learn the supremal controllabel and conormal sublanguage of a given prefix-closed specification language,and an illustrative example is also provided to show the effectiveness of the proposed algorithm.Moreover,the local synthesis of decentralized supervisors is also investigated,and based on the property of modular controllability,one can learn the local supervisors by using only local information and the specification can also be achieved by the joint work of the decentralized supervisors.Future work will be focused on synthesis problems when the given specification is not prefix-closed or not modularly controllable.

[1]P.J.Ramadge,W.M.Wonham.Supervisory control of a class of discrete event processes.SIAM Journal on Control and Optimization,1987,25(1):206–230.

[2]P.J.Ramadge,W.M.Wonham.The control of discrete event systems.Proceedings of the IEEE,1989,77(1):81–98.

[3] C.G.Cassandras,S.Lafortune.Introduction to Discrete Event Systems.London:Springer,2008.

[4]R.Kumar,V.K.Garg.Modeling and Control of Logical Discrete Event Systems.Boston:Kluwer,1995.

[5] R.Cieslak,C.Desclaux,A.S.Fawaz,et al.Supervisory control of discrete-event process with partial observation.IEEE Transactions on Automatic Control,1988,33(3):249–260.

[6]K.Rohloff,S.Lafortune.On the computational complexity of the verification of modular discrete-event systems.Proceedings of IEEE Conference on Decision and Control.Las Vegas:IEEE,2002:16–21.

[7]P.Kozak,W.M.Wonham.Fully decentralized solutions of supervisory control problems.IEEE Transactions on Automatic Control,1995,40(12):2094–2097.

[8]K.Rudie,W.M.Wonham.Think globally,actlocally:Decentralized supervisory control. IEEE Transactions on Automatic Control,1992,37(11):1692–1708.

[9]A.Overkamp,J.H.van Schuppen.Maximal solutions in decentralized supervisory control.SIAM Journal on Control and Optimization,2000,39(2):492–511.

[10]P.Kozak,W.M.Wonham.Decentralized controland coordination of discrete-event systems with partial observation.IEEE Transactions on Automatic Control,1990,35(12):1330–1337.

[11]Y.Willner,M.Heymann.Supervisory control of concurrent discrete-event systems.International Journal of Control,1991,54(5):1143–1169.

[12]S.Jiang,R.Kumar.Decentralized control of discrete event systems with specializations to local control and concurrent systems.IEEE Transactions on Systems,Man,and Cybernetics–Part B:Cybernetics,2000,30(5):653–660.

[13]S.Chung.S.Lafortune.Limited lookahead policies in supervisory control of discrete event systems.IEEE Transactionson Automatic Control,1992,37(12):1921–1935.

[14]F.Lin.Robust and adaptive supervisory control of discrete event systems.IEEE Transactions on Automatic Control,1993,38(12):1848–1852.

[15]Q.Wen,R.Kumar,J.Huang,et al.A framework for fault-tolerant control of discrete event systems.IEEE Transactionson Automatic Control,2008,53(8):1839–1849.

[16]F.Liu,H.Lin.Reliable supervisory control for general architecture of decentralized discrete event systems.Automatica,2010,46(9):1510–1516.

[17]F.Lin,W.M.Wonham.On observability of discrete-event systems.Information Sciences,1988,44(3):173–198.

[18]D. Angluin. Learning regular sets from queries and counterexamples.Information and Computation,1987,75(2):87–106.

[19]R.L.Rivest,R.E.Schapire.Inference of finite automata using homing sequences.Information and Computation,1993,103(2):299–347.

[20]X.Yang,M.D.Lemmon,P.Antsaklis.Inductive inference of logical DES controllers using the L?algorithm.Proceedings of the American Control Conference.Evanston:American Autom Control Council,1995:3163–3167.

[21]X.Yang,M.D.Lemmon,P.Antsaklis.Inductive inference of optimal controllers for uncertain logical discrete event systems.Proceedings of the IEEE International Symposium on Intelligent Control.New York:IEEE,1995:585–590.

[22]M.Heymann,F.Lin.On-line control of partially observed discrete event systems.Discrete Event Dynamical Systems,1994,4(3):221–236.

15 June 2014;revised 11 July 2014;accepted 11 July 2014

DOI10.1007/s11768-014-4082-2

?Corresponding author.

E-mail:hlin1@nd.edu.Tel.:+1 574 631-5480;fax:+1 574 631-4393.

This work was supported by the National Science Foundation(Nos.NSF-CNS-1239222,NSF-EECS-1253488).

?2014 South China University of Technology,Academy of Mathematics and Systems Science,CAS,and Springer-Verlag Berlin Heidelberg

Jin DAIreceived the B.S.degree from ShanghaiJiao Tong University (SJTU),Shanghai,in 2011,and is currently pursuing the Ph.D.degree in the Department of Electrical Engineering,University of Notre Dame.His research interests include verification and control of event-driven,fault tolerant and resilient systems,formal verification,formal methods and their application in cyber-physical systems and multi-robot systems.E-mail:jdai1@nd.edu.

Hai LINobtained his B.S.degree at the University of Science and Technology Beijing and his M.S.degree from the Chinese Academy of Sciences in 1997 and 2000 respectively.In 2005,he received his Ph.D.degree from the University of Notre Dame.Dr.Lin is currently an assistant professor at the Department of Electrical Engineering,University of Notre Dame.Before returning to his alma mater,Hai has been working as an assistant professor in the National University of Singapore from2006to 2011.Dr.Lin’s teaching and research interests are in the multidisciplinary study of the problems at the intersections of control,communication,computation and life sciences.His current research thrust is on cyber-physical systems,multi-robot cooperative tasking,systems biology and hybrid control.Hai has been served in several committees and editorial board.He is the Program Chair for IEEE ICCA 2011,IEEE CIS 2011 and the Chair for IEEE Systems,Man and Cybernetics Singapore Chapter for 2009 and 2010.He is a recipient of 2013 NSF CAREER award and a senior member of IEEE.E-mail:hlin1@nd.edu.