# Confusion Control in Generalized Petri Nets Using Synchronized Events

Authors: Xiaoliang Chen; Gaiyun Liu; Naiqi Wu; Abdulrahman M. Al-Ahmari; Abdulaziz Mohammed El-Tamimi; Emad S. Abouel Nasr
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

The loss of conflicting information in a Petri net (PN), usually called confusions, leads to incomplete and faulty system behavior. Confusions, as an unfortunate phenomenon in discrete event systems modeled with Petri nets, are caused by the frequent interlacement of conflicting and concurrent transitions. In this paper, confusions are defined and investigated in bounded generalized PNs. A reasonable control strategy for conflicts and confusions in a PN is formulated by proposing elementary conflict resolution sequences (ECRSs) and a class of local synchronized Petri nets (LSPNs). Two control algorithms are reported to control the appeared confusions by generating a series of external events. Finally, an example of confusion analysis and control in an automated manufacturing system is presented.


---

## Body

## 1. Introduction

Fault detection and avoidance through external control are important problems in discrete event systems [1–5]. A fault with the loss of conflicting information in a system should be avoided and controlled, which may lead to incomplete decision-making processes and confused implementation. The features of a fault are called confusions that occur frequently in a system with shared resources when the system is modeled by Petri nets. Petri nets (PNs) are an effective tool to model and analyze discrete event systems. Conflicts in a PN are tied to the competition for limited resources between two or more events, which usually is considered as the information interfaces between the DESs and the human decisions, for example, a switch controlled by humans or a static conflict resolution policy designed by humans [6, 7]. However, not all conflicts can be used for decision-making since frequent interlacements of concurrent and conflicting transitions may lead to the information loss of conflicts. In other words, confusions generate difficulties for resolution of conflicts. It is awkward to determine whether there are conflicts with integrated decision-making information from the reachability graph of a net if it contains confusions.We illustrate the significance of this study on confusions by an example shown in Figure1. The function of a system is concerned with “Recovery” and “Update.” In Figure 1(a), a confusion arises from the interlacement between two concurrent events “Fault alarm” and “Update” and two conflicting events “Recovery” and “Update.” It leads to the fact that “Recovery” cannot fire although it is expected to fire when “Fault alarm” is enabled, which is caused by the concurrent behavior between “Fault alarm” and “Update.” If the behavior is always sequentially involved, that is, “Update,” “Fault alarm,” the conflict between “Update” and “Recovery” may never happen and the “Recovery” is missing. Furthermore, the information of the conflict containing “Recovery” is missing. Figure 1(b) illustrates another confusion in the system. The interlacement between the two concurrent events “Update” and “Ignore” and two conflicting events “Update” and “Recovery” also leads to the loss of “Recovery” since “Recovery” cannot fire when the system concurrently fires “Ignore” and “Update.” Obviously, a system with confusions can cause ambiguous behavior and difficulties in system analysis. Solving the problem of confusion diagnosis means that each detected confusion should be controlled by a reasonable strategy. Hence, this study focuses on detection and control of confusions in PNs.Figure 1
A simplified model of fault recovery: (a) the model at markingM=p1+p2 and (b) the model at marking M′=p1+p4.
(a)
(b)Confusion problems in PNs are first investigated in [8, 9]. Several PN applications in a number of areas such as workflow nets (WF-nets) [10–13], unfolding nets [14, 15], safe marked ordinary nets [16–19], generalized (unsafe) nets [17], and generalized stochastic Petri nets (GSPNs) [20, 21] involve confusions. In this section, a brief survey of the existing studies on confusions is presented.van der Aalst et al. take into account the existence of confusions in WF-nets and show the defects of WF-nets with confusions [10–12]. First, the existence of confusions in a WF-net leads to a nondeterministic workflow process such that its correctness cannot be ensured. A WF-net is said to be correct if it satisfies the two properties “soundness” and being “well-structured,” which is reported by van der Aalst [12]. Every reachable marking of a WF-net can terminate properly if it is sound. A WF-net that is well-structured has a number of nice properties. For example, the soundness of a WF-net can be verified in polynomial time and a sound well-structured WF-net is safe. However, the correctness depends on the existence of confusions in a WF-net. If an acyclic WF-net (no directed cycle in the structure of a WF-net) contains a confusion, it is certainly not sound and well-structured. If a WF-net with cycles contains a confusion, it may not be sound and well-structured. Hence, we cannot determine the correctness of a WF-net if it contains confusions.The study on occurrence nets lies in that the behavior of PNs can be interpreted by branching unfolding semantics [15]. In PNs, the behavior such as sequences, concurrency, conflicts, trails, choices, and alternatives can be described and analyzed by decomposing an occurrence net into substructures given by the node relations associated with the behavior. However, confusions cannot be described by the existing branching semantics. Hence, Smith and Haar consider the independence of events in occurrence nets and the indirect influences among concurrent events in [14, 15]. Furthermore, interference structural conflict clusters are developed in [15] in order to describe confusions, which belong to a kind of the substructures of occurrence nets. In the work of Smith and Haar, confusion detection and control problems are not considered.The work of Bolton [16, 17] involves the detection of confusions in both safe and unsafe nets. Truly concurrent semantics and interleaving semantics for concurrent systems are discussed, which are useful to formalize and illustrate confusions. The main difference between the two kinds of semantics is that the synchronized firing of transitions and the nondeterministic choice among the possible orders of their firing can be distinguished by using truly concurrent semantics and not the interleaving semantics.For example, if two transitionst1 and t2 are in a PN concurrently fire, three transition firing sequences are possible, which are denoted by σ1=[t1t2], σ2=t1t2, and σ3=t2t1, respectively. The physical interpretation of σ1 in a real system is that the two events (represented by transitions t1 and t2) fire simultaneously. In this case, the firing of t1 and t2 is said to be synchronized. On the other hand, firing transition sequences σ2=t1t2 and σ3=t2t1 means that t1 and t2 fire sequentially. In [17], the definition of confusions in safe PNs is extended to unsafe generalized PNs, which depends on the inclusion relations of transition sets of conflicts at two markings. However, confusions in generalized PNs cannot be completely described by the definition in [17] since the transition sets of conflicts may remain unchanged although a confusion occurs in a generalized PN.The approaches for confusion detection in [17] are based on trace theory. Furthermore, Communicating Sequential Process (CSP) model-checker is used to detect confusions. The WF-net of a business procedure is constructed to depict the logical relations among business tasks and to detect potential faults in the procedure. Confusions may occur when the implementation of the WF-net contains the operations of both conflict and concurrency. If a WF-net contains a confusion, its procedure may not be completed or the procedure performing a desired work cannot be constructed. In [13], confusion detection algorithms based on the integer linear programming (ILP) are reported. ILP methods are available owing to the Wf-net features represented in [12]. This work also obtains a conclusion; that is, if an acyclic WF-system contains a confusion, it is certainly not well-structured.ILP methods presented in [13] nether work in safe marked ordinary nets since WF-nets are a subclass of safe marked ordinary nets. In [18], a confusion detection method is developed to capture confusion subnets in a safe marked ordinary net. Furthermore, a PN system must avoid any improper firing order of concurrent transitions by a control method such that the system can be immune to detect confusions. Two confusion online control algorithms are proposed to generate a set of control policies, which can completely avoid the occurrences of confusions [18].Confusion avoidance in a safe marked ordinary net can be considered as a problem to forbid the firing of transitions according to a control specification. The work [19] extends generalized mutual exclusion constraints (GMECs) [22, 23] and proposes a class of constraints with respect to places and enabling degrees (P/E constraints). P/E constraints can be used to design confusion avoidance supervisors by a linear algebra method. However, P/E constraints are unavailable in generalized PNs.Confusions in GSPNs are discussed in [20, 21]. The marking graph of a GSPN is not a stochastic process if the GSPN contains confusions, which implies that continuous-time Markov chains (CTMCs) cannot be used to analyze confused GSPNs. Generally, a classical analytical approach for GSPNs is to assume that the subnets of immediate transitions are confusion-free in order that the analysis can proceed. However, the assumption does not intrinsically solve the problem of confusions since they really exist in GSPNs.In the literature, confusion analysis in generalized PNs is considered in [17] only. Conflict-increasing and conflict-decreasing confusions are defined in unsafe PNs, which are classified according to the change of transition sets of conflicts. However, the definition of confusions in [17] is incomplete and cannot describe all confusions in generalized PNs. On the other hand, the confusion detection method in [18] is also available in generalized PNs owing to the same confusion structures in a safe or a generalized PN. However, the confusion control policies presented in [18] cannot be appropriately enforced since conflict resolution in a generalized PN is related to transition enabling degrees that is not appearing in safe marked ordinary PNs.This study extends the work on confusions in [17, 18] by introducing the concept of information content of conflicts. The behavior of a confusion can be clearly observed by comparing the proposed information content of its conflicts in the confusion subnet.Confusions should be prevented by a control method after captured confusions in a PN. This paper proposes a confusion control strategy in generalized PNs, which is based on external event control in synchronized PNs (synchronized PNs are proposed in [24] and developed in [25–27]) and based on the proposed elementary conflict resolution sequences (ECRSs). A class of synchronized PNs with the control information that is called allowable enabling degrees is introduced, in which external events are featured with desired enabling degrees of transitions and can perform a variety of dependency relations of their execution times. Any external event can be converted into a feedback control structure taking the form of PNs. The control policy refers to a group of static rules imposing restrictions on the enabling degrees and priorities of concurrent transitions in confusions. The control methods in this paper are considered for pure and bounded PNs only.This paper is organized as follows. Section2 introduces PNs, conflicts, concurrency, information content, and confusions in generalized PNs. Section 3 deals with the control problems of confusions. A class of synchronized PNs with allowable enabling degrees and ECRSs is proposed. Conclusions and future work are presented in Section 4.


## 2. Basics of PNs and Confusions

Section2.1 provides the basics of Petri nets involved in the paper. More details can be found in [28]. Section 2.2 introduces conflicts [2] and formalizes concurrency and confusions in generalized PNs.


### 2.1. Basics of PNs

Definition 1.
A generalized PNN is a four-tuple (P,T,F,W), where P and T are finite, nonempty, and disjoint sets. P is the set of places and T is the set of transitions. F⊆(P×T)∪(T×P) is called a flow relation of the net, represented by arcs with arrows from places to transitions or from transitions to places. W:(P×T)∪(T×P)→N is a mapping that assigns a weight to an arc: W(x,y)>0 if (x,y)∈F, and W(x,y)=0 otherwise, where x,y∈P∪T and N={0,1,2,…} is a set of nonnegative integers. A net is self-loop-free (pure) if ∄x,y∈P∪T, f(x,y)∈F∧f(y,x)∈F.The structure of a self-loop-free PN can be represented by its incidence matrix[N], that is, a P×T integer matrix with [N](p,t)=W(t,p)-W(p,t). [N] can be divided into two parts [N]+ and [N]- according to the token flow by defining [N]=[N]+-[N]-, where [N]+ with [N]+(p,t)=W(t,p) and [N]- with [N]-(p,t)=W(p,t) are called input and output matrices, respectively.Definition 2.
A markingM of N is a mapping from P to N. M(p) denotes the number of tokens contained in place p. p is marked at marking M if M(p)>0. (N,M0) is called a net system or marked net and M0 is called an initial marking of N.Multisets or formal sum notations are usually used to denote markings and vectors. As a result, a markingM can be denoted by ∑p∈P‍M(p)p. For example, a marking that has five tokens in place p2 and three tokens in place p4 in a net with four places p1, p2, p3, and p4 is denoted by 5p2+3p4 instead of (0,3,0,2)T.Definition 3.
Letx∈P∪T be a node in a net N=(P,T,F,W). The preset of x is defined as x•={y∈P∪T∣(y,x)∈F}, while the postset of x is defined as x•={y∈P∪T∣(x,y)∈F}. Let X be a set of nodes with X⊆P∪T. We have X•=∪x∈Xx•, and X•=∪x∈Xx•.Definition 4.
A transitiont∈T is enabled at marking M if, ∀p∈•t, M(p)≥W(p,t), which is denoted as Mt. If t is enabled, it can fire. Its firing yields another marking M′ such that, ∀p∈P, M′(p)=M(p)-W(p,t)+W(t,p), which is denoted by MtM′. Marking M′ is said to be reachable from M if there exists a transition sequence σ=t1t2…tn and markings M1,M2,…, and Mn-1 such that Mt1M1t2M2,…,Mn-1tnM′. This is denoted by MσM′. The set of markings reachable from M in N defines the reachability set of (N,M), denoted as R(N,M). A transition t∈T is live at M0 if, ∀M∈R(N,M0), ∃M′∈R(N,M), M′t holds.LetN=(P,T,F,W) be a net and let σ be a finite sequence of transitions. The Parikh vector of σ is σ→: T→N which maps t in T to the number of occurrences of t in σ. Let σ=t1t2t5t2t1t1 be a transition sequence of a net (N,M) with T=5. Its Parikh vector is σ→=(3,2,0,0,1)T.Definition 5.
A generalized PN is bounded if∃k∈N+, ∀M∈R(N,M0), ∀p∈P, M(p)≤k, where N+={1,2,…}.A net which is bounded implies that its reachability set has a finite number of elements. This paper deals with pure and bounded PNs.


### 2.2. Basic Definitions of Conflicts, Concurrency, and Confusions

Definition 6.
A structural conflict in a netN=(P,T,F,W) is a pair K=p,TK, where p∈P is called the structural conflicting place and T(K)={t1,t2,…,tn} is the set of output transitions of p with n=p•≥2. The elements in T(K) are called structural conflicting transitions.Definition 7.
An effective conflict in a marked net(N,M0), denoted by KM=p,TKM,M, is associated with a structural conflict K=p,TK and a marking M∈R(N,M0) such that, ∀ti∈T(KM), Mti is true, and M(p)<∑ti∈T(KM)‍W(p,ti), where T(KM)⊆T(K) is the set of enabled transitions in T(K) at marking M with TKM≥2.Figures2(a) and 2(b) show a structural conflict K=p2,t1,t2,t3,t4 and an effective conflict KM=p2,t1,t2,t3,2p1+2p2 that is associated with the structural conflict K, respectively. Their transition sets can be represented as T(K)={t1,t2,t3,t4} and T(KM)={t1,t2,t3}.Figure 2
(a) A structural conflictK=p2,t1,t2,t3,t4 and (b) an effective conflict KM=p2,t1,t2,t3,2p1+2p2.
(a)
(b)Definition 8.
The enabling degree of a transitionti in a pure net (N,M0) at a reachable marking M∈R(N,M0), denoted by qiM, is an integer such that (1)qiM≤min⁡MpWp,ti∣p∈•ti<qiM+1.A transition ti is said to be qiM-enabled, denoted by MtiqiM, if ti has enabling degree qiM. Note that if ti is 0-enabled, it means that ti is disabled.The enabling degreeqiM of a transition ti at marking M can be considered as the possible maximal number of the firing times of the transition ti at marking M. Let Mi be a reachable marking of a PN and Qi denote the vector of enabling degrees of all transitions at Mi. For example, let t1, t2, and t3 be the transitions in a PN (N,M0) with T=3. If they are 2-, 0-, and 3-enabled at the initial marking M0, respectively, we have Q0=[2,0,1]T.Definition 9.
A general conflict in a marked net(N,M0), denoted by KM=p,TKM,M, is associated with a structural conflict K=p,TK and a marking M∈R(N,M0) such that, ∀ti∈T(KM), Mti is true, and M(p)<∑ti∈T(KM)‍qiM·W(p,ti), where T(KM)⊆T(K) is the set of enabled transitions in T(K) at marking M with TKM≥2 and qiM is the enabling degree of transition ti at marking M.Figure3 illustrates a general conflict KM=p2,t1,t2,t3,2p1+3p2 that is associated with the structural conflict K=p2,t1,t2,t3,t4 at marking M=2p1+3p2. According to Definition 8, we have q1M=2, q2M=3, and q3M=3. In other words, transitions t1, t2, and t3 are 2-, 3-, and 3-enabled, respectively. Hence, we have(2)Mp2=3<q1M·Wp2,t1+q2M·Wp2,t2+q3M·Wp2,t3=8.The number of tokens in p2 does not suffice to fire all the output transitions of p2 according to their enabling degrees. An effective conflict in (N,M0) is also a general conflict according to Definitions 7 and 9. However the reverse is not true. For example, the general conflict KM=p2,t1,t2,t3,2p1+3p2 shown in Figure 3 is not effective since(3)Mp2=Wp2,t1+Wp2,t2+Wp2,t3=3.In this paper, general conflicts are considered in confusions.Figure 3
A general conflictKM=p2,t1,t2,t3,2p1+3p2.LetTc⊆T be a transition set in a net system (N,M0) and let M∈R(N,M0) be a reachable marking. Notation EM(Tc) is used to denote the number of enabled transitions in Tc at marking M. A transition sequence σ is said to be a resolution sequence of the general conflict KM=p,TKM,M at marking M if each transition in T(KM) becomes disabled after firing the sequence σ, that is, MσM′, where the marking M′ is called the output marking of KM by firing σ.A structural conflict in a net system can produce multiple general conflicts owing to different reachable markings. For a structural conflictK=p,TK, the information content of the general conflict KM, denoted by ψ(KM), associated with K at marking M is defined as follows:(4)ψKM=α·∑ti∈TKqiM·Wp,ti,where(5)α=1EMTK≥20otherwiseand, ∀ti∈T(K), qiM is the enabling degree of transition ti at marking M.The general conflicts associated with a structural conflictK can be compared by their information content at markings, which reflects the number of resolution sequences for the general conflicts. Note that α=0 can lead to zero information content; that is, ψ(KM)=0, which implies that K at marking M does not produce any general conflict. A general conflict KM associated with the structural conflict K in a PN (N,M0) is said to have integrated decision-making information if there does not exist another general conflict KM′ associated with K in (N,M0) such that ψ(KM′)>ψ(KM).Letσ=(t)n denote a transition sequence in which the transition t consecutively fires n times and σ=[t1,t2,…,tn] denotes a synchronized transition sequence in which transitions t1,t2,…, and tn fire synchronously; that is, the transitions fire simultaneously. Figures 4(a) and 4(b) show two general conflicts KM=p2,t1,t2,M and KM′=p2,t1,t2,M′ with the same structure at markings M=p1+2p2 and M′=2p1+3p2, respectively. For the former, that is, KM, we have(6)ψKM=q1M·Wp2,t1+q2M·Wp2,t2=3.Furthermore, four feasible resolution sequences σ1=t1t2, σ2=t2t1, σ3=(t2)2, and σ4=[t1t2] can be observed. Similarly, for the latter, that is, KM′, we have(7)ψKM′=q1M′·Wp2,t1+q2M′·Wp2,t2=5.The ψ(KM′)=5 implies that the general conflict KM′ has more resolution sequences than KM, which are σ1=(t1)2t2, σ2=t1t2t1, σ3=t2(t1)2, σ4=t1(t2)2, σ5=t2t1t2, σ6=(t2)2t1, σ7=(t2)3, σ8=[t1(t2)2], and σ9=[(t1)2t2]. Suppose that KM and KM′ are only two general conflicts associated with K in a PN. Then, the general conflict KM′ has integrated decision-making information since ψ(KM′)=5>ψ(KM)=3.Figure 4
(a) A general conflictKM=p2,t1,t2,p1+2p2 with ψ(KM)=3 and (b) a general conflict KM′=p2,t1,t2,2p1+3p2 with ψ(KM′)=5.
(a)
(b)General conflicts provide information for decision-making in generalized PNs. Confusions can cause the information loss. The proposed control strategy of confusions is based on general conflicts and the control objective is to ensure the integrity of decision-making information of the general conflicts.Definition 10.
(1) Transitionst1 and t2 are said to be concurrent at marking M in a marked net (N,M) if Mt1, M[t2〉, and (•t1∪t1•)∩(•t2∪t2•)=∅.
(2) LetDM={t1,t2,…,tn} be a transition set. It is called a set of concurrent transitions at marking M if, ∀ti,tk∈DM, i≠k, transitions ti and tk are concurrent at marking M.
(3) The concurrent degree of a setDM of concurrent transitions, denoted by λ, is defined as λ=DM.
(4) LetDM be a set of concurrent transitions in a marked net (N,M) with λ=DM. It is said to be λ-max-concurrent in (N,M) if there does not exist a set of concurrent transitions D^M≠DM with λ^=D^M in (N,M) such that λ^>λ. A transition in DM is said to be λ-max-concurrent if DM is λ-max-concurrent in (N,M).
(5) LetDM={D1M,D2M,…,DρM} be the set of concurrent transition sets in (N,M). In other words, ∀DjM∈DM, DjM is a set of concurrent transitions in (N,M). DM is said to be λ-max-concurrent if ∀DjM∈DM, DjM is λ-max-concurrent in (N,M).The net shown in Figure5 contains totally seven sets of concurrent transitions at marking M=p1+p4+2p5; that is, D1M={t1,t5}, D2M={t1,t6}, D3M={t2,t5}, D4M={t2,t6}, D5M={t5,t6}, D6M={t1,t5,t6}, and D7M={t2,t5,t6}. According to Definition 10, D6M and D7M with λ6=λ7=3 are 3-max-concurrent since there does not exist a set of concurrent transitions from D1M to D7M, whose cardinality is greater than three. Let D1M={D6M,D7M} and D2M={D1M,D2M,D6M} be two sets of concurrent transition sets. Then D1M is 3-max-concurrent and D2M is not 3-max-concurrent since there exist two sets D1M and D2M, whose concurrent degrees are less than three.Figure 5
Illustration of concurrency.It is denoted byMtnM′ that a transition t∈T consecutively fires n times at marking M, where n≤q1M and M′ is the reachable marking from M by firing tt⋯t︸n.LetTc⊆DM be a subset of concurrent transitions in net N at marking M. Let M′ be the reachable marking from M by firing all transitions in Tc according to their enabling degrees. The fact is denoted by MTcM′. Note that the firing orders of the transitions in Tc are nondeterministic since Tc is a subset of concurrent transitions. For example, if Tc={t1,t2} and two transitions t1 and t2 are 1- and 2-enabled, respectively, at marking M fire, their possible firing sequences, according to enabling degrees, are σ1=t1(t2)2, σ2=(t2)2t1, σ3=t2t1t2, and σ4=[t1(t2)2], where σ1–σ3 are sequential firing sequences; that is, transitions fire consecutively, and σ4 is a synchronized firing sequence; that is, transitions fire simultaneously. Correspondingly, MTcM′ implies Mσ1M′, Mσ2M′, Mσ3M′, and Mσ4M′, where M′ is the reachable marking from M by firing any of the four possible firing sequences of concurrent transitions in Tc.A subnet (structure) of a PNN=(P,T,F,W) is a four-tuple N¯=(P¯,T¯,F¯,W¯), where P¯⊆P, T¯⊆T, F¯=F∩[(P¯×T¯)∪(T¯×P¯)], and, ∀f∈F¯, W¯(f)=W(f). Let m and m′ be positive integers with m′≤m. Given a marked net (N,M) with place set P={p1,p2,…,pm} and its subnet N¯ with place set P¯={pg1,pg2,…,pgm′}⊆P, we denote by M¯ the projection of a marking M∈Nm on N¯.M
¯ is called the submarking of M in N, which is denoted by M¯≺M. It is said to be valid if ∃j∈{g1,g2,…,gm′}, M¯(pj)>0. It is invalid if, ∀j∈{g1,g2,…,gm′}, M¯(pj)=0. Figure 6(a) represents a net system (N,M) with four places p1–p4 and four transitions t1–t4 at marking M=(1,4,1,0)T. A subnet N¯ of N with two places p1 and p2 and two transitions t3 and t4 is shown in Figure 6(b) at the valid submarking M¯=(1,4)T.Figure 6
(a) A generalized PNN at marking M=(1,4,1,0)T and (b) a subnet N¯ of N at submarking M¯=(1,4)T.
(a)
(b)ForN at another marking M′=(0,0,0,2)T with Mt1M1t42M′, the submarking M¯′=(0,0)T for N¯ is obtained, which is invalid since any element in M¯′ is zero.Definition 11.
A confusion, denoted by(N¯,T(K),M¯,DM¯), is a marked subnet (N¯,M¯) in a net system (N,M0) such that(1)
there exists a structural conflictK=p,TK with p∈P¯ and T(K)⊂T¯;(2)
there exists a nonempty setDM¯ that is composed of all 2-max-concurrent transition sets at the submarking M¯ in (N¯,M¯);(3)
∀DjM¯∈DM¯, ∃ti∈DjM¯∖T(K) and ∃k∈{1,2,…,qiM¯} such that M¯tikM¯′ and ψ(KM¯)≠ψ(KM¯′), where ψ(KM¯) and ψ(KM¯′) are information content of general conflicts associated with K at submarkings M¯ and M¯′, respectively;(4)
there exist two reachable markingsM and M′ in R(N,M0) such that M¯≺M and M¯′≺M′ are valid.A confusion is said to be a conflict-increasing confusion (CIC), denoted as Cin(N¯,T(K),M¯,DM¯), if ψ(KM¯)<ψ(KM¯′). It is said to be a conflict-decreasing confusion (CDC), denoted as Cde(N¯,T(K),M¯,DM¯), if ψ(KM¯)>ψ(KM¯′).Definition11 defines confusions as a class of marked subnets in a net system and classifies them into CICs and CDCs. Condition (1) in Definition 11 imposes a requirement on marked subnets. If a marked subnet is a confusion, it necessarily contains a structural conflict. Condition (2) in Definition 11 limits the size of a marked subnet (N¯,M¯) by restricting that all sets of concurrent transitions in (N¯,M¯) are 2-max-concurrent at submarking M¯. The concurrent degree λ=2 in this condition means that there does not exist a set of concurrent transitions, which contains more than two transitions.Condition (3) in Definition11 gives the behavior characteristics of confusions. For any set DjM¯ of max-concurrent transitions in a confusion, the change of information content of general conflicts is caused by the firing of a transition t∈DjM¯ that is not a structural conflicting transition. Condition (4) in Definition 11 ensures that the behavior described in condition (3) can actually occur in the original net system. If condition (4) is not satisfied, confusions cannot occur in the original net system although it may contain the structures of confusions. Confusions are classified into CICs and CDCs according to the change of information content in Definition 11.Example 1.
Figure7(a) shows a CIC Cin(N¯1,T(K1),M¯1,DM¯1), where T(K1)={t1,t2} is derived from the existing structural conflict K1=p2,t1,t2 in N¯1, M¯1=p1+2p2+4p4 is an initial submarking, DM¯1={D1M¯1} is the set of 2-max-concurrent transitions sets, and D1M¯1={t1,t3}.
Figure7(b) shows the partial reachability graph of the CIC, which is generated by concurrently firing transitions t1 and t3 only. In Figure 7(b), any submarking M¯j is considered with the information content ψ(K1M¯j) of the general conflict K1M¯j. The confusion is conflict-increasing since transition t3 can fire twice or four times, which can produce an increment of the information content. We cannot determine whether the general conflicts associated with K1 occur from the initial submarking M¯1 to the submarking M¯10 according to the concurrent firing of transitions t1 and t3.
As depicted in Figure7(b), three general conflicts occur at submarkings M¯3, M¯4, and M¯5 due to ψ(K1M¯3)=2, ψ(K1M¯4)=2, and ψ(K1M¯5)=3, respectively. However, the other submarkings in Figure 7(b) do not produce any general conflict. On the other hand, the general conflict K1M¯5=〈p2,{t1,t2},M¯5〉 at M¯5 is expected to occur since it has the maximal information content ψ(K1M¯5)=3 in Figure 7(b). The submarking M¯5 can be reached by only one path, that is, M¯1t3M¯2t3M¯3t3M¯4t3M¯5, which implies that the transition sequence σ=(t3)4 fires. However, transitions t1 and t3 in Figure 7(a) are concurrent, which implies that the firing orders of t1 and t3 are nondeterministic. The nondeterminism causes that the transition sequence σ=(t3)4 is not guaranteed to be fired. In this case, we can say that the information loss of the general conflict K1M¯5 occurs if a transition sequence fires, which does not pass through the submarking M¯5.Figure 7
(a) A CICCin(N¯1,T(K1),M¯1,DM¯1) with DM¯1=1 and (b) its partial reachability graph obtained by concurrently firing t1 and t3.
(a)
(b)Example 2.
Figure8(a) shows a CIC Cin(N¯2,T(K2),M¯1,DM¯1), where T(K2)={t1,t2,t3,t4}, M¯1=2p1+2p4, DM¯1={D1M¯1,D2M¯1}, D1M¯1={t1,t5}, and D2M¯1={t2,t5}. According to condition (3) in Definition 11, both sets D1M¯1 and D2M¯1 of 2-max-concurrent transitions need to be considered. If transitions t1 and t5 in D1M¯1 concurrently fire, the partial reachability graph shown in Figure 8(b) is obtained. By observing the reachability graph, the general conflict K2M¯3=p1,t1,t2,t3,t4,M¯3 at submarking M¯3=2p1+2p2+2p3 has the maximal information content ψ(K2M¯3)=6. The information loss of the general conflict K2M¯3 occurs if the transition sequence σ1=t5t1t5 or σ2=t1t5t5 fires.
The partial reachability graph shown in Figure8(c) is obtained by analyzing the concurrent firing of transitions t2 and t5 in D2M¯1. The same general conflict K2M¯3 with the maximal information content ψ(K2M¯3)=6 is obtained in Figure 8(c). There exists only one path M¯1t5M¯2t5M¯3 in Figure 8(c), which reaches the submarking M¯3. However, more paths exist in Figure 8(c) than Figure 8(b) from the initial submarking M¯1 to the submarking M¯6 such that the information loss of the general conflict K2M¯3 occurs. In other words, K2M¯3 does not occur if a path in Figure 8(c) does not pass through the submarking M¯3 from M¯1 to M¯6.Figure 8
(a) A CICCin(N¯2,T(K2),M¯1,DM¯1) with DM=2, (b) the partial reachability graph of (a) obtained by concurrently firing t1 and t5, and (c) the partial reachability graph of (a) obtained by concurrently firing t2 and t5.
(a)
(b)
(c)Example 3.
Figure9(a) shows a CDC that consists of two structural conflicts K3=p1,t1,t2 and K4=p2,t2,t3. Only one structural conflict in the confusion is considered due to symmetry. In this example, the structural conflict K3 is focused; that is, the CDC Cde(N¯3,T(K3),M¯1,DM¯1) is analyzed. From Figure 9(a), we have T(K3)={t1,t2}, M¯1=2p1+3p2, DM¯1={D1M¯1}, and D1M¯1={t1,t3}.
Figure9(b) depicts the partial reachability graph of the CDC, which can be obtained by concurrently firing transitions t1 and t3. The maximal information content of general conflicts associated with the structural conflict K3 can be found at the initial submarking M¯1=2p1+3p2; that is, ψ(K3M¯1)=3. Hence, the decisions on conflicting transitions t1 and t2 should be made for the general conflict K3M¯1=p1,t1,t2,M¯1. However, a transition t3∉T(K3) can concurrently fire such that the information content is reduced from ψ(K3M¯1)=3 to ψ(K3M¯4)=0. Consequently, the information loss of K3M¯1 occurs.
On the other hand, firingt1 also reduces the information content, which is not concerned with the information loss since t1 is a structural conflict transition for decisions. The submarking M¯2=p1+3p2+p3 with ψ(K3M¯2)=2 is reached after firing t1 at M¯1, which is also prone to the information loss of the general conflict K3M¯2=p1,t1,t2,M¯2 by firing t3.Figure 9
(a) A CDCCde(N¯3,T(K3),M¯1,DM¯1) with DM=1 and (b) its partial reachability graph obtained by concurrently firing t1 and t3.
(a)
(b)Example 4.
Figure10(a) depicts a CDC with two structural conflicts K5=p1,t1,t2,t3,t4 and K6=p2,t3,t4,t5. Similarly, we consider K5 in the confusion Cde(N¯4,T(K5),M¯1,DM¯1) only, where T(K5)={t1,t2,t3,t4}, M¯1=2p1+p2, DM¯1={D1M¯1,D2M¯1}, D1M¯1={t1,t5}, and D2M¯1={t2,t5}. In this case, the partial reachability graph shown in Figure 10(b) (resp., Figure 10(c)) is obtained by concurrently firing two transitions t1 and t5 (resp., t2 and t5). The confusion is prone to the information loss of the general conflict K5M¯1=p1,t1,t2,t3,t4,M¯1 since firing transition t5 reduces the information content from ψ(K5M¯1)=8 to ψ(K5M¯3)=4 and t5 does not have a structural conflict transition in T(K5).Figure 10
(a) A CDCCde(N¯4,T(K5),M¯1,DM¯1) with |DM|=2, (b) the partial reachability graph of (a) obtained by concurrently firing t1 and t5, and (c) the partial reachability graph of (a) obtained by concurrently firing t2 and t5.
(a)
(b)
(c)Confusion control in a generalized PN means that a reasonable strategy should be constructed to ensure the appearance of the general conflicts with maximal information content and if an output marking of a general conflict is preassigned, the control policy can guarantee the marking to be reachable.


## 2.1. Basics of PNs

Definition 1.
A generalized PNN is a four-tuple (P,T,F,W), where P and T are finite, nonempty, and disjoint sets. P is the set of places and T is the set of transitions. F⊆(P×T)∪(T×P) is called a flow relation of the net, represented by arcs with arrows from places to transitions or from transitions to places. W:(P×T)∪(T×P)→N is a mapping that assigns a weight to an arc: W(x,y)>0 if (x,y)∈F, and W(x,y)=0 otherwise, where x,y∈P∪T and N={0,1,2,…} is a set of nonnegative integers. A net is self-loop-free (pure) if ∄x,y∈P∪T, f(x,y)∈F∧f(y,x)∈F.The structure of a self-loop-free PN can be represented by its incidence matrix[N], that is, a P×T integer matrix with [N](p,t)=W(t,p)-W(p,t). [N] can be divided into two parts [N]+ and [N]- according to the token flow by defining [N]=[N]+-[N]-, where [N]+ with [N]+(p,t)=W(t,p) and [N]- with [N]-(p,t)=W(p,t) are called input and output matrices, respectively.Definition 2.
A markingM of N is a mapping from P to N. M(p) denotes the number of tokens contained in place p. p is marked at marking M if M(p)>0. (N,M0) is called a net system or marked net and M0 is called an initial marking of N.Multisets or formal sum notations are usually used to denote markings and vectors. As a result, a markingM can be denoted by ∑p∈P‍M(p)p. For example, a marking that has five tokens in place p2 and three tokens in place p4 in a net with four places p1, p2, p3, and p4 is denoted by 5p2+3p4 instead of (0,3,0,2)T.Definition 3.
Letx∈P∪T be a node in a net N=(P,T,F,W). The preset of x is defined as x•={y∈P∪T∣(y,x)∈F}, while the postset of x is defined as x•={y∈P∪T∣(x,y)∈F}. Let X be a set of nodes with X⊆P∪T. We have X•=∪x∈Xx•, and X•=∪x∈Xx•.Definition 4.
A transitiont∈T is enabled at marking M if, ∀p∈•t, M(p)≥W(p,t), which is denoted as Mt. If t is enabled, it can fire. Its firing yields another marking M′ such that, ∀p∈P, M′(p)=M(p)-W(p,t)+W(t,p), which is denoted by MtM′. Marking M′ is said to be reachable from M if there exists a transition sequence σ=t1t2…tn and markings M1,M2,…, and Mn-1 such that Mt1M1t2M2,…,Mn-1tnM′. This is denoted by MσM′. The set of markings reachable from M in N defines the reachability set of (N,M), denoted as R(N,M). A transition t∈T is live at M0 if, ∀M∈R(N,M0), ∃M′∈R(N,M), M′t holds.LetN=(P,T,F,W) be a net and let σ be a finite sequence of transitions. The Parikh vector of σ is σ→: T→N which maps t in T to the number of occurrences of t in σ. Let σ=t1t2t5t2t1t1 be a transition sequence of a net (N,M) with T=5. Its Parikh vector is σ→=(3,2,0,0,1)T.Definition 5.
A generalized PN is bounded if∃k∈N+, ∀M∈R(N,M0), ∀p∈P, M(p)≤k, where N+={1,2,…}.A net which is bounded implies that its reachability set has a finite number of elements. This paper deals with pure and bounded PNs.


## 2.2. Basic Definitions of Conflicts, Concurrency, and Confusions

Definition 6.
A structural conflict in a netN=(P,T,F,W) is a pair K=p,TK, where p∈P is called the structural conflicting place and T(K)={t1,t2,…,tn} is the set of output transitions of p with n=p•≥2. The elements in T(K) are called structural conflicting transitions.Definition 7.
An effective conflict in a marked net(N,M0), denoted by KM=p,TKM,M, is associated with a structural conflict K=p,TK and a marking M∈R(N,M0) such that, ∀ti∈T(KM), Mti is true, and M(p)<∑ti∈T(KM)‍W(p,ti), where T(KM)⊆T(K) is the set of enabled transitions in T(K) at marking M with TKM≥2.Figures2(a) and 2(b) show a structural conflict K=p2,t1,t2,t3,t4 and an effective conflict KM=p2,t1,t2,t3,2p1+2p2 that is associated with the structural conflict K, respectively. Their transition sets can be represented as T(K)={t1,t2,t3,t4} and T(KM)={t1,t2,t3}.Figure 2
(a) A structural conflictK=p2,t1,t2,t3,t4 and (b) an effective conflict KM=p2,t1,t2,t3,2p1+2p2.
(a)
(b)Definition 8.
The enabling degree of a transitionti in a pure net (N,M0) at a reachable marking M∈R(N,M0), denoted by qiM, is an integer such that (1)qiM≤min⁡MpWp,ti∣p∈•ti<qiM+1.A transition ti is said to be qiM-enabled, denoted by MtiqiM, if ti has enabling degree qiM. Note that if ti is 0-enabled, it means that ti is disabled.The enabling degreeqiM of a transition ti at marking M can be considered as the possible maximal number of the firing times of the transition ti at marking M. Let Mi be a reachable marking of a PN and Qi denote the vector of enabling degrees of all transitions at Mi. For example, let t1, t2, and t3 be the transitions in a PN (N,M0) with T=3. If they are 2-, 0-, and 3-enabled at the initial marking M0, respectively, we have Q0=[2,0,1]T.Definition 9.
A general conflict in a marked net(N,M0), denoted by KM=p,TKM,M, is associated with a structural conflict K=p,TK and a marking M∈R(N,M0) such that, ∀ti∈T(KM), Mti is true, and M(p)<∑ti∈T(KM)‍qiM·W(p,ti), where T(KM)⊆T(K) is the set of enabled transitions in T(K) at marking M with TKM≥2 and qiM is the enabling degree of transition ti at marking M.Figure3 illustrates a general conflict KM=p2,t1,t2,t3,2p1+3p2 that is associated with the structural conflict K=p2,t1,t2,t3,t4 at marking M=2p1+3p2. According to Definition 8, we have q1M=2, q2M=3, and q3M=3. In other words, transitions t1, t2, and t3 are 2-, 3-, and 3-enabled, respectively. Hence, we have(2)Mp2=3<q1M·Wp2,t1+q2M·Wp2,t2+q3M·Wp2,t3=8.The number of tokens in p2 does not suffice to fire all the output transitions of p2 according to their enabling degrees. An effective conflict in (N,M0) is also a general conflict according to Definitions 7 and 9. However the reverse is not true. For example, the general conflict KM=p2,t1,t2,t3,2p1+3p2 shown in Figure 3 is not effective since(3)Mp2=Wp2,t1+Wp2,t2+Wp2,t3=3.In this paper, general conflicts are considered in confusions.Figure 3
A general conflictKM=p2,t1,t2,t3,2p1+3p2.LetTc⊆T be a transition set in a net system (N,M0) and let M∈R(N,M0) be a reachable marking. Notation EM(Tc) is used to denote the number of enabled transitions in Tc at marking M. A transition sequence σ is said to be a resolution sequence of the general conflict KM=p,TKM,M at marking M if each transition in T(KM) becomes disabled after firing the sequence σ, that is, MσM′, where the marking M′ is called the output marking of KM by firing σ.A structural conflict in a net system can produce multiple general conflicts owing to different reachable markings. For a structural conflictK=p,TK, the information content of the general conflict KM, denoted by ψ(KM), associated with K at marking M is defined as follows:(4)ψKM=α·∑ti∈TKqiM·Wp,ti,where(5)α=1EMTK≥20otherwiseand, ∀ti∈T(K), qiM is the enabling degree of transition ti at marking M.The general conflicts associated with a structural conflictK can be compared by their information content at markings, which reflects the number of resolution sequences for the general conflicts. Note that α=0 can lead to zero information content; that is, ψ(KM)=0, which implies that K at marking M does not produce any general conflict. A general conflict KM associated with the structural conflict K in a PN (N,M0) is said to have integrated decision-making information if there does not exist another general conflict KM′ associated with K in (N,M0) such that ψ(KM′)>ψ(KM).Letσ=(t)n denote a transition sequence in which the transition t consecutively fires n times and σ=[t1,t2,…,tn] denotes a synchronized transition sequence in which transitions t1,t2,…, and tn fire synchronously; that is, the transitions fire simultaneously. Figures 4(a) and 4(b) show two general conflicts KM=p2,t1,t2,M and KM′=p2,t1,t2,M′ with the same structure at markings M=p1+2p2 and M′=2p1+3p2, respectively. For the former, that is, KM, we have(6)ψKM=q1M·Wp2,t1+q2M·Wp2,t2=3.Furthermore, four feasible resolution sequences σ1=t1t2, σ2=t2t1, σ3=(t2)2, and σ4=[t1t2] can be observed. Similarly, for the latter, that is, KM′, we have(7)ψKM′=q1M′·Wp2,t1+q2M′·Wp2,t2=5.The ψ(KM′)=5 implies that the general conflict KM′ has more resolution sequences than KM, which are σ1=(t1)2t2, σ2=t1t2t1, σ3=t2(t1)2, σ4=t1(t2)2, σ5=t2t1t2, σ6=(t2)2t1, σ7=(t2)3, σ8=[t1(t2)2], and σ9=[(t1)2t2]. Suppose that KM and KM′ are only two general conflicts associated with K in a PN. Then, the general conflict KM′ has integrated decision-making information since ψ(KM′)=5>ψ(KM)=3.Figure 4
(a) A general conflictKM=p2,t1,t2,p1+2p2 with ψ(KM)=3 and (b) a general conflict KM′=p2,t1,t2,2p1+3p2 with ψ(KM′)=5.
(a)
(b)General conflicts provide information for decision-making in generalized PNs. Confusions can cause the information loss. The proposed control strategy of confusions is based on general conflicts and the control objective is to ensure the integrity of decision-making information of the general conflicts.Definition 10.
(1) Transitionst1 and t2 are said to be concurrent at marking M in a marked net (N,M) if Mt1, M[t2〉, and (•t1∪t1•)∩(•t2∪t2•)=∅.
(2) LetDM={t1,t2,…,tn} be a transition set. It is called a set of concurrent transitions at marking M if, ∀ti,tk∈DM, i≠k, transitions ti and tk are concurrent at marking M.
(3) The concurrent degree of a setDM of concurrent transitions, denoted by λ, is defined as λ=DM.
(4) LetDM be a set of concurrent transitions in a marked net (N,M) with λ=DM. It is said to be λ-max-concurrent in (N,M) if there does not exist a set of concurrent transitions D^M≠DM with λ^=D^M in (N,M) such that λ^>λ. A transition in DM is said to be λ-max-concurrent if DM is λ-max-concurrent in (N,M).
(5) LetDM={D1M,D2M,…,DρM} be the set of concurrent transition sets in (N,M). In other words, ∀DjM∈DM, DjM is a set of concurrent transitions in (N,M). DM is said to be λ-max-concurrent if ∀DjM∈DM, DjM is λ-max-concurrent in (N,M).The net shown in Figure5 contains totally seven sets of concurrent transitions at marking M=p1+p4+2p5; that is, D1M={t1,t5}, D2M={t1,t6}, D3M={t2,t5}, D4M={t2,t6}, D5M={t5,t6}, D6M={t1,t5,t6}, and D7M={t2,t5,t6}. According to Definition 10, D6M and D7M with λ6=λ7=3 are 3-max-concurrent since there does not exist a set of concurrent transitions from D1M to D7M, whose cardinality is greater than three. Let D1M={D6M,D7M} and D2M={D1M,D2M,D6M} be two sets of concurrent transition sets. Then D1M is 3-max-concurrent and D2M is not 3-max-concurrent since there exist two sets D1M and D2M, whose concurrent degrees are less than three.Figure 5
Illustration of concurrency.It is denoted byMtnM′ that a transition t∈T consecutively fires n times at marking M, where n≤q1M and M′ is the reachable marking from M by firing tt⋯t︸n.LetTc⊆DM be a subset of concurrent transitions in net N at marking M. Let M′ be the reachable marking from M by firing all transitions in Tc according to their enabling degrees. The fact is denoted by MTcM′. Note that the firing orders of the transitions in Tc are nondeterministic since Tc is a subset of concurrent transitions. For example, if Tc={t1,t2} and two transitions t1 and t2 are 1- and 2-enabled, respectively, at marking M fire, their possible firing sequences, according to enabling degrees, are σ1=t1(t2)2, σ2=(t2)2t1, σ3=t2t1t2, and σ4=[t1(t2)2], where σ1–σ3 are sequential firing sequences; that is, transitions fire consecutively, and σ4 is a synchronized firing sequence; that is, transitions fire simultaneously. Correspondingly, MTcM′ implies Mσ1M′, Mσ2M′, Mσ3M′, and Mσ4M′, where M′ is the reachable marking from M by firing any of the four possible firing sequences of concurrent transitions in Tc.A subnet (structure) of a PNN=(P,T,F,W) is a four-tuple N¯=(P¯,T¯,F¯,W¯), where P¯⊆P, T¯⊆T, F¯=F∩[(P¯×T¯)∪(T¯×P¯)], and, ∀f∈F¯, W¯(f)=W(f). Let m and m′ be positive integers with m′≤m. Given a marked net (N,M) with place set P={p1,p2,…,pm} and its subnet N¯ with place set P¯={pg1,pg2,…,pgm′}⊆P, we denote by M¯ the projection of a marking M∈Nm on N¯.M
¯ is called the submarking of M in N, which is denoted by M¯≺M. It is said to be valid if ∃j∈{g1,g2,…,gm′}, M¯(pj)>0. It is invalid if, ∀j∈{g1,g2,…,gm′}, M¯(pj)=0. Figure 6(a) represents a net system (N,M) with four places p1–p4 and four transitions t1–t4 at marking M=(1,4,1,0)T. A subnet N¯ of N with two places p1 and p2 and two transitions t3 and t4 is shown in Figure 6(b) at the valid submarking M¯=(1,4)T.Figure 6
(a) A generalized PNN at marking M=(1,4,1,0)T and (b) a subnet N¯ of N at submarking M¯=(1,4)T.
(a)
(b)ForN at another marking M′=(0,0,0,2)T with Mt1M1t42M′, the submarking M¯′=(0,0)T for N¯ is obtained, which is invalid since any element in M¯′ is zero.Definition 11.
A confusion, denoted by(N¯,T(K),M¯,DM¯), is a marked subnet (N¯,M¯) in a net system (N,M0) such that(1)
there exists a structural conflictK=p,TK with p∈P¯ and T(K)⊂T¯;(2)
there exists a nonempty setDM¯ that is composed of all 2-max-concurrent transition sets at the submarking M¯ in (N¯,M¯);(3)
∀DjM¯∈DM¯, ∃ti∈DjM¯∖T(K) and ∃k∈{1,2,…,qiM¯} such that M¯tikM¯′ and ψ(KM¯)≠ψ(KM¯′), where ψ(KM¯) and ψ(KM¯′) are information content of general conflicts associated with K at submarkings M¯ and M¯′, respectively;(4)
there exist two reachable markingsM and M′ in R(N,M0) such that M¯≺M and M¯′≺M′ are valid.A confusion is said to be a conflict-increasing confusion (CIC), denoted as Cin(N¯,T(K),M¯,DM¯), if ψ(KM¯)<ψ(KM¯′). It is said to be a conflict-decreasing confusion (CDC), denoted as Cde(N¯,T(K),M¯,DM¯), if ψ(KM¯)>ψ(KM¯′).Definition11 defines confusions as a class of marked subnets in a net system and classifies them into CICs and CDCs. Condition (1) in Definition 11 imposes a requirement on marked subnets. If a marked subnet is a confusion, it necessarily contains a structural conflict. Condition (2) in Definition 11 limits the size of a marked subnet (N¯,M¯) by restricting that all sets of concurrent transitions in (N¯,M¯) are 2-max-concurrent at submarking M¯. The concurrent degree λ=2 in this condition means that there does not exist a set of concurrent transitions, which contains more than two transitions.Condition (3) in Definition11 gives the behavior characteristics of confusions. For any set DjM¯ of max-concurrent transitions in a confusion, the change of information content of general conflicts is caused by the firing of a transition t∈DjM¯ that is not a structural conflicting transition. Condition (4) in Definition 11 ensures that the behavior described in condition (3) can actually occur in the original net system. If condition (4) is not satisfied, confusions cannot occur in the original net system although it may contain the structures of confusions. Confusions are classified into CICs and CDCs according to the change of information content in Definition 11.Example 1.
Figure7(a) shows a CIC Cin(N¯1,T(K1),M¯1,DM¯1), where T(K1)={t1,t2} is derived from the existing structural conflict K1=p2,t1,t2 in N¯1, M¯1=p1+2p2+4p4 is an initial submarking, DM¯1={D1M¯1} is the set of 2-max-concurrent transitions sets, and D1M¯1={t1,t3}.
Figure7(b) shows the partial reachability graph of the CIC, which is generated by concurrently firing transitions t1 and t3 only. In Figure 7(b), any submarking M¯j is considered with the information content ψ(K1M¯j) of the general conflict K1M¯j. The confusion is conflict-increasing since transition t3 can fire twice or four times, which can produce an increment of the information content. We cannot determine whether the general conflicts associated with K1 occur from the initial submarking M¯1 to the submarking M¯10 according to the concurrent firing of transitions t1 and t3.
As depicted in Figure7(b), three general conflicts occur at submarkings M¯3, M¯4, and M¯5 due to ψ(K1M¯3)=2, ψ(K1M¯4)=2, and ψ(K1M¯5)=3, respectively. However, the other submarkings in Figure 7(b) do not produce any general conflict. On the other hand, the general conflict K1M¯5=〈p2,{t1,t2},M¯5〉 at M¯5 is expected to occur since it has the maximal information content ψ(K1M¯5)=3 in Figure 7(b). The submarking M¯5 can be reached by only one path, that is, M¯1t3M¯2t3M¯3t3M¯4t3M¯5, which implies that the transition sequence σ=(t3)4 fires. However, transitions t1 and t3 in Figure 7(a) are concurrent, which implies that the firing orders of t1 and t3 are nondeterministic. The nondeterminism causes that the transition sequence σ=(t3)4 is not guaranteed to be fired. In this case, we can say that the information loss of the general conflict K1M¯5 occurs if a transition sequence fires, which does not pass through the submarking M¯5.Figure 7
(a) A CICCin(N¯1,T(K1),M¯1,DM¯1) with DM¯1=1 and (b) its partial reachability graph obtained by concurrently firing t1 and t3.
(a)
(b)Example 2.
Figure8(a) shows a CIC Cin(N¯2,T(K2),M¯1,DM¯1), where T(K2)={t1,t2,t3,t4}, M¯1=2p1+2p4, DM¯1={D1M¯1,D2M¯1}, D1M¯1={t1,t5}, and D2M¯1={t2,t5}. According to condition (3) in Definition 11, both sets D1M¯1 and D2M¯1 of 2-max-concurrent transitions need to be considered. If transitions t1 and t5 in D1M¯1 concurrently fire, the partial reachability graph shown in Figure 8(b) is obtained. By observing the reachability graph, the general conflict K2M¯3=p1,t1,t2,t3,t4,M¯3 at submarking M¯3=2p1+2p2+2p3 has the maximal information content ψ(K2M¯3)=6. The information loss of the general conflict K2M¯3 occurs if the transition sequence σ1=t5t1t5 or σ2=t1t5t5 fires.
The partial reachability graph shown in Figure8(c) is obtained by analyzing the concurrent firing of transitions t2 and t5 in D2M¯1. The same general conflict K2M¯3 with the maximal information content ψ(K2M¯3)=6 is obtained in Figure 8(c). There exists only one path M¯1t5M¯2t5M¯3 in Figure 8(c), which reaches the submarking M¯3. However, more paths exist in Figure 8(c) than Figure 8(b) from the initial submarking M¯1 to the submarking M¯6 such that the information loss of the general conflict K2M¯3 occurs. In other words, K2M¯3 does not occur if a path in Figure 8(c) does not pass through the submarking M¯3 from M¯1 to M¯6.Figure 8
(a) A CICCin(N¯2,T(K2),M¯1,DM¯1) with DM=2, (b) the partial reachability graph of (a) obtained by concurrently firing t1 and t5, and (c) the partial reachability graph of (a) obtained by concurrently firing t2 and t5.
(a)
(b)
(c)Example 3.
Figure9(a) shows a CDC that consists of two structural conflicts K3=p1,t1,t2 and K4=p2,t2,t3. Only one structural conflict in the confusion is considered due to symmetry. In this example, the structural conflict K3 is focused; that is, the CDC Cde(N¯3,T(K3),M¯1,DM¯1) is analyzed. From Figure 9(a), we have T(K3)={t1,t2}, M¯1=2p1+3p2, DM¯1={D1M¯1}, and D1M¯1={t1,t3}.
Figure9(b) depicts the partial reachability graph of the CDC, which can be obtained by concurrently firing transitions t1 and t3. The maximal information content of general conflicts associated with the structural conflict K3 can be found at the initial submarking M¯1=2p1+3p2; that is, ψ(K3M¯1)=3. Hence, the decisions on conflicting transitions t1 and t2 should be made for the general conflict K3M¯1=p1,t1,t2,M¯1. However, a transition t3∉T(K3) can concurrently fire such that the information content is reduced from ψ(K3M¯1)=3 to ψ(K3M¯4)=0. Consequently, the information loss of K3M¯1 occurs.
On the other hand, firingt1 also reduces the information content, which is not concerned with the information loss since t1 is a structural conflict transition for decisions. The submarking M¯2=p1+3p2+p3 with ψ(K3M¯2)=2 is reached after firing t1 at M¯1, which is also prone to the information loss of the general conflict K3M¯2=p1,t1,t2,M¯2 by firing t3.Figure 9
(a) A CDCCde(N¯3,T(K3),M¯1,DM¯1) with DM=1 and (b) its partial reachability graph obtained by concurrently firing t1 and t3.
(a)
(b)Example 4.
Figure10(a) depicts a CDC with two structural conflicts K5=p1,t1,t2,t3,t4 and K6=p2,t3,t4,t5. Similarly, we consider K5 in the confusion Cde(N¯4,T(K5),M¯1,DM¯1) only, where T(K5)={t1,t2,t3,t4}, M¯1=2p1+p2, DM¯1={D1M¯1,D2M¯1}, D1M¯1={t1,t5}, and D2M¯1={t2,t5}. In this case, the partial reachability graph shown in Figure 10(b) (resp., Figure 10(c)) is obtained by concurrently firing two transitions t1 and t5 (resp., t2 and t5). The confusion is prone to the information loss of the general conflict K5M¯1=p1,t1,t2,t3,t4,M¯1 since firing transition t5 reduces the information content from ψ(K5M¯1)=8 to ψ(K5M¯3)=4 and t5 does not have a structural conflict transition in T(K5).Figure 10
(a) A CDCCde(N¯4,T(K5),M¯1,DM¯1) with |DM|=2, (b) the partial reachability graph of (a) obtained by concurrently firing t1 and t5, and (c) the partial reachability graph of (a) obtained by concurrently firing t2 and t5.
(a)
(b)
(c)Confusion control in a generalized PN means that a reasonable strategy should be constructed to ensure the appearance of the general conflicts with maximal information content and if an output marking of a general conflict is preassigned, the control policy can guarantee the marking to be reachable.


## 3. Control of Conflicts and Confusions Using Synchronized PNs

Confusions may occur in a PN since a class of special structures in the PN is closely related to the appearances of confusions and the improper firing orders of concurrent transitions exist in its subnets at some markings. The information content of general conflicts becomes nondeterministic if a confusion occurs. A PN system must avoid any improper firing order of concurrent transitions such that the system can be immune to the information loss of general conflicts.Seeking a control mechanism carried out off-line to prevent the appearance of confusions is expected. In this section, we achieve this purpose by using synchronized PNs. Synchronized PNs are established to reinforce the firing conditions of each transition by introducing a reasonable external event. In PNs, a transition can fire if it is enabled. However, when it will be fired is unknown. In contrast, in a synchronized PN, a transition fires if it is enabled and the associated external event is satisfied.External events usually have practical meanings. For example, a synchronized PN in which external events are associated with time or probability is called aT-timed PN or a stochastic PN, which is introduced by Ramchandani [29], and Florin and Natkin [30], respectively. The synchronized firing of transitions is allowed in a synchronized PN with external events. In other words, two enabled transitions can fire simultaneously by the control of their external events.In this section, a transition firing mechanism is developed, which applies external events to each transition with control information that is called allowable enabling degrees. They are featured with desired enabling degrees of transitions and can perform a variety of external event dependency relations by assigning their dependency orders. The dependency relations of two external events can be described as the fact that the execution times of an external event depend on that of another external event. Then, an approach to confusion control is proposed, which refers to a group of static rules imposing restrictions on the enabling degrees and the dependency relations of external events controlling concurrent transitions in confusions. A major advantage is that any assigned external event can be converted into a feedback structure taking the form of PNs such that confusions can be controlled in system design stages.Letα∈N be a nonnegative integer. It is said to be an allowable enabling degree of a transition t if t is α′-enabled and α′≥α.Definition 12.
A synchronized PNNs with allowable enabling degrees is a three-tuple (N,E,S), where N=(P,T,F,W) is a PN, ∀ti∈T, αi is the allowable enabling degree of ti, E={e[αg1]1,e[αg2]2,…,e[αgn]n} with n≤T being a set of external events, and S is a function from the transition set T of N to E. (Ns,M0) is called a synchronized net system, where M0 is an initial marking.In a synchronized net system(Ns,M), if a transition ti∈T is controlled by an external event e[αgk]k with αgk=αi and is enabled at M, it does not become fireable unless the enabling degree of ti is greater than or equal to the assigned allowable enabling degree αi. If ti obtains a proper enabling degree at M, then it can immediately fire αi times.A given external event can control more than one transition such that they can synchronously fire according to their allowable enabling degrees. Letti and tj be two transitions in a synchronized PN with i≠j. Suppose that ti and tj are controlled by an external event e[αgk]k that can impose different allowable enabling degrees αi and αj to ti and tj, respectively. Transitions ti and tj are said to be synchronized with e[αgk]k if two functions S(ti)=e[αi]k and S(tj)=e[αj]k exist. If αi=2 and αj=3 are assigned and ti and tj are 2- and 4-enabled at marking M, respectively, they can synchronously fire twice and thrice, respectively. Consequently, the transition sequence σ=[(ti)2(tj)3] fires.Lete[αgi]i and e[αgj]j be two external events in E with i≠j. The fact that the execution times of e[αgj]j rely on that of e[αgi]i is denoted by e[αgi]i≫e[αgj]j. In this case, we can say that the external events e[αgi]i and e[αgj]j satisfy the dependency relation e[αgi]i≫e[αgj]j. For instance, let transitions t1 and t5 be controlled by an external event e[αg1]1 with the functions S(t1)=e[2]1 and S(t5)=e[3]1 and let transition t2 be controlled by another external event e[αg2]2 with the function S(t2)=e[2]2, implying that α1=2, α2=2, and α5=3. Let q1M=2, q2M=3, and q5M=3 be their enabling degrees at marking M, respectively. Then, they are fireable since, ∀k∈{1,2,5}, qkM≥αk is true. Suppose that the external events satisfy the dependency relation e[αg2]2≫e[αg1]1. Then, the transition sequence [(t1)2(t5)3] can fire ρ times if the sequence [(t2)2] had fired ρ times, where ρ∈N.LetNs=(N,E,S) be a synchronized net with n external events, where n≤|T|. The transition set T of Ns can be partitioned into n subsets T1, T2, …, and Tn according to the control of the n external events. In other words, an external event e[αgk]k controls all the transitions in the subset Tk, where k∈{1,2,…,n}. Ns at a marking M satisfies the following transition firing rules:(1)
Event dependency relations are not given for external events: a transitiontj∈Tk⊆T is fireable and immediately fires αj times at the marking M if, ∀ti∈Tk, Mti and qiM≥αi are true.(2)
Event dependency relations are given forn external events; for example, e[αg1]1≫⋯≫e[αgk-1]k-1≫e[αgk]k≫⋯≫e[αgn]n: a transition tj∈Tk⊆T is fireable and immediately fires ρ·αj times at the marking M if, ∀ti∈Tk, Mti and qiM≥αi are true and ∃M′, ∃σ such that M′σM and, ∀tj∈Tk-1, tj fires ρ·αj times at the marking M′.In the rules, qiM is the enabling degree of the transition ti at marking M, αi is the allowable enabling degree of the transition ti controlled by external events, and ρ∈N is an integer. Any synchronized transition (a transition controlled by an external event) in synchronized PNs is presumed as an immediate transition [26]. The transition firing rules are illustrated in Examples 5 and 6, respectively.Figures11(a) and 11(b) show a PN (N,M0) and its reachability graph with 10 markings, respectively. Two synchronized PNs (Ns,M0) and (Ns′,M0) with [N]=[Ns]=[Ns′] are illustrated in Figures 11(c) and 11(e), respectively. Their evolutions are depicted as reachability graphs and shown in Figures 11(d) and 11(f), respectively. The restrictions generated by the control of external events can be observed by comparing their reachability graphs. As shown in the examples, a node nk in the reachability graph of a synchronized PN contains the following information:(1)
The markingMk.(2)
The vectorQk of enabling degrees at marking Mk.(3)
A list of allowable enabling degrees for transitions, which is shown on the right side ofQk in a reachability graph.The weight on an arc is denoted by the form σ/e[αgi]i that illustrates the marking change due to the firing of transition sequence σ by the control of external event e[αgi]i∈E.Figure 11
(a) A net system(N,M0), (b) the reachability graph of (N,M0), (c) a synchronized net system (Ns,M0), (d) the reachability graph of (Ns,M0), (e) a synchronized net system (Ns′,M0) with an event dependency relation, and (f) the reachability graph of (Ns′,M0).
(a)
(b)
(c)
(d)
(e)
(f)Example 5.
Figure11(c) shows a synchronized PN (Ns,M0) that has the same structure and the initial marking of (N,M0), where t1 and t2 are synchronized with e[αg1]1 and both t1 and t2 are controlled by e[1]1 with the allowable enabling degrees α1=α2=1. They can synchronously fire if q1M≥α1 and q2M≥α2 are satisfied at a reachable marking M. Otherwise they cannot fire. Transition t3 is controlled by event e[2]2 with α3=2. Figure 11(d) depicts the reachability graph of (Ns,M0), where the initial marking M0=[M0(p1),M0(p2),M0(p3)]T=[1,1,1]T. At this marking, the vector of enabling degrees of t1, t2, and t3 is Q0=[q1M0,q2M0,q3M0]T=[1,1,1]T.
According toQ0, we have q1M0=α1, q2M0=α2, and q3M0<α3. The synchronized transitions t1 and t2 can fire. The marking M4=[0,1,2]T can be obtained from the initial marking M0 by firing the transition sequence σ=[t1t2]. Then, the vector of enabling degree Q0=[1,1,1]T is updated to Q4=[0,1,2]T at M4. When marking M4 and vector Q4 are considered, we have q1M4<α1, q2M4=α2, and q3M4=α3. However, transition t2 is not allowed to fire owing to the control of the external event e[αg1]1. It can fire if its synchronized transition t1 is also fireable. On the other hand, transition t3 is not synchronized with other transitions. Hence, it can fire. After the transition sequence σ=(t3)2 fires, marking M3=[2,1,0]T and vector Q3=[2,1,0]T are obtained. The transition sequence σ=[t1t2] can immediately fire since the allowable enabling degrees of t1 and t2 are satisfied at marking M3. Finally, the state returns to the initial marking M0.Example 6.
Figure11(e) depicts a synchronized net system (Ns′,M0), where transitions t1, t2, and t3 are controlled by e[1]1, e[1]1, and e[1]2 with α1=α2=α3=1, respectively. If the dependency relations are set for the external events e[αg1]1 and e[αg2]2 with e[αg2]2≫e[αg1]1, the reachability graph shown in Figure 11(f) is obtained. By considering the initial marking M0=[1,1,1]T, we obtain the vector Q0=[1,1,1]T. The three transitions t1, t2, and t3 are fireable since their allowable enabling degrees are satisfied. In this case, t1 and t2 can fire if t3 has fired, which is ensured by the assigned event dependency relation. Hence, t1 and t2 cannot fire at M0 until t3 fires once. Marking M3=[2,1,0]T is reached by firing t3 from the initial marking M0. Then, the transition sequence σ=[t1t2] fires once and the state returns to the initial marking M0.The control of external events generates restrictions on the reachability set of(Ns,M0); that is, R(Ns,M0)⊆R(N,M0). On the other hand, the set of feasible transition firing sequences of (Ns,M0) is also included in that of (N,M0) [26].To illustrate the feasibility of the control of external events in synchronized PNs, we provide formal definitions and illustrations by converting the control into feedback control structures taking the form of PNs.LetT′={t1,t2,…,tη}⊆T be the set of the transitions controlled by an external event e[αgk]k∈E with k∈{1,2,…,|E|} in a synchronized PN Ns and, ∀ti∈T′, let αi be the allowable enabling degree of the transition ti. The feedback control structure of e[αgk]k can be constructed according to the following steps:(1)
Lettrk and tck be transitions and let prk, pc1–pcη, and pm1–pmη be places. Define M(prk)=0, M(pmi)=αi, and, ∀i={1,2,…,η}, M(pci)=0.(2)
Transitiontck performs reading operation that can read the token information of the preset places of the controlled transitions according to their allowable enabling degrees. If the tokens in the preset places satisfy the firing rules of the controlled transitions according to their allowable enabling degrees, the transition trk fires and outputs a token to the place prk. The construction of this step can be formally defined as follows: define the arc (trk,prk) with W(trk,prk)=1. ∀ti∈T′, ∀p∈•ti, define arcs (p,trk), (ti,pmi), and (pmi,trk), where W(p,trk)=αi·W(p,ti), W(ti,pmi)=1, and W(pmi,trk)=αi.(3)
Then, transitiontck restores the tokens in the preset places of the controlled transitions and outputs control tokens to the places pc1–pcη such that the tokens in them can control the firing of the controlled transitions. The construction of this step can be formally defined as follows: define the arc (prk,tck) with W(prk,tck)=1. ∀ti∈T′, ∀p∈•ti, define arcs (tck,p), (tck,pci), and (pci,ti) with W(tck,p)=αi·W(p,ti), W(tck,pci)=αi, and W(pci,ti)=1.The constructed feedback control structures of external events are illustrated with examples. First, in a synchronized net system, an external event can perform control on the allowable enabling degree of a transition. For example, transitiont1 in Figure 12(a) is considered, which has two input places p1 and p2. An external event e[αg1]1 with S(t1)=e[2]1 (α1=2) is designated to control t1 and the allowable enabling degree α1=2 is used to control that the transition t1 cannot fire unless its enabling degree is greater than or equal to two. The feedback structure shown in Figure 12(b) achieves the control purposes.Figure 12
Illustration of the control of external events: (a) a transition with an external event, (b) the feedback structure of (a), (c) two synchronized transitions, (d) the feedback structure of (c), (e) two synchronized transitions with a common preset place, (f) the feedback structure of (e), (g) setting dependency relatione[αg1]1≫e[αg2]2 for two external events, and (h) the feedback structure of (g).In Figure12(b), two tokens in place pm1 imply α1=2. Transition tr1 performs reading operations for the enabling degree of t1 at a marking. If the enabling degree of t1 is greater than or equal to two, transition tr1 fires. Then, transition tc1 outputs control tokens such that t1 fires twice.Second, synchronized firing of transitions can be performed by external events. Transitionst2 and t3 shown in Figure 12(c) are controlled by an external event e[αg2]2 with S(t2)=e[3]2 (α2=3) and S(t3)=e[2]2 (α3=2). If both enabling degrees of t1 and t2 satisfy their allowable enabling degrees, they become fireable and fire; otherwise none of them is allowed to fire.Figure12(d) depicts the feedback control structure that achieves the same control purposes of e[αg2]2 for transitions t2 and t3. Both enabling degrees of t2 and t3 are detected by transition tr2. Furthermore, transition tc2 outputs control tokens for the two transitions simultaneously after tr2 fires.Suppose thatt2 and t3 in Figure 12(c) have common preset places. For example, the two places p3 and p4 in Figure 12(c) are merged into the place p3 shown in Figure 12(e). The PN construction of Figure 12(e) can be obtained by merging p3, p4, and their arcs in Figure 12(d), which is shown in Figure 12(f).LetT′ and T′′ be subsets of the transition set T in a synchronized PN Ns with T′∩T′′=∅ and let e[αgk]k and e[αgj]j be two external events, where the transitions in T′ (resp., T′′) are controlled by the event e[αgk]k (resp., e[αgj]j). If e[αgk]k and e[αgj]j satisfy the event dependency relation e[αgk]k≫e[αgj]j. The corresponding feedback control structure can be constructed according to the following steps:(1)
Letts1 and ts2 be two transitions, and let ps1–ps3 be three places, where, ∀i={1,2,3}, M(psi)=0.(2)
Transitionts1 fires if the control of the external event e[αgk]k is executed. The execution times of e[αgk]k are stored into the place ps3 by firing ts2. The tokens in p3 control the execution times of another external event e[αgj]j such that the execution times of e[αgj]j rely on e[αgk]k. The construction of this step is formally defined as follows: define arcs (trk,ps1), (ps1,ts1), (ts1,ps2), (ps2,ts2), (ts2,ps3), and (ps3,trj), where W(trk,ps1)=1, W(ps1,ts1)=1, W(ts1,ps2)=1, W(ps2,ts2)=1, W(ts2,ps3)=1, and W(ps3,trj)=1. ∀ti∈T′, define the arcs (pmi,ts1) and (ts2,pmi), where W(pmi,ts1)=W(ts2,pmi)=M(pmi).As shown in Figure12(g), the execution times of the event e[αg2]2 rely on that of e[αg1]1; that is, e[αg1]1≫e[αg2]2. By considering Figure 12(h), the dependency relation can be achieved by adding two transitions ts1 and ts2, three places ps1–ps3, and their arcs.


### 3.1. Control of General Conflicts in Synchronized PNs

The resolution control of a general conflict is to choose a transition sequence such that the general conflict can be resolved according to the selected sequence to reach an expected marking.The resolution control is illustrated by an example.KM=p1,t1,t2,3p1+2p2 shown in Figure 13(a) is a general conflict at marking M=3p1+2p2. Figure 13(b) depicts KM in the corresponding synchronized net Ns of N with S(t1)=e[α1]1 and S(t2)=e[α2]1. The resolution control of KM means to make decision on firing times of transitions t1 and t2. In other words, the values of α1 and α2 are determined such that a resolution sequence of KM fires. Figures 13(c) and 13(d) show two feasible control policies.Figure 13
Illustration of the control of resolution sequences in a general conflict.
(a)
(b)
(c)
(d)If functionsS(t1)=e[α1]1=e[2]1 and S(t2)=e[α2]1=e[1]1 are employed, the general conflict KM will fire resolution sequence σ1=[(t1)2t2] in a net system (N,M). If S(t1)=e[α1]1=e[1]1 and S(t2)=e[α2]1=e[2]1 are applied, the resolution sequence σ2=[t1(t2)2] is ensured to fire in (N,M).In a general conflict, some resolution sequences can lead to the same output marking, which have different transition firing orders. In these resolution sequences, the synchronized one is unique, which is used to resolve the general conflict in synchronized PNs. For example,σ1=t1(t2)2, σ2=t2t1t2, σ3=(t2)2t1, and σ4=[t1(t2)2] are four resolution sequences of the general conflict shown in Figure 13(a). Firing any of them leads to the same output marking. In this example, σ4 is used to resolve the general conflict in the synchronized PN.A strategy to find all synchronized resolution sequences for a general conflict is proposed. LetT(e[αgi]i,M) be the set of transitions that are controlled by the external event e[αgi]i at marking M. Let a and b be two vectors. Notation a≥b means for every i, a(i)≥b(i) and a⪈b means for every i, a(i)≥b(i) and for at least one i, a(i)>b(i).Definition 13.
The sequenceσk is said to be an elementary conflict resolution sequence (ECRS) with an external event e[αgi]i in (Ns,M) if it meets the following four conditions:(1)
All the transitions inσk belong to T(e[αgi]i,M).(2)
All the transitions inσk belong to T(KM).(3)
[Ns]-·σk→≤M, where [Ns]- with [Ns]-(p,t)=W(p,t) is the output incidence matrix and σk→ is the Parikh vector of σk.(4)
There is no sequenceσ^k such that σ^k→⪈σk→.An ECRS of a general conflict in a net(Ns,M) corresponds to a synchronized resolution sequence. Conditions (1) and (2) in Definition 13 guarantee that the fundamental elements (transitions) in an ECRS are controlled by e[αgi]i at marking M and the transitions are in the set of general conflicting transitions. Condition (3) in Definition 13 ensures that the conflicting transitions in T(KM) according to the ECRS are feasible (the tokens in places meet the firing condition of their output transitions in σk). Finally, according to condition (4) in Definition 13, σk is ensured as a resolution sequence of the general conflict KM. In other words, all conflicting transitions become disabled if σk fires. Algorithm 14 is proposed to generate all ECRSs of a synchronized PN at a marking.Algorithm14 is illustrated through an example shown in Figure 14 in which the weight of each arc equals one for the sake of simplicity since the weights do not affect the function of Algorithm 14. Actually, a weight means a coefficient in the computation of enabling degrees. A synchronized PN (Ns,M) is shown in Figure 14(a), where M=3p2+2p3+2p4+p6. Transitions from t1 to t4 are controlled by an external event e[αg1]1 outputting the functions from S(t1)=e[α1]1 to S(t2)=e[α4]1, respectively. Transition t5 is controlled by another external event e[αg2]2 with S(t5)=e[α5]2. The values of allowable enabling degrees of conflicting transitions can be obtained according to the firing times of the transitions in every ECRS.Figure 14
Application of Algorithm14 to a PN Ns.Algorithm 14 (generation of all ECRSs of a synchronized PN(Ns,M)).
Input is as follows:(Ns,M) and e[αgi]i. //e[αgi]i is an external event and employed in Ns at marking M.
Output is as follows: all ECRSs:
Step 1: delete all transitions not belonging toT(e[αgi]i,M) and their input and output arcs according to condition (1) in Definition 13.
Step 2: according to condition (2) in Definition13, delete all the transitions not belonging to T(KM) and their input and output arcs.
Step 3: delete all the arcs from transitions to places since an ECRS is related to the output matrix only according to condition (3) in Definition13. the reduction leads to a new synchronized PN N¯s. All the transitions in N¯s are conflicting transitions.
Step 4: construct the reachability graph of(N¯,M). Then, each deadlock marking implies an ECRS. //(N¯,M) is the generalized PN with [N¯]=[N¯s].
Step 5: output the ECRSs.First, the input of Algorithm14 is (Ns,M) and the external event e[αg1]1. After Step 1 in Algorithm 14, a subnet of Ns is obtained as shown in Figure 14(b), where transition t5 and its corresponding arcs in Ns are removed since t5 is not controlled by e[αg1]1. Then, transitions t1, t4, and their corresponding arcs are removed by Step 2 in Algorithm 14 since they are not conflicting transitions, which is depicted in Figure 14(c). The subnet N¯s of Ns can be found as shown in Figure 14(d) according to Step 3 in Algorithm 14.The generalized PN(N¯,M) with [N¯]=[N¯s] contains a general conflict KM=p2,t2,t3,3p2+2p3+2p4+p6. Its reachability graph is shown in Figure 14(e). There are three deadlock markings that correspond to three different ECRSs σ1=[(t2)3], σ2=[t2(t3)2], and σ3=[(t2)2t3], respectively. Each ECRS can deduce the values of α1, α2, α3, and α4 on external event e[αg1]1. For example, σ2=[t2(t3)2] is an ECRS of KM, which means that KM can be resolved by firing transitions t2 once, and t3 twice simultaneously. Hence, α1=0, α2=1, α3=2, and α4=0 are obtained. The external event e[αg1]1 with the four allowable enabling degrees can perform control such that the transitions in KM fire according to the ECRS σ2 at marking M.The validity of Algorithm14 is clear since the reachability graph of the PN that is composed of a general conflict only contains all feasible paths from an initial marking to all dead markings.


### 3.2. Control of Confusions Using External Events

As stated in Section2, a confusion is prone to the information loss of general conflicts owing to nondeterministic firing orders of concurrent transitions. In a CIC, a general conflict KM with maximal information content is implied in the evolution of markings. The marking M at which the general conflict KM occurs is expected. It should be ensured that the firing of a transition sequence can reach the marking M. Also, the transition firing sequences that lead to the information loss of the general conflict KM should be avoided.If a general conflictKM with maximal information content in a confusion occurs, all the ECRSs are needed and can be obtained. Furthermore, an ECRS is selected as a decision to generate the allowable enabling degrees of transitions. The general conflict KM can always be resolved according to the selected ECRS by the control of external events. Here we assume that confusions have been found at a marking and we aim to control them. Algorithm 15 is proposed to control a given CIC.Algorithm 15 (general conflict control in CIC(N¯,M¯)).
Input is as follows:(N¯,M¯).
Output is as follows: outputS(ti), ∀ti∈T¯, and the dependency relation between e[αgj]j and e[αgk]k // T¯ is the set of transitions in N¯. S is a function mapping from T¯ to E. E={e[αgj]j,e[αgk]k} is a set of external events with j≠k:
Step 1: find the setT(K) of the structural conflicting transitions in N¯. Let H=T¯∖T(K). ∀ti∈H, design a function Sti=eαij. ∀ti∈T(K), design a function S(ti)=e[αi]k.
Step 2:∀ti∈H, αi:=qiM¯. //qiM¯ is the enabling degree of ti at the submarking M¯.
Step 3: design the dependency relatione[αgj]j≫e[αgk]k.
Step 4: obtain the submarkingM¯′ by firing all transitions in H at M¯ according to their enabling degrees.
Step 5: find all ECRSs of(N¯,M¯′) by Algorithm 14 with the inputs (N¯,M¯′) and e[αgk]k.
Step 6: choose an ECRS. For any transitionti in T(K), obtain the allowable enabling degree αi by the ECRS.
Step 7: outputS(ti), ∀ti∈T¯, and e[αgj]j≫e[αgk]k.When the general conflict of a CIC is identified at making, its control can be enforced by adding external events according to some of the established rules. Algorithm15 presents the rules. In Step 1 of Algorithm 15, the transition set T¯ of a CIC is partitioned into two parts T(K) and H=T¯∖T(K). According to Definition 11, a CIC occurs if the transitions in T(K) fire before those in H. Hence, Algorithm 15 designs a dependency relation by Step 3 in Algorithm 15 between the event controlling the transitions in H and the event controlling the transitions in T(K) such that, ∀ti∈H, ∀tj∈T(K), ti fires qiM¯ times before firing tj. If the transitions in H fire according to their enabling degrees, the general conflict associated with K with the maximal information content is obtained. We can obtain all ECRSs according to Algorithm 14. Any ECRS is a control policy. Then, an ECRS is selected and the allowable enabling degrees of conflicting transitions to perform this ECRS can be obtained. Finally, the output functions and the event dependency relation presented in Step 7 of Algorithm 15 can control the CIC such that the information loss of the general conflict that has the maximal information content does not occur.The CICCin(N¯1,T(K1),M¯1,DM¯1) in Example 1 is also depicted in Figure 15(a) to illustrate Algorithm 15, where T(K1)={t1,t2}, M¯1=p1+2p2+4p4, DM¯1={D1M¯1}, and D1M¯1={t1,t3}. By the analysis in Section 2, the general conflict K1M¯5=〈p2,{t1,t2},M¯5〉 at the submarking M¯5=p1+2p2+4p3 has the maximal information content ψ(K1M¯5)=3. Transitions t1 and t3 are concurrent.Figure 15
Illustration of the control of confusions using external events: (a) a CIC (N¯1,M¯1), (b) application of Algorithm 15 to (N¯1,M¯1), (c) a CDC (N¯3,M¯1), and (d) application of Algorithm 16 to (N¯3,M¯1).The information loss ofK1M¯5 in the CIC occurs if the conflicting transition t1 fires before firing transition sequence (t3)4. For example, the firing of the sequence σ1=t1(t3)4, σ2=t3t1(t3)3, σ3=(t3)2t1(t3)2, or σ4=(t3)3t1t3 at the initial submarking M¯1 causes the information loss of K1M¯5. On the contrary, the information loss of K1M¯5 does not occur in the CIC if the transition sequence (t3)4 fires before firing t1. For example, the firing of the sequence σ5=(t3)4t1 does not cause the information loss since the submarking M¯5 leading to K1M¯5 can be reached through firing the sequence σ5=(t3)4t1 from M¯1, that is, M¯1[(t3)4〉M¯5[t1〉M¯10. The control processes for this confusion contain the following steps according to Algorithm 15:(1)
Two setsT(K)={t1,t2} and H={t3} are obtained. Let t1, t2, and t3 be controlled by e[α1]2, e[α2]2, and e[α3]1, respectively (Step 1). // Suppose that j=1 and k=2.(2)
The allowable enabling degree of transitiont3 is obtained by α3=q3M¯1=4 (Step 2).(3)
The dependency relatione[αg1]1≫e[αg2]2 is assigned (Step 3).(4)
The submarkingM¯5=p1+2p2+4p3 is reached by firing t3 four times (Step 4).(5)
Two ECRSsσ1=[t1t2] and σ2=[(t2)2] of the general conflict K1M¯5 are obtained by Algorithm 14 (Step 5).(6)
The ECRSσ1 is selected. We have the allowable enabling degrees α1=α2=1 by the ECRS (Step 6).(7)
Three functionsS(t1)=e[1]2, S(t2)=e[1]2, and S(t3)=e[4]1 are obtained. The dependency relation e[αg1]1≫e[αg2]2 needs to be applied (Step 7).Finally, the controlled CIC is shown in Figure 15(b), where only the transition sequence σ=(t3)4[t1t2] can fire. The information loss of K1M¯5 is prevented.The structure of a CDC is composed of two structural conflicts. However, only one structural conflict can be used to analyze the information loss of general conflicts in the CDC, which is illustrated with the example shown in Figure16.Figure 16
Schema of a CDC (N¯,M¯) without considering the weights of arcs, where Kg1=p1,p1•, Kg2=〈p2,p2•〉, Ω∗=T(Kg1)∩T(Kg2), Ω1=T(Kg1)∖Ω∗, and Ω2=T(Kg2)∖Ω∗.Figure16 shows the schema of a CDC (N¯,M¯) without considering the weights of arcs, where Kg1=p1,TKg1 with T(Kg1)=p1• and Kg2=p2,TKg2 with T(Kg2)=p2• are two structural conflicts in the CDC. Let Kg1M¯ and Kg2M¯ be two general conflicts associated with Kg1 and Kg2 at submaking M¯, respectively. All transitions in (N¯,M¯) are partitioned into three subsets Ω∗=T(Kg1)∩T(Kg2), Ω1=T(Kg1)∖Ω∗, and Ω2=T(Kg2)∖Ω∗. Let DM¯={D1M¯,D2M¯,…,D|Ω1|·Ω2M¯} denote the set of 2-max-concurrent transition sets of (N¯,M¯). ∀ti∈Ω1, ∀tk∈Ω2, transitions ti and tk are concurrent.According to Definition11, ∀ti∈Ω1, ∀tk∈Ω2, ∃DjM¯={ti,tk}∈DM¯, we have ti∈T(Kg1)∩DjM¯ and tk∈DjM¯∖T(Kg1) such that the information loss of Kg1M¯ occurs by firing the sequence σ=tkti. However, we also have tk∈T(Kg2)∩DjM¯ and ti∈DjM¯∖T(Kg2) such that the firing of the same sequence σ=tkti does not cause the information loss of Kg2M¯. Hence, the contradiction occurs. For a CDC, only one structural conflict can be used to analyze the information loss of general conflicts in the CDC.Algorithm 16 (general conflict control in CDC(N¯,M¯)).
Input is as follows:(N¯,M¯).
Output is as followd:S(ti), ∀ti∈T¯, and the dependency relation between e[αgj]j and e[αgk]k // T¯ is the set of transitions in N¯. S is a function mapping from T¯ to E. E={e[αgj]j,e[αgk]k} is a set of external events with j≠k:
Step 1:∀ti∈T¯, design a function S(ti)=e[αi]j. Find all ECRSs of (N¯,M¯) by Algorithm 14 with the inputs (N¯,M¯) and e[αgj]j. Choose an ECRS. For any transition ti that meets S(ti)=e[αi]j, obtain the allowable enabling degree αi by the ECRS.
Step 2: find the two setsT(Kg1) and T(Kg2) of the structural conflicting transitions in N¯. Let Ω∗=T(Kg1)∩T(Kg2), Ω1=T(Kg1)∖Ω∗, and Ω2=T(Kg2)∖Ω∗. // The structure of any CDC is composed of two structural conflicts.
Step 3: choose a set of structural conflict transitions. IfT(Kg1) is considered, go to Step 4; else go to Step 5. // Determine a structural conflict to be controlled.
Step 4:∀ti∈Ω2, replace the function S(ti)=e[αi]j with S(ti)=e[αi]k. Go to Step 6.
Step 5:∀ti∈Ω1, replace the function S(ti)=e[αi]j with S(ti)=e[αi]k. Go to Step 6.
Step 6: design the the dependency relatione[αgj]j≫e[αgk]k.
Step 7: outputS(ti), ∀ti∈T¯ and e[αgj]j≫e[αgk]k.When a CDC is detected, its structure is known [18]. According to Figure 16, any CDC contains two general conflicts in which one is focused to control. Hence, Algorithm 16 designs rules to add external control events such that the focused general conflict can be resolved before the other. Algorithm 16 achieves this purpose. First, the partition of the transitions in a CDC (N¯,M¯) is performed. Let us consider the structural conflict Kg1. The information loss of the corresponding general conflict Kg1M¯ occurs if the transitions in Ω2 (Ω2⊈T(Kg1)) fire before the resolution of Kg1M¯. On the contrary, the information loss of Kg1M¯ does not occur if Kg1M¯ is resolved before the transitions in Ω2 fire. Hence, Algorithm 16 designs a dependency relation between the event controlling the transitions in T(Kg1) and that controlling the transitions in Ω2, which also assigns the allowable enabling degrees of the transitions in T(Kg1) to resolve the general conflict Kg1M¯. Finally, the output functions and the dependency relation can control the CDC such that the information loss of Kg1M¯ does not occur.TheCde-conf Cde(N¯3,T(K3),M¯1,DM¯1) in Example 3 is also illustrated in Figure 15(c), where K3=〈p1,T(K3)〉, T(K3)={t1,t2}, M¯1=2p1+3p2, DM¯1={D1M¯1}, and D1M¯1={t1,t3}. In this case, K3 is focused only. By the analysis in Section 2, K3M¯1=〈p1,{t1,t2},2p1+3p2〉 is a general conflict with the maximal information content ψ(K3M¯1)=3 at the initial submarking M¯1. The decisions on K3M¯1 are made. However, t1 and t3 are concurrent. The information loss of K3M¯1 does not occur unless transition t3 fires after the general conflict K3M¯1 is resolved. The control processes for this CDC contain the following steps according to Algorithm 16:(1)
Three functionsS(t1)=e[α1]1, S(t2)=e[α2]1, and S(t3)=e[α3]1 are obtained. Two ECRSs σ1=[t1t2] and σ2=[(t1)2t3] are obtained by Algorithm 14. Suppose that ECRS σ2 is selected. Three allowable enabling degrees α1=2, α2=0, and α3=1 are assigned (Step 1). // Suppose that j=1 and k=2.(2)
Five setsT(Kg1)={t1,t2}, T(Kg2)={t2,t3}, Ω∗={t2}, Ω1={t1}, and Ω2={t3} are obtained (Step 2).(3)
T(Kg1)={t1,t2}; that is, T(K3) in Example 3 in Section 2 is selected (Step 3).(4)
The functionS(t3)=e[1]1 is replaced by S(t3)=e[1]2 (Step 4).(5)
The dependency relatione[αg1]1≫e[αg2]2 is assigned (Step 6).(6)
Three functionsS(t1)=e[2]1, S(t2)=e[0]1, and S(t3)=e[1]2 are obtained. The dependency relation e[αg1]1≫e[αg2]2 needs to be applied (Step 7).Finally, the controlled CDC is obtained as shown in Figure15(d), where only transition sequence σ=[(t1)2]t3 can fire. K3M¯1 can be resolved before t3 fires.The computational complexity of Algorithms14, 15, and 16 is analyzed. First, the reachability graph of a synchronized PN to compute ECRSs is necessary, which is the main cost in Algorithms 14, 15, and 16. However, the reachability graph for a general conflict is only a small part of that of the whole PN, which is necessary to find all synchronized resolution sequences. Second, in Algorithms 15 and 16, finding the structural conflicts in a confusion (N¯,M¯) and partitioning the transitions in T¯ are involved. For the former, structural conflicts can be found by scanning the incidence matrix [N¯], which can be completed in O(mn) time, where m and n are the numbers of places and transitions in N¯, respectively. For the latter, the partitions follow the basic operations of sets, which can be completed in O(n2) time.Third, adding and outputting external events of transitions in Algorithms15 and 16 can be completed in O(n2) time. The computational complexity of adding external events to the transitions in N¯ is considered. According to the constructions in Figure 12, only 5 elements (two transitions and three places) are needed for an external event to control a transition in N¯. In the worst case, we need n external events to control totally n transitions in N¯. In other words, 5·n elements in total are added by adding rows and columns in the incidence matrix [N¯], which can be completed in O(n2) time since the number of rows and columns added has linear relation with the number n of transitions.Finally, Algorithm15 or Algorithm 16 outputs an event dependency relation for the two external events in a confusion subnet. According to the constructions in Figure 12, only 5 elements (two transitions and three places) are used to represent the event dependency relation. The number of elements added for the event dependency relation has no relation with the numbers m of places and n transitions in N¯. Hence, adding an event dependency relation in Algorithm 15 or Algorithm 16 can be completed in O(1) time.The control strategies (Algorithms14, 15, and 16) of confusions are based on synchronized PNs in which any transition is controlled by an external event. The strategies are applied to generalized PNs. It is unnecessary to control the transitions not in confusions by external events. Hence a class of local synchronized PNs (LSPNs) is proposed.Definition 17.
A marked LSPN is a seven-tupleNl=(P,T,F,W,E,S,M0), where P and T=Tn∪Ts (Tn≠∅ and Ts≠∅ are the sets of nonsynchronized and synchronized transitions, resp.) are finite, nonempty, and disjoint sets. F⊆(P×T)∪(T×P) is called a flow relation of the net. W:(P×T)∪(T×P)→N is a mapping that assigns a weight to an arc: W(x,y)>0 if (x,y)∈F, and W(x,y)=0 otherwise, where x,y∈P∪T. E={e[αg1]1,e[αg2]2,…,e[αgn]n} is a set of external events. S is a function defined from Ts to E. M0 is an initial marking.As stated,N=(P,T,F,W) is a generalized PN and Nl is its corresponding LSPN. It means [N]=[Nl]. ∀t∈Ts, t is controlled by an external event e[αgi]i in Nl and ∀t∈Tn, t is a nonsynchronized transition in Nl. In other words, the transitions in Tn are not controlled by any external event, whose firing coincides with those in generalized PNs. Tn≠∅ (resp., Ts≠∅) means that there necessarily exists at least a nonsynchronized (resp., synchronized) transition in an LSPN.The method of confusion control in a PN is mapping the PN into an LSPN such that the behavior of confusions cannot occur, which contains the following two steps:(1)
If a CIC (N¯,M¯) is known in a PN, Algorithm 15 is performed with the input (N¯,M¯). If a CDC (N¯′,M¯′) is known in a PN, Algorithm 16 is performed with the input (N¯′,M¯′). Then, for any transition ti in confusions, we obtain a function S(ti). In other words, the external events that control confusions are obtained.(2)
The obtained external events are applied to the LSPN of the PN by assigning the setE of external events and the function S.


### 3.3. Control of Confusions in LSPNs: An Example

An automated manufacturing system (AMS) is taken as an example to demonstrate the proposed confusion control methods. An AMS is composed of machining tools, buffers, conveyers, and robots. Several raw and semifinished parts are manufactured through predefined routes. The realization of resource allocation depends on conflicts and concurrency. Hence, confusions may appear in an AMS, which can lead to the loss of decision-making information.A flexible assembly cell is shown in Figure17(a). The description of the operations to be performed in the cell is stated as follows. Robot R1 loads raw Part 1 to machine tool M1. After being processed by machine tool M1, a semifinished Part 1 is produced and stored in buffer B1. The semifinished Part 1 is loaded into machine tool M2 when the part is moved by robot R1 from conveyors C1 to C3. After this stage, a finished Part 1 is obtained. Correspondingly, machine tools M1, M2 and robot R1 can be considered as shared resources, where M1 (resp., M2) can process two (resp., three) raw parts simultaneously. Part 2 is also produced by them. First, machine tool M1 loads raw Part 2. The produced semifinished Part 2 is stored in buffer B2. Then, robot R1 moves semifinished Part 2 from conveyors C2 to C4. At this moment, the semifinished Part 2 is available and is loaded by machine tool M2. After this stage, a finished Part 2 is obtained. The PN model (N,M0) of the cell is shown in Figure 17(b) and the detailed descriptions are shown in Table 1. The net is bounded and live.Table 1
Descriptions of the system model shown in Figure17(b).
Element
Meanings
p
0
Raw Part 1 is available and conveyor belt C1 requests robot R1
p
1
Machine tool M1 is working
p
2
Semifinished Part 1 is stored in buffer B1
p
3
Robot R1 is working
p
4
Semifinished Part 1 is available
p
5
Machine tool M2 is working
p
6
Raw Part 2 is available
p
7
Machine tool M1 is working
p
8
Semifinished Part 2 is stored in buffer B2 and conveyor belt C2 requests robot R1
p
9
Robot R1 is working
p
10
Semifinished Part 2 is available
p
11
Machine tool M2 is working
p
12
Machine tool M1 is available
p
13
Robot R1 is available
p
14
Machine tool M2 is available
t
0
Robot R1 responds to conveyor belt C1 and machine tool M1 begins working
t
1
The working of machine tool M1 is finished
t
2
Move semifinished Part 1 with robot R1 from conveyor belts C1 to C3
t
3
Conveyor belt C1 releases robot R1
t
4
Machine tool M2 begins working
t
5
The working of machine tool M2 is finished, and the finished Part 1 is available
t
6
Machine tool M1 begins working
t
7
The working of machine tool M1 is finished
t
8
Robot R1 responds to conveyor belt C2 and moves semifinished Part 2 from conveyor belts C2 to C4
t
9
Conveyor belt C2 releases robot R1
t
10
Machine tool M2 begins working
t
11
The working of machine tool M2 is finished and the finished Part 2 is availableFigure 17
(a) A flexible assembly cell and (b) its Petri net model (N,M0).
(a)
(b)Two confusions exist in the PN, which are shown in Figures18(a) and 18(c). The marked subnet (N¯1,M¯1) with M¯1=3p0+p6+2p8+2p12+3p13 depicted in Figure 18(a) is a CDC. It contains two structural conflicts K1=〈p12,{t0,t6}〉 and K2=〈p13,{t0,t8}〉. K1 at marking M¯1 produces a general conflict K1M¯1={p12,{t0,t6},M¯1}, where two ECRSs σ1=[t0t6] and σ2=[(t0)2] can be used to make decisions. Firing σ1 implies that a raw Part 1 and a raw Part 2 are processed by machine tool M1. In other words, two processes for the production of two different finished parts start simultaneously. The firing of σ2 means that two raw Parts 2 are processed by machine tool M1. Finished Parts 2 are produced only and M1 can process two parts at a moment. As stated previously, two ECRSs σ1=[t0t6] and σ2=[(t0)2] can be used to make decisions. However, transitions t6 and t8 are concurrent. If t8 fires before t6, two tokens in place p13 are removed. Consequently, t0 becomes 1-enabled. The decision for σ2=[(t0)2] cannot be performed. In other words, the information loss of K1M¯1 occurs.Figure 18
(a) A CDC(N¯1,M¯1) and its control, (b) the structure of a CIC N¯2, and (c) a CIC (N¯3,M¯3) and its control.
(a)
(b)
(c)For this assembly cell, suppose that both production processes are expected to work. The decision onσ1 is made. By Algorithm 16 with the input (N¯1,M¯1), we can obtain three functions; that is, S(t0)=e[1]1, S(t6)=e[1]1, and S(t8)=e[1]2, and the event dependency relation e[αg1]1≫e[αg2]2.The marked subnet(N¯3,M¯3) with M¯3=3p4+p9+2p10+3p14 shown in Figure 18(c) is a CIC that contains a structural conflict K3=p14,t4,t10. The general conflict K3M¯3=p14,t4,t10,M¯3 with the information content ψ(K3M¯3)=4 occurs at submarking M¯3, which is not the general conflict with the maximal information content in the CIC. Transitions t4 and t9 are concurrent at M¯3. If t9 fires, we obtain another general conflict K3M¯4=p14,t4,t10,M¯4 with ψ(K3M¯4)=5 at submarking M¯4=3p4+3p10+3p14. The general conflict needs to be resolved since ψ(K3M¯4)=5 is the maximal information content in the evolution of the CIC.Two ECRSsσ3=[t4t10] and σ4=[(t10)3] can be used to make decisions. If σ3 is selected to fire, semifinished Parts 1 and 2 are processed by machine tool M2 simultaneously. The decision coincides with σ1=[t0t6] of the general conflict K1M¯1 in (N¯1,M¯1), which makes both production processes work. If σ4 is selected to fire, only semifinished Parts 2 can be processed by machine tool M2.Suppose that the ECRSσ3=[t4t10] is the decision to be made. By Algorithm 15 with the input (N¯3,M¯3), we can obtain three functions; that is, S(t4)=e[1]4, S(t9)=e[1]3, and S(t10)=e[1]4, and the event dependency relation e[αg3]3≫e[αg4]4.All the obtained external events and the event dependency relations are added to the original PN to control the two confusions (N¯1,M¯1) and (N¯3,M¯3). Then an LSPN without the behavior of confusions is finally obtained, where Tn={t1,t2,t3,t5,t7,t11}, Ts={t0,t4,t6,t8,t9,t10}, and E={eαg11,eαg22,eαg33,eαg44}.Figure18(b) shows a subnet N¯2 of a CIC obtained by the detection algorithms in the next section. In the subnet, the information loss of the general conflicts associated with K3=〈p14,{t4,t10}〉 does not occur. Hence, confusion control is not applied to N¯2.In this paper, the integrity of decision-making information of a general conflict is ensured such that a system designer can make a decision based on all ECRSs. In a real-world system, the decisions on ECRSs are made by control engineers. If two inappropriate ECRSs are selected, the system may lead to deadlocks. For example, in the considered assembly cell,σ1=[t0t6] and σ4=[(t10)3] are ECRSs for general conflicts K1M¯1 and K3M¯4, respectively. If K1M¯1 and K3M¯4 are resolved according to ECRSs σ1 and σ4, respectively, the system will be in a deadlock state since transition t4 becomes disabled by the control of e[0]4. Consecutively, transition t0 becomes disabled. Then, transition t6 is not allowed to fire although it is enabled since t0 and t6 are synchronized by the control of e[1]1. The problem can be solved by classifying ECRSs according to the relations among conflicts. They will be considered in our future work.On the other hand, the proposed control methods can be applied to industrial cases since any external event can be designed as a controller according to a feedback control structure. First, a monitor is designed to observe whether the enabling degree of a transition is equal to the allowable enabling degree. Then, a controller is designed as a trigger that can output control information to transitions. The event dependency relations can be performed by designing counters.


## 3.1. Control of General Conflicts in Synchronized PNs

The resolution control of a general conflict is to choose a transition sequence such that the general conflict can be resolved according to the selected sequence to reach an expected marking.The resolution control is illustrated by an example.KM=p1,t1,t2,3p1+2p2 shown in Figure 13(a) is a general conflict at marking M=3p1+2p2. Figure 13(b) depicts KM in the corresponding synchronized net Ns of N with S(t1)=e[α1]1 and S(t2)=e[α2]1. The resolution control of KM means to make decision on firing times of transitions t1 and t2. In other words, the values of α1 and α2 are determined such that a resolution sequence of KM fires. Figures 13(c) and 13(d) show two feasible control policies.Figure 13
Illustration of the control of resolution sequences in a general conflict.
(a)
(b)
(c)
(d)If functionsS(t1)=e[α1]1=e[2]1 and S(t2)=e[α2]1=e[1]1 are employed, the general conflict KM will fire resolution sequence σ1=[(t1)2t2] in a net system (N,M). If S(t1)=e[α1]1=e[1]1 and S(t2)=e[α2]1=e[2]1 are applied, the resolution sequence σ2=[t1(t2)2] is ensured to fire in (N,M).In a general conflict, some resolution sequences can lead to the same output marking, which have different transition firing orders. In these resolution sequences, the synchronized one is unique, which is used to resolve the general conflict in synchronized PNs. For example,σ1=t1(t2)2, σ2=t2t1t2, σ3=(t2)2t1, and σ4=[t1(t2)2] are four resolution sequences of the general conflict shown in Figure 13(a). Firing any of them leads to the same output marking. In this example, σ4 is used to resolve the general conflict in the synchronized PN.A strategy to find all synchronized resolution sequences for a general conflict is proposed. LetT(e[αgi]i,M) be the set of transitions that are controlled by the external event e[αgi]i at marking M. Let a and b be two vectors. Notation a≥b means for every i, a(i)≥b(i) and a⪈b means for every i, a(i)≥b(i) and for at least one i, a(i)>b(i).Definition 13.
The sequenceσk is said to be an elementary conflict resolution sequence (ECRS) with an external event e[αgi]i in (Ns,M) if it meets the following four conditions:(1)
All the transitions inσk belong to T(e[αgi]i,M).(2)
All the transitions inσk belong to T(KM).(3)
[Ns]-·σk→≤M, where [Ns]- with [Ns]-(p,t)=W(p,t) is the output incidence matrix and σk→ is the Parikh vector of σk.(4)
There is no sequenceσ^k such that σ^k→⪈σk→.An ECRS of a general conflict in a net(Ns,M) corresponds to a synchronized resolution sequence. Conditions (1) and (2) in Definition 13 guarantee that the fundamental elements (transitions) in an ECRS are controlled by e[αgi]i at marking M and the transitions are in the set of general conflicting transitions. Condition (3) in Definition 13 ensures that the conflicting transitions in T(KM) according to the ECRS are feasible (the tokens in places meet the firing condition of their output transitions in σk). Finally, according to condition (4) in Definition 13, σk is ensured as a resolution sequence of the general conflict KM. In other words, all conflicting transitions become disabled if σk fires. Algorithm 14 is proposed to generate all ECRSs of a synchronized PN at a marking.Algorithm14 is illustrated through an example shown in Figure 14 in which the weight of each arc equals one for the sake of simplicity since the weights do not affect the function of Algorithm 14. Actually, a weight means a coefficient in the computation of enabling degrees. A synchronized PN (Ns,M) is shown in Figure 14(a), where M=3p2+2p3+2p4+p6. Transitions from t1 to t4 are controlled by an external event e[αg1]1 outputting the functions from S(t1)=e[α1]1 to S(t2)=e[α4]1, respectively. Transition t5 is controlled by another external event e[αg2]2 with S(t5)=e[α5]2. The values of allowable enabling degrees of conflicting transitions can be obtained according to the firing times of the transitions in every ECRS.Figure 14
Application of Algorithm14 to a PN Ns.Algorithm 14 (generation of all ECRSs of a synchronized PN(Ns,M)).
Input is as follows:(Ns,M) and e[αgi]i. //e[αgi]i is an external event and employed in Ns at marking M.
Output is as follows: all ECRSs:
Step 1: delete all transitions not belonging toT(e[αgi]i,M) and their input and output arcs according to condition (1) in Definition 13.
Step 2: according to condition (2) in Definition13, delete all the transitions not belonging to T(KM) and their input and output arcs.
Step 3: delete all the arcs from transitions to places since an ECRS is related to the output matrix only according to condition (3) in Definition13. the reduction leads to a new synchronized PN N¯s. All the transitions in N¯s are conflicting transitions.
Step 4: construct the reachability graph of(N¯,M). Then, each deadlock marking implies an ECRS. //(N¯,M) is the generalized PN with [N¯]=[N¯s].
Step 5: output the ECRSs.First, the input of Algorithm14 is (Ns,M) and the external event e[αg1]1. After Step 1 in Algorithm 14, a subnet of Ns is obtained as shown in Figure 14(b), where transition t5 and its corresponding arcs in Ns are removed since t5 is not controlled by e[αg1]1. Then, transitions t1, t4, and their corresponding arcs are removed by Step 2 in Algorithm 14 since they are not conflicting transitions, which is depicted in Figure 14(c). The subnet N¯s of Ns can be found as shown in Figure 14(d) according to Step 3 in Algorithm 14.The generalized PN(N¯,M) with [N¯]=[N¯s] contains a general conflict KM=p2,t2,t3,3p2+2p3+2p4+p6. Its reachability graph is shown in Figure 14(e). There are three deadlock markings that correspond to three different ECRSs σ1=[(t2)3], σ2=[t2(t3)2], and σ3=[(t2)2t3], respectively. Each ECRS can deduce the values of α1, α2, α3, and α4 on external event e[αg1]1. For example, σ2=[t2(t3)2] is an ECRS of KM, which means that KM can be resolved by firing transitions t2 once, and t3 twice simultaneously. Hence, α1=0, α2=1, α3=2, and α4=0 are obtained. The external event e[αg1]1 with the four allowable enabling degrees can perform control such that the transitions in KM fire according to the ECRS σ2 at marking M.The validity of Algorithm14 is clear since the reachability graph of the PN that is composed of a general conflict only contains all feasible paths from an initial marking to all dead markings.


## 3.2. Control of Confusions Using External Events

As stated in Section2, a confusion is prone to the information loss of general conflicts owing to nondeterministic firing orders of concurrent transitions. In a CIC, a general conflict KM with maximal information content is implied in the evolution of markings. The marking M at which the general conflict KM occurs is expected. It should be ensured that the firing of a transition sequence can reach the marking M. Also, the transition firing sequences that lead to the information loss of the general conflict KM should be avoided.If a general conflictKM with maximal information content in a confusion occurs, all the ECRSs are needed and can be obtained. Furthermore, an ECRS is selected as a decision to generate the allowable enabling degrees of transitions. The general conflict KM can always be resolved according to the selected ECRS by the control of external events. Here we assume that confusions have been found at a marking and we aim to control them. Algorithm 15 is proposed to control a given CIC.Algorithm 15 (general conflict control in CIC(N¯,M¯)).
Input is as follows:(N¯,M¯).
Output is as follows: outputS(ti), ∀ti∈T¯, and the dependency relation between e[αgj]j and e[αgk]k // T¯ is the set of transitions in N¯. S is a function mapping from T¯ to E. E={e[αgj]j,e[αgk]k} is a set of external events with j≠k:
Step 1: find the setT(K) of the structural conflicting transitions in N¯. Let H=T¯∖T(K). ∀ti∈H, design a function Sti=eαij. ∀ti∈T(K), design a function S(ti)=e[αi]k.
Step 2:∀ti∈H, αi:=qiM¯. //qiM¯ is the enabling degree of ti at the submarking M¯.
Step 3: design the dependency relatione[αgj]j≫e[αgk]k.
Step 4: obtain the submarkingM¯′ by firing all transitions in H at M¯ according to their enabling degrees.
Step 5: find all ECRSs of(N¯,M¯′) by Algorithm 14 with the inputs (N¯,M¯′) and e[αgk]k.
Step 6: choose an ECRS. For any transitionti in T(K), obtain the allowable enabling degree αi by the ECRS.
Step 7: outputS(ti), ∀ti∈T¯, and e[αgj]j≫e[αgk]k.When the general conflict of a CIC is identified at making, its control can be enforced by adding external events according to some of the established rules. Algorithm15 presents the rules. In Step 1 of Algorithm 15, the transition set T¯ of a CIC is partitioned into two parts T(K) and H=T¯∖T(K). According to Definition 11, a CIC occurs if the transitions in T(K) fire before those in H. Hence, Algorithm 15 designs a dependency relation by Step 3 in Algorithm 15 between the event controlling the transitions in H and the event controlling the transitions in T(K) such that, ∀ti∈H, ∀tj∈T(K), ti fires qiM¯ times before firing tj. If the transitions in H fire according to their enabling degrees, the general conflict associated with K with the maximal information content is obtained. We can obtain all ECRSs according to Algorithm 14. Any ECRS is a control policy. Then, an ECRS is selected and the allowable enabling degrees of conflicting transitions to perform this ECRS can be obtained. Finally, the output functions and the event dependency relation presented in Step 7 of Algorithm 15 can control the CIC such that the information loss of the general conflict that has the maximal information content does not occur.The CICCin(N¯1,T(K1),M¯1,DM¯1) in Example 1 is also depicted in Figure 15(a) to illustrate Algorithm 15, where T(K1)={t1,t2}, M¯1=p1+2p2+4p4, DM¯1={D1M¯1}, and D1M¯1={t1,t3}. By the analysis in Section 2, the general conflict K1M¯5=〈p2,{t1,t2},M¯5〉 at the submarking M¯5=p1+2p2+4p3 has the maximal information content ψ(K1M¯5)=3. Transitions t1 and t3 are concurrent.Figure 15
Illustration of the control of confusions using external events: (a) a CIC (N¯1,M¯1), (b) application of Algorithm 15 to (N¯1,M¯1), (c) a CDC (N¯3,M¯1), and (d) application of Algorithm 16 to (N¯3,M¯1).The information loss ofK1M¯5 in the CIC occurs if the conflicting transition t1 fires before firing transition sequence (t3)4. For example, the firing of the sequence σ1=t1(t3)4, σ2=t3t1(t3)3, σ3=(t3)2t1(t3)2, or σ4=(t3)3t1t3 at the initial submarking M¯1 causes the information loss of K1M¯5. On the contrary, the information loss of K1M¯5 does not occur in the CIC if the transition sequence (t3)4 fires before firing t1. For example, the firing of the sequence σ5=(t3)4t1 does not cause the information loss since the submarking M¯5 leading to K1M¯5 can be reached through firing the sequence σ5=(t3)4t1 from M¯1, that is, M¯1[(t3)4〉M¯5[t1〉M¯10. The control processes for this confusion contain the following steps according to Algorithm 15:(1)
Two setsT(K)={t1,t2} and H={t3} are obtained. Let t1, t2, and t3 be controlled by e[α1]2, e[α2]2, and e[α3]1, respectively (Step 1). // Suppose that j=1 and k=2.(2)
The allowable enabling degree of transitiont3 is obtained by α3=q3M¯1=4 (Step 2).(3)
The dependency relatione[αg1]1≫e[αg2]2 is assigned (Step 3).(4)
The submarkingM¯5=p1+2p2+4p3 is reached by firing t3 four times (Step 4).(5)
Two ECRSsσ1=[t1t2] and σ2=[(t2)2] of the general conflict K1M¯5 are obtained by Algorithm 14 (Step 5).(6)
The ECRSσ1 is selected. We have the allowable enabling degrees α1=α2=1 by the ECRS (Step 6).(7)
Three functionsS(t1)=e[1]2, S(t2)=e[1]2, and S(t3)=e[4]1 are obtained. The dependency relation e[αg1]1≫e[αg2]2 needs to be applied (Step 7).Finally, the controlled CIC is shown in Figure 15(b), where only the transition sequence σ=(t3)4[t1t2] can fire. The information loss of K1M¯5 is prevented.The structure of a CDC is composed of two structural conflicts. However, only one structural conflict can be used to analyze the information loss of general conflicts in the CDC, which is illustrated with the example shown in Figure16.Figure 16
Schema of a CDC (N¯,M¯) without considering the weights of arcs, where Kg1=p1,p1•, Kg2=〈p2,p2•〉, Ω∗=T(Kg1)∩T(Kg2), Ω1=T(Kg1)∖Ω∗, and Ω2=T(Kg2)∖Ω∗.Figure16 shows the schema of a CDC (N¯,M¯) without considering the weights of arcs, where Kg1=p1,TKg1 with T(Kg1)=p1• and Kg2=p2,TKg2 with T(Kg2)=p2• are two structural conflicts in the CDC. Let Kg1M¯ and Kg2M¯ be two general conflicts associated with Kg1 and Kg2 at submaking M¯, respectively. All transitions in (N¯,M¯) are partitioned into three subsets Ω∗=T(Kg1)∩T(Kg2), Ω1=T(Kg1)∖Ω∗, and Ω2=T(Kg2)∖Ω∗. Let DM¯={D1M¯,D2M¯,…,D|Ω1|·Ω2M¯} denote the set of 2-max-concurrent transition sets of (N¯,M¯). ∀ti∈Ω1, ∀tk∈Ω2, transitions ti and tk are concurrent.According to Definition11, ∀ti∈Ω1, ∀tk∈Ω2, ∃DjM¯={ti,tk}∈DM¯, we have ti∈T(Kg1)∩DjM¯ and tk∈DjM¯∖T(Kg1) such that the information loss of Kg1M¯ occurs by firing the sequence σ=tkti. However, we also have tk∈T(Kg2)∩DjM¯ and ti∈DjM¯∖T(Kg2) such that the firing of the same sequence σ=tkti does not cause the information loss of Kg2M¯. Hence, the contradiction occurs. For a CDC, only one structural conflict can be used to analyze the information loss of general conflicts in the CDC.Algorithm 16 (general conflict control in CDC(N¯,M¯)).
Input is as follows:(N¯,M¯).
Output is as followd:S(ti), ∀ti∈T¯, and the dependency relation between e[αgj]j and e[αgk]k // T¯ is the set of transitions in N¯. S is a function mapping from T¯ to E. E={e[αgj]j,e[αgk]k} is a set of external events with j≠k:
Step 1:∀ti∈T¯, design a function S(ti)=e[αi]j. Find all ECRSs of (N¯,M¯) by Algorithm 14 with the inputs (N¯,M¯) and e[αgj]j. Choose an ECRS. For any transition ti that meets S(ti)=e[αi]j, obtain the allowable enabling degree αi by the ECRS.
Step 2: find the two setsT(Kg1) and T(Kg2) of the structural conflicting transitions in N¯. Let Ω∗=T(Kg1)∩T(Kg2), Ω1=T(Kg1)∖Ω∗, and Ω2=T(Kg2)∖Ω∗. // The structure of any CDC is composed of two structural conflicts.
Step 3: choose a set of structural conflict transitions. IfT(Kg1) is considered, go to Step 4; else go to Step 5. // Determine a structural conflict to be controlled.
Step 4:∀ti∈Ω2, replace the function S(ti)=e[αi]j with S(ti)=e[αi]k. Go to Step 6.
Step 5:∀ti∈Ω1, replace the function S(ti)=e[αi]j with S(ti)=e[αi]k. Go to Step 6.
Step 6: design the the dependency relatione[αgj]j≫e[αgk]k.
Step 7: outputS(ti), ∀ti∈T¯ and e[αgj]j≫e[αgk]k.When a CDC is detected, its structure is known [18]. According to Figure 16, any CDC contains two general conflicts in which one is focused to control. Hence, Algorithm 16 designs rules to add external control events such that the focused general conflict can be resolved before the other. Algorithm 16 achieves this purpose. First, the partition of the transitions in a CDC (N¯,M¯) is performed. Let us consider the structural conflict Kg1. The information loss of the corresponding general conflict Kg1M¯ occurs if the transitions in Ω2 (Ω2⊈T(Kg1)) fire before the resolution of Kg1M¯. On the contrary, the information loss of Kg1M¯ does not occur if Kg1M¯ is resolved before the transitions in Ω2 fire. Hence, Algorithm 16 designs a dependency relation between the event controlling the transitions in T(Kg1) and that controlling the transitions in Ω2, which also assigns the allowable enabling degrees of the transitions in T(Kg1) to resolve the general conflict Kg1M¯. Finally, the output functions and the dependency relation can control the CDC such that the information loss of Kg1M¯ does not occur.TheCde-conf Cde(N¯3,T(K3),M¯1,DM¯1) in Example 3 is also illustrated in Figure 15(c), where K3=〈p1,T(K3)〉, T(K3)={t1,t2}, M¯1=2p1+3p2, DM¯1={D1M¯1}, and D1M¯1={t1,t3}. In this case, K3 is focused only. By the analysis in Section 2, K3M¯1=〈p1,{t1,t2},2p1+3p2〉 is a general conflict with the maximal information content ψ(K3M¯1)=3 at the initial submarking M¯1. The decisions on K3M¯1 are made. However, t1 and t3 are concurrent. The information loss of K3M¯1 does not occur unless transition t3 fires after the general conflict K3M¯1 is resolved. The control processes for this CDC contain the following steps according to Algorithm 16:(1)
Three functionsS(t1)=e[α1]1, S(t2)=e[α2]1, and S(t3)=e[α3]1 are obtained. Two ECRSs σ1=[t1t2] and σ2=[(t1)2t3] are obtained by Algorithm 14. Suppose that ECRS σ2 is selected. Three allowable enabling degrees α1=2, α2=0, and α3=1 are assigned (Step 1). // Suppose that j=1 and k=2.(2)
Five setsT(Kg1)={t1,t2}, T(Kg2)={t2,t3}, Ω∗={t2}, Ω1={t1}, and Ω2={t3} are obtained (Step 2).(3)
T(Kg1)={t1,t2}; that is, T(K3) in Example 3 in Section 2 is selected (Step 3).(4)
The functionS(t3)=e[1]1 is replaced by S(t3)=e[1]2 (Step 4).(5)
The dependency relatione[αg1]1≫e[αg2]2 is assigned (Step 6).(6)
Three functionsS(t1)=e[2]1, S(t2)=e[0]1, and S(t3)=e[1]2 are obtained. The dependency relation e[αg1]1≫e[αg2]2 needs to be applied (Step 7).Finally, the controlled CDC is obtained as shown in Figure15(d), where only transition sequence σ=[(t1)2]t3 can fire. K3M¯1 can be resolved before t3 fires.The computational complexity of Algorithms14, 15, and 16 is analyzed. First, the reachability graph of a synchronized PN to compute ECRSs is necessary, which is the main cost in Algorithms 14, 15, and 16. However, the reachability graph for a general conflict is only a small part of that of the whole PN, which is necessary to find all synchronized resolution sequences. Second, in Algorithms 15 and 16, finding the structural conflicts in a confusion (N¯,M¯) and partitioning the transitions in T¯ are involved. For the former, structural conflicts can be found by scanning the incidence matrix [N¯], which can be completed in O(mn) time, where m and n are the numbers of places and transitions in N¯, respectively. For the latter, the partitions follow the basic operations of sets, which can be completed in O(n2) time.Third, adding and outputting external events of transitions in Algorithms15 and 16 can be completed in O(n2) time. The computational complexity of adding external events to the transitions in N¯ is considered. According to the constructions in Figure 12, only 5 elements (two transitions and three places) are needed for an external event to control a transition in N¯. In the worst case, we need n external events to control totally n transitions in N¯. In other words, 5·n elements in total are added by adding rows and columns in the incidence matrix [N¯], which can be completed in O(n2) time since the number of rows and columns added has linear relation with the number n of transitions.Finally, Algorithm15 or Algorithm 16 outputs an event dependency relation for the two external events in a confusion subnet. According to the constructions in Figure 12, only 5 elements (two transitions and three places) are used to represent the event dependency relation. The number of elements added for the event dependency relation has no relation with the numbers m of places and n transitions in N¯. Hence, adding an event dependency relation in Algorithm 15 or Algorithm 16 can be completed in O(1) time.The control strategies (Algorithms14, 15, and 16) of confusions are based on synchronized PNs in which any transition is controlled by an external event. The strategies are applied to generalized PNs. It is unnecessary to control the transitions not in confusions by external events. Hence a class of local synchronized PNs (LSPNs) is proposed.Definition 17.
A marked LSPN is a seven-tupleNl=(P,T,F,W,E,S,M0), where P and T=Tn∪Ts (Tn≠∅ and Ts≠∅ are the sets of nonsynchronized and synchronized transitions, resp.) are finite, nonempty, and disjoint sets. F⊆(P×T)∪(T×P) is called a flow relation of the net. W:(P×T)∪(T×P)→N is a mapping that assigns a weight to an arc: W(x,y)>0 if (x,y)∈F, and W(x,y)=0 otherwise, where x,y∈P∪T. E={e[αg1]1,e[αg2]2,…,e[αgn]n} is a set of external events. S is a function defined from Ts to E. M0 is an initial marking.As stated,N=(P,T,F,W) is a generalized PN and Nl is its corresponding LSPN. It means [N]=[Nl]. ∀t∈Ts, t is controlled by an external event e[αgi]i in Nl and ∀t∈Tn, t is a nonsynchronized transition in Nl. In other words, the transitions in Tn are not controlled by any external event, whose firing coincides with those in generalized PNs. Tn≠∅ (resp., Ts≠∅) means that there necessarily exists at least a nonsynchronized (resp., synchronized) transition in an LSPN.The method of confusion control in a PN is mapping the PN into an LSPN such that the behavior of confusions cannot occur, which contains the following two steps:(1)
If a CIC (N¯,M¯) is known in a PN, Algorithm 15 is performed with the input (N¯,M¯). If a CDC (N¯′,M¯′) is known in a PN, Algorithm 16 is performed with the input (N¯′,M¯′). Then, for any transition ti in confusions, we obtain a function S(ti). In other words, the external events that control confusions are obtained.(2)
The obtained external events are applied to the LSPN of the PN by assigning the setE of external events and the function S.


## 3.3. Control of Confusions in LSPNs: An Example

An automated manufacturing system (AMS) is taken as an example to demonstrate the proposed confusion control methods. An AMS is composed of machining tools, buffers, conveyers, and robots. Several raw and semifinished parts are manufactured through predefined routes. The realization of resource allocation depends on conflicts and concurrency. Hence, confusions may appear in an AMS, which can lead to the loss of decision-making information.A flexible assembly cell is shown in Figure17(a). The description of the operations to be performed in the cell is stated as follows. Robot R1 loads raw Part 1 to machine tool M1. After being processed by machine tool M1, a semifinished Part 1 is produced and stored in buffer B1. The semifinished Part 1 is loaded into machine tool M2 when the part is moved by robot R1 from conveyors C1 to C3. After this stage, a finished Part 1 is obtained. Correspondingly, machine tools M1, M2 and robot R1 can be considered as shared resources, where M1 (resp., M2) can process two (resp., three) raw parts simultaneously. Part 2 is also produced by them. First, machine tool M1 loads raw Part 2. The produced semifinished Part 2 is stored in buffer B2. Then, robot R1 moves semifinished Part 2 from conveyors C2 to C4. At this moment, the semifinished Part 2 is available and is loaded by machine tool M2. After this stage, a finished Part 2 is obtained. The PN model (N,M0) of the cell is shown in Figure 17(b) and the detailed descriptions are shown in Table 1. The net is bounded and live.Table 1
Descriptions of the system model shown in Figure17(b).
Element
Meanings
p
0
Raw Part 1 is available and conveyor belt C1 requests robot R1
p
1
Machine tool M1 is working
p
2
Semifinished Part 1 is stored in buffer B1
p
3
Robot R1 is working
p
4
Semifinished Part 1 is available
p
5
Machine tool M2 is working
p
6
Raw Part 2 is available
p
7
Machine tool M1 is working
p
8
Semifinished Part 2 is stored in buffer B2 and conveyor belt C2 requests robot R1
p
9
Robot R1 is working
p
10
Semifinished Part 2 is available
p
11
Machine tool M2 is working
p
12
Machine tool M1 is available
p
13
Robot R1 is available
p
14
Machine tool M2 is available
t
0
Robot R1 responds to conveyor belt C1 and machine tool M1 begins working
t
1
The working of machine tool M1 is finished
t
2
Move semifinished Part 1 with robot R1 from conveyor belts C1 to C3
t
3
Conveyor belt C1 releases robot R1
t
4
Machine tool M2 begins working
t
5
The working of machine tool M2 is finished, and the finished Part 1 is available
t
6
Machine tool M1 begins working
t
7
The working of machine tool M1 is finished
t
8
Robot R1 responds to conveyor belt C2 and moves semifinished Part 2 from conveyor belts C2 to C4
t
9
Conveyor belt C2 releases robot R1
t
10
Machine tool M2 begins working
t
11
The working of machine tool M2 is finished and the finished Part 2 is availableFigure 17
(a) A flexible assembly cell and (b) its Petri net model (N,M0).
(a)
(b)Two confusions exist in the PN, which are shown in Figures18(a) and 18(c). The marked subnet (N¯1,M¯1) with M¯1=3p0+p6+2p8+2p12+3p13 depicted in Figure 18(a) is a CDC. It contains two structural conflicts K1=〈p12,{t0,t6}〉 and K2=〈p13,{t0,t8}〉. K1 at marking M¯1 produces a general conflict K1M¯1={p12,{t0,t6},M¯1}, where two ECRSs σ1=[t0t6] and σ2=[(t0)2] can be used to make decisions. Firing σ1 implies that a raw Part 1 and a raw Part 2 are processed by machine tool M1. In other words, two processes for the production of two different finished parts start simultaneously. The firing of σ2 means that two raw Parts 2 are processed by machine tool M1. Finished Parts 2 are produced only and M1 can process two parts at a moment. As stated previously, two ECRSs σ1=[t0t6] and σ2=[(t0)2] can be used to make decisions. However, transitions t6 and t8 are concurrent. If t8 fires before t6, two tokens in place p13 are removed. Consequently, t0 becomes 1-enabled. The decision for σ2=[(t0)2] cannot be performed. In other words, the information loss of K1M¯1 occurs.Figure 18
(a) A CDC(N¯1,M¯1) and its control, (b) the structure of a CIC N¯2, and (c) a CIC (N¯3,M¯3) and its control.
(a)
(b)
(c)For this assembly cell, suppose that both production processes are expected to work. The decision onσ1 is made. By Algorithm 16 with the input (N¯1,M¯1), we can obtain three functions; that is, S(t0)=e[1]1, S(t6)=e[1]1, and S(t8)=e[1]2, and the event dependency relation e[αg1]1≫e[αg2]2.The marked subnet(N¯3,M¯3) with M¯3=3p4+p9+2p10+3p14 shown in Figure 18(c) is a CIC that contains a structural conflict K3=p14,t4,t10. The general conflict K3M¯3=p14,t4,t10,M¯3 with the information content ψ(K3M¯3)=4 occurs at submarking M¯3, which is not the general conflict with the maximal information content in the CIC. Transitions t4 and t9 are concurrent at M¯3. If t9 fires, we obtain another general conflict K3M¯4=p14,t4,t10,M¯4 with ψ(K3M¯4)=5 at submarking M¯4=3p4+3p10+3p14. The general conflict needs to be resolved since ψ(K3M¯4)=5 is the maximal information content in the evolution of the CIC.Two ECRSsσ3=[t4t10] and σ4=[(t10)3] can be used to make decisions. If σ3 is selected to fire, semifinished Parts 1 and 2 are processed by machine tool M2 simultaneously. The decision coincides with σ1=[t0t6] of the general conflict K1M¯1 in (N¯1,M¯1), which makes both production processes work. If σ4 is selected to fire, only semifinished Parts 2 can be processed by machine tool M2.Suppose that the ECRSσ3=[t4t10] is the decision to be made. By Algorithm 15 with the input (N¯3,M¯3), we can obtain three functions; that is, S(t4)=e[1]4, S(t9)=e[1]3, and S(t10)=e[1]4, and the event dependency relation e[αg3]3≫e[αg4]4.All the obtained external events and the event dependency relations are added to the original PN to control the two confusions (N¯1,M¯1) and (N¯3,M¯3). Then an LSPN without the behavior of confusions is finally obtained, where Tn={t1,t2,t3,t5,t7,t11}, Ts={t0,t4,t6,t8,t9,t10}, and E={eαg11,eαg22,eαg33,eαg44}.Figure18(b) shows a subnet N¯2 of a CIC obtained by the detection algorithms in the next section. In the subnet, the information loss of the general conflicts associated with K3=〈p14,{t4,t10}〉 does not occur. Hence, confusion control is not applied to N¯2.In this paper, the integrity of decision-making information of a general conflict is ensured such that a system designer can make a decision based on all ECRSs. In a real-world system, the decisions on ECRSs are made by control engineers. If two inappropriate ECRSs are selected, the system may lead to deadlocks. For example, in the considered assembly cell,σ1=[t0t6] and σ4=[(t10)3] are ECRSs for general conflicts K1M¯1 and K3M¯4, respectively. If K1M¯1 and K3M¯4 are resolved according to ECRSs σ1 and σ4, respectively, the system will be in a deadlock state since transition t4 becomes disabled by the control of e[0]4. Consecutively, transition t0 becomes disabled. Then, transition t6 is not allowed to fire although it is enabled since t0 and t6 are synchronized by the control of e[1]1. The problem can be solved by classifying ECRSs according to the relations among conflicts. They will be considered in our future work.On the other hand, the proposed control methods can be applied to industrial cases since any external event can be designed as a controller according to a feedback control structure. First, a monitor is designed to observe whether the enabling degree of a transition is equal to the allowable enabling degree. Then, a controller is designed as a trigger that can output control information to transitions. The event dependency relations can be performed by designing counters.


## 4. Conclusions and Future Work

This paper investigates confusion issues in generalized PNs. Two problems are considered. The first is the formalization of confusions in generalized PNs. Confusions are well defined by proposing a novel concept of information content. Both CICs and CDCs in generalized PNs can be well described by the proposed definition.The second is the confusion control. Synchronized PNs with allowable enabling degrees and LSPNs are developed to control two classes of confusions. The work can be regarded as an effective method to control Petri nets by using Petri nets. First, the concept of ECRSs of a general conflict is proposed. Each ECRS can deduce a series of control information of external events. Second, two algorithms are proposed to automatically generate external events and the event dependency relations, which can be successfully applied to the control of confusions such that the information loss of the general conflicts in the confusions does not occur. Finally, an example of confusion detection and control in the PN model of a manufacturing cell is given. Consequently, confusions in the PN can be effectively detected and controlled by using the proposed methods.Future work includes the control of confusions in generalized PNs by an algebraic method. On the other hand, we also aim to detect confusions in a PN without computing a reachability graph. The methods can involve finding markings that are prone to the information loss of general conflicts by state estimation and structural analysis methods.



---

*Source: 636959-2015-09-16.xml*