# Model Identification of Unobservable Behavior of Discrete Event Systems Using Petri Nets

Authors: Guanghui Zhu; Ya Wang; Yajie Wang
Journal: Journal of Control Science and Engineering
 (2019)

---

## Abstract

This paper deals with the problem of identifying a Petri net that models the unobservable behavior of a system from the knowledge of its dynamical evolution. We assume that a partial Petri net model that represents the observable behavior of a system is given in which all the transitions are observable. An identifier monitors the system evolution and records the observed transition sequence (and possible corresponding markings). Some unobservable transitions modeling the unknown system behavior are identified from the transition sequence by formulating and solving integer linear programming problems. These identified unobservable transitions together with the given partial Petri net model characterize the whole system, including observable and unobservable behavior. Two different cases are considered. First, we assume that no place is observable. In such a case, a transition sequence is observed only during the evolution of the system. Second, we assume that a subset of places is observable; i.e., the observation contains not only the transition sequence but the corresponding markings as well. Hence an additional constraint should be imposed on the unobservable transition in the related programming problems according to the observed markings such that a more authentic unobservable transition can be found.


---

## Body

## 1. Introduction

Dynamic systems can always be modeled as continuous time systems or discrete event systems (DESs) [1]. In the framework of DESs, the dynamic behavior of a system is usually characterized by its output in the form of numbers, symbols, text, etc. An interesting issue is to infer a system model from the knowledge of system’s output information such that its behavior can be verified, controlled [2, 3], or diagnosed [4–7]. The identification of a DES consists in determining a mathematical model from the data set of input-output signals of a system that describes all or part of the system behavior.In the DES context, the model setting for the identification problem mainly includes automata and Petri nets. In the early work, Gold [8] shows that the problem of whether there exists an automaton that agrees with the given data is NP-complete. On the basis of an automaton model, Angluin [9] presents a family of efficient algorithms for inferring thek-reversible languages from finite positive samples.Given some information on the evolution of a system, several studies discuss the identification problem of DES using Petri nets. Roughly speaking, the existing approaches can be divided into three categories: (a) given a finite language describing the system behavior, it consists in determining the structure and initial marking of a Petri net system whose language coincides with the given one [10–12], (b) given an event sequence (transition sequence) as well as the corresponding system states (markings), the goal is to determine a Petri net system such that the given event sequence is firable from its initial marking [13–15], and (c) assuming that the net to be identified has special structure (e.g., safe Petri nets) or properties (e.g., exhibiting cyclic behavior), the net is identified from finite data using the customized algorithm [16–19]. In general, an integer linear programming problem (ILPP) is defined to impose certain constraints on the structure of the net to be identified in cases (a) and (b). It may require heavy computational costs to solve an ILPP; however this technique is very general. On the other hand, a customized algorithm is designed based on the knowledge of the structure and property of the net in case (c), and the algorithm often has polynomial time complexity. Nevertheless, it can only be applied to a special class of Petri nets.Giua and Seatzu [10] present an integer programming technique for the identification of a free-labeled net, i.e., a net without an associated labelling function, from a finite prefix-closed language with the length of its longest word less than or equal to a given positive integer. In their approach, both positive examples and counterexamples can be derived from the given language, and the constraint set of the programming problem allows the positive examples but forbids the counterexamples. The approach is general, but it has high computational complexity. Cabasino et al. [11] extend this approach to the identification of adeterministicλ-free-labeled Petri net, i.e., a net where two transitions can share the same label (cannot be an empty string).Unlike the studies in [10, 11] in which no information about places is known, Dotoli et al. [13] assume that a transition sequence and the corresponding reached marking after transition fires are observed. A net system is identified by solving an ILPP such that the transition sequence is firable from its initial marking and each marking after firing a transition in the sequence equals the observed one.Hiraishi [16] proposes an approach which constructs a safe Petri net from the knowledge of firing sequences. Firstly, a finite state automaton is identified from the given firing sequences, and then the structure of the Petri net is estimated. The approach has polynomial time complexity, but it can only be applied to safe Petri nets. Bekrar et al. [19] provide an algorithm that identifies a safe Petri net from the data set of I/O signals of a system. They assume that the considered system is cyclic and all its cycles start from the same initial state. Meda et al. in [17, 18] discuss the identification problem by using Interpreted Petri nets, i.e., a Petri net associated with an input function and an output function, assuming that the dependency between transitions is known. All studies in [16–19] fall into case (c). These approaches are not general and can only be applied to Petri nets with special structure or behavior.The problems of fault diagnosis and diagnosability have received a lot of attention since the work by Sampath et al. [20]. In the context of Petri nets, it is usually assumed that the faulty model describing not only the fault-free but faulty behavior of a system is known and that the fault events are modeled by unobservable transitions [4–7]. In other words, when we build the Petri net model of a system for diagnosis, both fault-free system behavior and faulty behavior should be considered simultaneously. However, it is not realistic to figure out all possible faulty behavior when one models a system [21]. Thus an issue arises: how to identify faulty (unobservable) behavior to improve the accuracy of the faulty model. In this issue, the fault-free model is assumed to be known. We have to decide whether some unobservable behaviors occur according to the observed event sequence. To the best of our knowledge, there are few studies focusing on the identification of unobservable transitions using Petri nets.Cabasino et al. [12] propose an approach based on the work in [10] to identify the faulty (unobservable) transitions by assuming that the fault-free model is known and that the system contains at most one unobservable loop-free transition. The main idea is to define and solve an integer programming problem according to the positive examples and counterexamples that can be computed by comparing the given language and the observed language. The main drawbacks of this approach are the computational complexity and the limitation that only one unobservable transition can be identified.Dotoli et al. [15] also assume that the nominal model without unobservable transitions is known. An online approach is proposed to identify recursively an unobservable subnet from the knowledge of an observed transition sequence and the corresponding reached markings.In this paper, we extend the work in [15], where all places are assumed to be observable, to the case of partial observable places. Our work is motivated by the fact that in the practical application it is difficult to associate each place with a sensor because of the technical or financial consideration.This paper deals with the identification of unobservable transitions from the knowledge of an observed transition sequence. An identifier monitors the system and, upon the observation of a transition, an integer programming problem is solved to decide whether an unobservable transition should be introduced. If it is true, an unobservable transition is identified by solving another integer programming problem. An online algorithm is also presented to identify an unobservable subnet consisting of identified unobservable transitions.In contrast to the work [15], the proposed approach is more general since only part of places need to be observable (all places are assumed to be observable in [15]), and they have the same computational complexity. More specifically, the number τ of observable places in our approach satisfies 0≤τ≤m, where m is the number of places in a net. For τ=0, i.e., no place is observable, the observed output is a transition sequence. For 0<τ<m, i.e., a subset of places is observable, the observation is a transition-partial-marking sequence, where apartial marking is a marking of observable places. If τ=m, then the problem to solve is the same as [15].This paper is organized as follows. Section2 presents basic definitions about Petri nets as well as some preliminary results. In Section 3, we first present some results that are theoretical basis of the subsequent identification algorithm, and then an online algorithm and its computational complexity are discussed. In Section 4, we extend the algorithm to the case that some of places are observable. Finally, we conclude this paper with the further work in Section 5.


## 2. Preliminary

This section recalls basic concepts of Petri nets and some preliminary results. In addition, several definitions used in this paper are given. For more details on Petri nets, the reader is referred to [1, 22].


### 2.1. Basics of Petri Nets

A Petri net is a four-tuplePN=(P,T,Pre,Post), where P is the set of places, T is the set of transitions, Pre:P×T→N, and Post:P×T→N are the pre- and postincidence matrices, respectively, which specify the structure of the Petri net. For p∈P, t∈T, and x∈N, Pre(p,t)=x if there exists an arc with weight x from p to t, 0 otherwise; Post(p,t)=x if an arc with weight x goes from t to p, 0 otherwise. Here N is the set of nonnegative integers. We denote by m=|P| the number of places and n=T that of transitions. The incidence matrix of a net is denoted as C=Post-Pre. For t∈T, itspreset is defined as t•=p∈P∣Pre(p,t)>0, and itspostset is defined as t•=p∈P∣Post(p,t)>0. A transition t is said to be asource transition if it satisfies t•=∅. A marking of a Petri net is a vector M:P→N, and M(p) indicates the number of tokens in place p. A net system 〈PN,M0〉 is a Petri net with an initial marking M0.A transitiontj∈T isenabled at marking M if ∀p∈t•j,M(p)≥Pre(p,tj), which is denoted by Mtj. An enabled transition tj at M can fire yielding a new marking M′ such that M′=M+Post(·,tj)-Pre(·,tj), which is denoted as MtjM′. If MtjM′ holds, by the definition of incidence matrix C, we have M′=M+C(·,tj), which can be rewritten as M′=M+C·t→j, where t→j is the n-dimensional canonical basic vector and its j-th entry is one.Given a transition sequenceσ and a marking M, M[σ〉 denotes that σ is enabled at marking M and MσM′ denotes that a new marking M′ isreachable from M after firing σ. All the markings reachable from M0 comprise thereachability set of a Petri net and it is denoted as R(PN,M0). The set of sequences enabled at the initial marking M0 is denoted as(1)LPN,M0=σ∈T∗∣M0σ,which is called thelanguage of a Petri net.We define ann-dimensional column vector σ→:T→N (calledfiring vector) for the corresponding transition sequence σ such that σ→(t)=k if transition t occurs k times in σ. For an enabled transition sequence σ at M0 such that M0σM, we have the following state equation:(2)M=M0+C·σ→,which is called thestate equation of a Petri net system.


### 2.2. Labeled Petri Net

Given a Petri netPN=(P,T,Pre,Post) and the set of events E, a labeling function λ:T→E∪ε assigns to each transition t∈T either a symbol from the event set E or an empty string ε. A transition with label ε is called anunobservable transition and the set of unobservable transitions is denoted as Tu=t∈T∣λ(t)=ε with nu=Tu being the cardinality of set Tu. All other transitions whose labels are not ε comprise the set ofobservable transitionsTo=t∈T∣λ(t)≠ε and no=To. Thus the set T is divided into two disjoint subsets To and Tu with T=To∪Tu. We assume that each label e∈E can only be assigned to one transition, i.e., the set E is isomorphic to the set of observable transitions To, and thus without loss of generality we assume E=To. A place p∈P is said to beobservable if it is equipped with a sensor that allows observation of the number of its tokens.For eachσo∈To∗, we define an no-dimensional vector σ→o:To→N and σ→o(t)=k if t∈To occurs k times in σo. Analogously, for each σu∈Tu∗, an nu-dimensional vector σ→u:Tu→N is defined and σ→u(t)=k if t∈Tu occurs k times in σu.


### 2.3. Linear Reformulation

An optimization problem with an absolute value is nonlinear. Absolute value functions are not continuously differentiable, and it is difficult to perform standard optimization procedure on them. However, we can convert an absolute value function into several linear constraints such that the optimization can be solved using the standard linear programming technique. We here only consider this situation: there is an absolute value in the objective function. Let us consider the following optimization problem:(3)mina→T·absx→+b→T·y→s.t.Awhere x→ and y→ are variables in Rn and Rm, respectively, a→ and b→ are constant vectors in R≥0n and Rm, respectively, abs(x→) denotes the absolute value of vector x→, and A denotes the linear constraints in this programming problem. Note that a→ is a column vector consisting of nonnegative real numbers.Programming problem (3) can be rewritten in the form of a linear objective function as(4)mina→T·z→+b→T·y→s.t.A-x→≤z→x→≤z→z→≥0→where z→ is a variable in Rn; i.e., we add a variable z→≥0→ and two additional constraints -x→≤z→ and x→≤z→.In fact, for the real numbersx1 and z1 that are the first entries of vectors x→ and z→, respectively, there are three different cases.(1)
x1>0. Constraint -x1≤z1 is always fulfilled. Because of the constraint x1≤z1, z1 is necessarily at least as large as x1. On the other hand, z1 is in the objective function such that it trends to be as small as possible. Thus z1 will be equal to x1, i.e., z1=abs(x1).(2)
x1=0. In this case, constraints -x1≤z1 and x1≤z1 are always verified because of z1≥0. Moreover z1 is in the objective function, and thus it trends to be zero, i.e., z1=abs(x1).(3)
x1<0. Being analogous to case (1), z1=abs(x1) is trivially verified.Definition 1.
Given a Petri netPN=(P,T,Pre,Post) with T=To∪Tu, PN can be partitioned into two components denoted by PN=PNo⊗PNu. Here PNo=(P,To,Preo,Posto) is theobservable subnet, where P is the set of places, To is the set of observable transitions, and Preo and Posto are the restrictions of Pre and Post to To, respectively; PNu=(P,Tu,Preu,Postu) is theunobservable subnet, where Tu is the set of unobservable transitions and Preu and Postu are the restrictions of Pre and Post to Tu, respectively.Definition 2 (see [5]).
Considering the netPN=(P,T,Pre,Post) with T=To∪Tu, we define the following two projection operations: (i)
Qo:T∗→To∗, which is defined as (i) Qo(ε)=ε; (ii) for all σ∈T∗ and t∈T, Qo(σt)=Qo(σ)t if t∈To, and Qo(σt)=Qo(σ) otherwise, where ε is the empty string.(ii)
Qu:T∗→Tu∗, which is defined as (i) Qu(ε)=ε; (ii) for all σ∈T∗ and t∈T, Qu(σt)=Qu(σ)t if t∈Tu, and Qu(σt)=Qu(σ) otherwise.In plain words, given a transition sequenceσ∈T∗, the operator Qo computes the projection of σ on observable transition set To and the operator Qu computes the projection of σ on unobservable transition set Tu. Note that Qo-1 denotes the inverse of projection Qo.Given a sequenceσ∈L(PN,M0), w=Qo(σ) is the observed sequence. The set of all observed sequences can be represented by (5)ΩPN,M0=w∈To∗∣σ∈LPN,M0,w=Qoσ.A Petri net is said to beacyclic if it has no directed circuit. Equation (2) shows that there exists a nonnegative integer x→ such that M=M0+C·x→ if M is reachable from M0, which is a necessary but not sufficient condition. However, for an acyclic Petri net, it is necessary and sufficient, as shown by the following theorem.Theorem 3 (see [22]).
In an acyclic Petri net, a markingM≥0 is reachable from M0 if and only if (iff) there exists a nonnegative integer solution x→ satisfying M=M0+C·x→.A netPN=(P,T,Pre,Post) ispure if it has no self-loop; namely, ∀t∈T, Pre(p,t)×Post(p,t)=0 for each p∈P. Note that the structure of a pure net can be represented by its incidence matrix. Moreover, it is trivially verified that an acyclic net is pure.Definition 4.
Consider net systemPN,M0 with T=To∪Tu. Let w∈Ω(PN,M0) be an observed sequence. The sequences of unobservable transitions which enable the occurrence of w are denoted by (6)Σw=y∈Tu∗∣y=QuQo-1wand the nu-dimensional firing vectors of sequences of unobservable transitions associated with w are denoted by (7)Yw=y→∈Nnu∣y∈Σw.Example 5.
Figure1 shows a net system with To=t1,t2, Tu=ε1,ε2,ε3, and M0=1,0,0,0T. If an observed transition sequence is w=t1t2, by Definition 4, we observe Qo-1w=t1ε1ε2t2,t1ε3t2. Thus Σ(w)=ε1ε2,ε3 and Y(w)=1,1,0T,0,0,1T.Figure 1
A Petri net system.


## 2.1. Basics of Petri Nets

A Petri net is a four-tuplePN=(P,T,Pre,Post), where P is the set of places, T is the set of transitions, Pre:P×T→N, and Post:P×T→N are the pre- and postincidence matrices, respectively, which specify the structure of the Petri net. For p∈P, t∈T, and x∈N, Pre(p,t)=x if there exists an arc with weight x from p to t, 0 otherwise; Post(p,t)=x if an arc with weight x goes from t to p, 0 otherwise. Here N is the set of nonnegative integers. We denote by m=|P| the number of places and n=T that of transitions. The incidence matrix of a net is denoted as C=Post-Pre. For t∈T, itspreset is defined as t•=p∈P∣Pre(p,t)>0, and itspostset is defined as t•=p∈P∣Post(p,t)>0. A transition t is said to be asource transition if it satisfies t•=∅. A marking of a Petri net is a vector M:P→N, and M(p) indicates the number of tokens in place p. A net system 〈PN,M0〉 is a Petri net with an initial marking M0.A transitiontj∈T isenabled at marking M if ∀p∈t•j,M(p)≥Pre(p,tj), which is denoted by Mtj. An enabled transition tj at M can fire yielding a new marking M′ such that M′=M+Post(·,tj)-Pre(·,tj), which is denoted as MtjM′. If MtjM′ holds, by the definition of incidence matrix C, we have M′=M+C(·,tj), which can be rewritten as M′=M+C·t→j, where t→j is the n-dimensional canonical basic vector and its j-th entry is one.Given a transition sequenceσ and a marking M, M[σ〉 denotes that σ is enabled at marking M and MσM′ denotes that a new marking M′ isreachable from M after firing σ. All the markings reachable from M0 comprise thereachability set of a Petri net and it is denoted as R(PN,M0). The set of sequences enabled at the initial marking M0 is denoted as(1)LPN,M0=σ∈T∗∣M0σ,which is called thelanguage of a Petri net.We define ann-dimensional column vector σ→:T→N (calledfiring vector) for the corresponding transition sequence σ such that σ→(t)=k if transition t occurs k times in σ. For an enabled transition sequence σ at M0 such that M0σM, we have the following state equation:(2)M=M0+C·σ→,which is called thestate equation of a Petri net system.


## 2.2. Labeled Petri Net

Given a Petri netPN=(P,T,Pre,Post) and the set of events E, a labeling function λ:T→E∪ε assigns to each transition t∈T either a symbol from the event set E or an empty string ε. A transition with label ε is called anunobservable transition and the set of unobservable transitions is denoted as Tu=t∈T∣λ(t)=ε with nu=Tu being the cardinality of set Tu. All other transitions whose labels are not ε comprise the set ofobservable transitionsTo=t∈T∣λ(t)≠ε and no=To. Thus the set T is divided into two disjoint subsets To and Tu with T=To∪Tu. We assume that each label e∈E can only be assigned to one transition, i.e., the set E is isomorphic to the set of observable transitions To, and thus without loss of generality we assume E=To. A place p∈P is said to beobservable if it is equipped with a sensor that allows observation of the number of its tokens.For eachσo∈To∗, we define an no-dimensional vector σ→o:To→N and σ→o(t)=k if t∈To occurs k times in σo. Analogously, for each σu∈Tu∗, an nu-dimensional vector σ→u:Tu→N is defined and σ→u(t)=k if t∈Tu occurs k times in σu.


## 2.3. Linear Reformulation

An optimization problem with an absolute value is nonlinear. Absolute value functions are not continuously differentiable, and it is difficult to perform standard optimization procedure on them. However, we can convert an absolute value function into several linear constraints such that the optimization can be solved using the standard linear programming technique. We here only consider this situation: there is an absolute value in the objective function. Let us consider the following optimization problem:(3)mina→T·absx→+b→T·y→s.t.Awhere x→ and y→ are variables in Rn and Rm, respectively, a→ and b→ are constant vectors in R≥0n and Rm, respectively, abs(x→) denotes the absolute value of vector x→, and A denotes the linear constraints in this programming problem. Note that a→ is a column vector consisting of nonnegative real numbers.Programming problem (3) can be rewritten in the form of a linear objective function as(4)mina→T·z→+b→T·y→s.t.A-x→≤z→x→≤z→z→≥0→where z→ is a variable in Rn; i.e., we add a variable z→≥0→ and two additional constraints -x→≤z→ and x→≤z→.In fact, for the real numbersx1 and z1 that are the first entries of vectors x→ and z→, respectively, there are three different cases.(1)
x1>0. Constraint -x1≤z1 is always fulfilled. Because of the constraint x1≤z1, z1 is necessarily at least as large as x1. On the other hand, z1 is in the objective function such that it trends to be as small as possible. Thus z1 will be equal to x1, i.e., z1=abs(x1).(2)
x1=0. In this case, constraints -x1≤z1 and x1≤z1 are always verified because of z1≥0. Moreover z1 is in the objective function, and thus it trends to be zero, i.e., z1=abs(x1).(3)
x1<0. Being analogous to case (1), z1=abs(x1) is trivially verified.Definition 1.
Given a Petri netPN=(P,T,Pre,Post) with T=To∪Tu, PN can be partitioned into two components denoted by PN=PNo⊗PNu. Here PNo=(P,To,Preo,Posto) is theobservable subnet, where P is the set of places, To is the set of observable transitions, and Preo and Posto are the restrictions of Pre and Post to To, respectively; PNu=(P,Tu,Preu,Postu) is theunobservable subnet, where Tu is the set of unobservable transitions and Preu and Postu are the restrictions of Pre and Post to Tu, respectively.Definition 2 (see [5]).
Considering the netPN=(P,T,Pre,Post) with T=To∪Tu, we define the following two projection operations: (i)
Qo:T∗→To∗, which is defined as (i) Qo(ε)=ε; (ii) for all σ∈T∗ and t∈T, Qo(σt)=Qo(σ)t if t∈To, and Qo(σt)=Qo(σ) otherwise, where ε is the empty string.(ii)
Qu:T∗→Tu∗, which is defined as (i) Qu(ε)=ε; (ii) for all σ∈T∗ and t∈T, Qu(σt)=Qu(σ)t if t∈Tu, and Qu(σt)=Qu(σ) otherwise.In plain words, given a transition sequenceσ∈T∗, the operator Qo computes the projection of σ on observable transition set To and the operator Qu computes the projection of σ on unobservable transition set Tu. Note that Qo-1 denotes the inverse of projection Qo.Given a sequenceσ∈L(PN,M0), w=Qo(σ) is the observed sequence. The set of all observed sequences can be represented by (5)ΩPN,M0=w∈To∗∣σ∈LPN,M0,w=Qoσ.A Petri net is said to beacyclic if it has no directed circuit. Equation (2) shows that there exists a nonnegative integer x→ such that M=M0+C·x→ if M is reachable from M0, which is a necessary but not sufficient condition. However, for an acyclic Petri net, it is necessary and sufficient, as shown by the following theorem.Theorem 3 (see [22]).
In an acyclic Petri net, a markingM≥0 is reachable from M0 if and only if (iff) there exists a nonnegative integer solution x→ satisfying M=M0+C·x→.A netPN=(P,T,Pre,Post) ispure if it has no self-loop; namely, ∀t∈T, Pre(p,t)×Post(p,t)=0 for each p∈P. Note that the structure of a pure net can be represented by its incidence matrix. Moreover, it is trivially verified that an acyclic net is pure.Definition 4.
Consider net systemPN,M0 with T=To∪Tu. Let w∈Ω(PN,M0) be an observed sequence. The sequences of unobservable transitions which enable the occurrence of w are denoted by (6)Σw=y∈Tu∗∣y=QuQo-1wand the nu-dimensional firing vectors of sequences of unobservable transitions associated with w are denoted by (7)Yw=y→∈Nnu∣y∈Σw.Example 5.
Figure1 shows a net system with To=t1,t2, Tu=ε1,ε2,ε3, and M0=1,0,0,0T. If an observed transition sequence is w=t1t2, by Definition 4, we observe Qo-1w=t1ε1ε2t2,t1ε3t2. Thus Σ(w)=ε1ε2,ε3 and Y(w)=1,1,0T,0,0,1T.Figure 1
A Petri net system.


## 3. Model Identification without Observable Places

### 3.1. Problem Statement

Assume that the observable subnetPNo and the initial marking M0 are known. We monitor the system evolution and record the occurred event. Upon the occurrence of an event, a transition t∈To is observed and it is appended to the tail of the observed sequence. If the observed transition sequence is v, then two different situations are taken into account.(i)M0v holds, i.e., v∈L(PNo,M0). In such a case the observable subnet is sufficient to describe the observed transition sequence.(ii)M0v does not hold. We infer that one or more unobservable transitions not included in PNo occur.We can infer a netPN=(P,T,Pre,Post) with PN=PNo⊗PNu from the observed transition sequence v such that it can describe the observable and unobservable system behavior. To correctly identify the unobservable subnet, we make the following assumptions.(A1)
The unobservable behavior of a system can be characterized by an acyclic subnet, denoted byPNu=(P,Tu,Preu,Postu).Given an observable subnetPNo that models the observable behavior of a system, Assumption (A1) means that we can always find a solution of an acyclic unobservable subnet PNu such that the combined net PN=PNo⊗PNu describes the whole system. On the other hand, Assumption (A1) provides a necessary and sufficient condition for the reachability of the unobservable subnet PNu.To combine the known observable subnetPNo and the identified unobservable subnet PNu, the preincidence matrix of the whole net PN is computed by Pre=[PreoPreu], and its postincidence matrix is represented by Post=[PostoPostu]. Correspondingly, we have C=[CoCu].Problem 6.
Assume that an observable subsetPNo=(P,To,Preo,Posto) and the initial marking M0 are given and that the observed transition sequence is w∈To∗. Under Assumption (A1), the problem consists in finding a Petri net PN=(P,T,Pre,Post) such that PN=PNo⊗PNu and w∈Ω(PN,M0).The structure of a pure net can be represented by its incidence matrix. Thus, by Assumption (A1), we only need to compute the incidence matrixCu of the unobservable subnet PNu to determine its structure. On the other hand, the observable subset PNo is known, and thus we can obtain the net PN.


### 3.2. Main Results

Assume that the observable subnetPNo and M0 are given and that a sequence v has been observed. A Petri net PN is identified such that PN=PNo⊗PNu and v∈Ω(PN,M0). Now a new transition t∈To is observed. We can decide whether vt∈Ω(PN,M0) holds thanks to the following theorem, where vt denotes the observed sequence after transition t is recorded.Theorem 7.
Assume that Assumption (A1) is satisfied in a Petri netPN with PN=PNo⊗PNu. Let v∈Ω(PN,M0) be the current observed sequence and y→∈Y(v) be a corresponding firing vector of unobservable transitions. A new transition t is observed. If (8) admits a solution, then vt∈Ω(PN,M0).(8)M0+Co·v→+Cu·y→+Cu·σ→u≥Preo·,tσ→u∈NnuProof.
LetM′=M0+Co·v→+Cu·y→ be a marking of PN after sequence v fires. Clearly, M′∈R(PN,M0) holds. If (8) admits a solution, then there exists an nonnegative integer vector σ→u such that M′+Cu·σ→u≥Preo(·,t)≥0→. Let M′′=M′+Cu·σ→u. By Assumption (A1) and Theorem 3, there exists an unobservable transition sequence σu such that M′′∈R(PN,M0) and M′σuM′′. Since M′′≥Preo(·,t), M′σuM′′t holds. Thus the transition t can be observed after v by firing σu, i.e., vt∈Ω(PN,M0).The solution to (8) is not unique, and we can choose a performance index to select a solution among the set of admissible ones such that it is most suitable for the current situation. In particular, we can consider the performance index 1→nuT·σ→u which minimizes the sum of the firing times of unobservable transitions. We define the following ILPP:(9)ILPP1:min1→nuT·σ→us.t.Eq.8where 1→nuT is a row vector of dimension nu with each element being 1.Example 8.
Consider the net system in Figure2, where P=p1,p2,p3, To=t1,t2,t3, Tu=ε1, and the dashed lines represent the arcs connected with unobservable transitions. Assume that the observed sequence is v=t1 and that the corresponding firing vector of unobservable transitions is y→=1T. If the transition t2 is now observed, we find a solution σ→u=1T by solving ILPP 1. According to Theorem 7, we have v=t1t2∈Ω(PN,M0). In fact, there exists a firing sequence σ=ε1t1ε1t2 such that M0σ.Figure 2
A Petri net withTu=ε1.If (8) has no feasible solution, we can only add a new unobservable transition to Petri net PN to obtain a new Petri net PN′ such that vt∈Ω(PN′,M0). Assume that εz is the considered unobservable transition. Let PN′=PNo⊗PNu′; i.e., Petri nets PN and PN′ have the same observable subnet PNo; however the unobservable subnet PNu′ is obtained by adding the unobservable transition εz to PNu. By Assumption (A1), the structure of PNu can be determined by its incidence matrix Cu. Assume that ε→z is the column in the incidence matrix associated with εz and then the incidence matrix of PNu′ is Cu′=[Cuε→z]; i.e., PNu′ retains the structure of PNu but includes an additional transition εz. The following proposition provides a method to compute the unobservable transition.Proposition 9.
Given a net system〈PN,M0〉 with PN=PNo⊗PNu, let v∈Ω(PN,M0) be the current observed sequence and y→∈Y(v) be a corresponding firing vector of unobservable transitions. Assume that a new transition t is observed. If there exists a vector ε→z satisfying (10), then vt∈Ω(PN′,M0), where PN′ is a Petri net obtained by adding an unobservable transition εz with the corresponding incidence matrix column being ε→z to PN.(10)M0+Co·v→+Cu·y→+ε→z≥Preo·,tε→z∈Zmε→z≠0→where Z is the set of integers.Proof.
LetM′=M0+Co·v→+Cu·y→ be a marking of PN after firing sequence v. Obviously, M′∈R(PN′,M0) holds. If ε→z is a solution of (10), then M′+ε→z≥Preo(·,t) holds. Let M′′=M′+ε→z. Since Cu′=[Cuε→z], i.e., ε→z is the last column of incidence matrix Cu′, by Theorem 3, M′+Cu′(·,εz)=M′′≥Preo(·,t) holds, where εz denotes the new unobservable transition whose incidence matrix column is ε→z. Thus M′εzM′′t holds, i.e., vt∈Ω(PN′,M0).Let us consider (10) again. When the cardinality of set Tu is zero, i.e., Tu=0, the incidence matrix Cu is a 0×0 matrix and we can set Cu·y→=0→. On the other hand, there may be more than one solution satisfying the linear constraint set represented by (10), and we can define a performance index to select a solution among those solutions. In particular, if f=1→mT·abs(ε→z) is considered as a performance index which minimizes the sum of weights of the arcs connected with the unobservable transition εz, the following integer programming problem is formulated:(11)min1→mT·absε→zs.t.Eq.10S∈0,1m1→mT·S≤m-1-K·S+ε→z≤-1→mawhere K is a constant that is large enough.If the performance indexf=1→mT·abs(ε→z) is chosen, the solution of (11) is always ε→z≥0; namely, we can always obtain a source transition. In practical applications, because of the limited resources, a source transition that models unobservable behavior of a system is not common. In order to forbid the solution containing source transitions, we impose the additional constraints (a) on the unobservable transition to guarantee thatat least one component of the solution ε→z is a negative integer; i.e., the solution cannot be a source transition. Here, thatat least a component of a vector is less than or equal to zero can be characterized by the logical OR operator which can be easily converted into some linear constraints [23], such as constraints (a) in (11).On the other hand, the optimization problem represented by (11) is nonlinear because of the absolute value in the objective function. We have shown in Section 2.3 that the absolute value in a programming problem can be removed by adding additional variables and constraints. Thus (11) can be rewritten as follows:(12)ILPP2min1→mT·r→s.t.Eq.10S∈0,1m1→mT·S≤m-1-K·S+ε→z≤-1→ma-ε→z≤r→ε→z≤r→r→∈Nmbwhere r→ and (b) are, respectively, the additional variables and constraints associated with abs(ε→z) in (11).Example 10.
Consider the net systemPN,M0 in Figure 3(a), where To=t1,t2,t3 and Tu=ε1. Assume that the observed sequence is v=t1t2 satisfying v∈Ω(PN,M0) and that the corresponding firing vector is y→=2T. Suppose that t3 is now observed, but ILPP 1 has no feasible solution; i.e., we should add a new unobservable transition to PN such that t1t2t3∈Ω(PN,M0). The solution ε→2=1,1,-1T is found by solving ILPP 2. Let Cu=[Cu,ε→2] and update the structure of PNu by adding a new unobservable transition ε2. Figure 3(b) shows the obtained Petri net.Figure 3
(a) A net satisfyingt1t2∈Ω(PN,M0), (b) a net after ε2 is added, and (c) a net with a simpler structure than (b).
(a) (b) (c)Note that the net system in Figure3(c) is also a solution of Example 10. Moreover, it has a smaller sum of weights of the arcs connected with ε2. In fact, we can make use of the previously obtained unobservable transitions when we compute the new unobservable transition to obtain a simpler solution. The following proposition provides a technique to make use of the previously identified unobservable transitions.Proposition 11.
Assume that the net systemPN,M0 is given and v∈Ω(PN,M0) is the current observed sequence with y→∈Y(v). A new transition t is observed. If there exists a vector ε→z satisfying; (13a), (13b), (13c), and (13d), then vt∈Ω(PN′,M0), where PN′ is a Petri net obtained by adding εz to PN.(13a)M0+Co·v→+Cu·y→+σ→u+ε→z≥Preo·,t(13b)σ→u∈Nnu(13c)ε→z∈Zm(13d)ε→z≠0→Proof.
LetM′=M0+Co·v→+Cu·y→ be the marking after firing sequence v. M′∈R(PN′,M0) holds. The constraint (13a) can be rewritten as(14)M′+Cu·σ→u+ε→z≥Preo·,t.Since Cu′=[Cuε→z], (14) is rewritten as(15)M′+Cu′·σ→u1≥Preo·,t.Let M′′=M′+Cu′·σ→u1T. By Theorem 3, there exists an unobservable transition sequence σu′ such that M′σu′M′′. Since M′′≥Preo(·,t), M′σu′M′′t holds, i.e., vt∈Ω(PN′,M0).As shown in (10), the solution of (13a), (13b), (13c), and (13d) is neither unique. We still consider the performance index f=1→mT·abs(ε→z) and convert the absolute value in objective function into linear constraints. The final integer linear programming problem is shown as follows:(16)ILPP3:min1→mT·r→s.t.Eq.13a,13b,13c,and13dS∈0,1m1→mT·S≤m-1-K·S+ε→z≤-1→ma-ε→z≤r→ε→z≤r→r→∈NmbExample 12.
Consider again the net system in Figure3(a) and assume that v=t1t2 is the observed sequence and y→=2T. Now the transition t3 is observed and ILPP 1 has no feasible solution. We solve ILPP 3 to introduce a new unobservable transition. A solution ε→2=1,0,-1T is found. Let Cu=[Cuε→2]. The resulting net system is shown in Figure 3(c) such that t1t2t3∈Ω(PN,M0).


### 3.3. Online Identification Algorithm

There may be different approaches that can provide a solution to Problem6; however we propose an online identification algorithm that recursively determines the structure of the unobservable subnet. Upon each observed transition t, we record t and decide whether a new unobservable transition should be introduced by solving ILPP 1. If it is the case, we obtain the unobservable transition by solving ILPP 3 and update the structure of the unobservable subnet. The identification procedure is shown by Algorithm 1, which monitors the system evolution and waits until a transition is observed.Algorithm 1:Identification of an unobservable subnet.
Input: A net system 〈PNo,M0〉 Output: A Petri net PN with PN=PNo⊗PNu (1) Tu=∅, nu=0, Cu=, y→=, v=′′; (2) wait until transition t is observed; (3) ifnu==0then (4)ifM0+Co⋅v→≥Preo(⋅,t)then (5)v=vt; goto 2; (6)else (7) goto 13; (8)end if (9)else (10)ifILPP 1 admits a solution σ→uthen (11)v=vt; y→=y→+σ→u; goto 2; (12)else (13)ifILPP 3 admits a solution ε→nu and σ→uthen (14)nu=nu+1; Cu=[Cu,ε→nu]; Tu=Tu∪εnu; (15)y→=y→+σ→u; y→=y→1; (16)v=vt; (17)goto 2; (18)else (19)error:cannot find a solution satisfying ILPP 3 (20)return (21)end if (22)end if (23)end ifThe inputs of Algorithm1 are the observable subnet PNo and the initial marking M0, i.e., Preo, Posto, and M0, and its output is the unobservable subnet PNu such that we can obtain the whole net PN=PNo⊗PNu.In line (1), the algorithm initializes the variables. Initially, the unobservable subnetPNu is null, i.e., Tu=∅, Cu is a 0×0 matrix, and the vector y→ is also null. Note that the vector y→ is maintained and updated by Algorithm 1 when a transition is observed. In addition, nu denotes the number of unobservable transitions, and it is the subscript when we name the newly identified transition εnu.In line (3), ifnu equals zero, i.e., no unobservable transition is identified, it is not necessary to solve ILPP 1. Instead, the condition of line (4) is checked.In line (10), ILPP 1 has a feasible solution; then we only update the firing vectory→ and go back to line (2). In lines (14) and (15), a new unobservable transition is identified and we will update the corresponding variables. First, we add the solution ε→nu to Cu as the last column, and the corresponding unobservable transition is called εnu. Note that nu increases by one when a new unobservable transition is identified such that the unobservable transitions are named ε1, ε2, ε3,... We also obtain the value of variable σ→u that represents the firing vector of the previously identified unobservable transitions to enable the observed transition t. Hence we add y→ by σ→u and add the dimension of y→ by one, which means that the new identified unobservable transition εnu fires once.In line (19), it happens that ILPP 3 has no feasible solution, which probably stems from the necessity of a source transition or the inaccurate sensor reading.Example 13.
Consider the observable subnet in Figure4(a), where P=p1,p2,…,p7, To=t1,t2,…,t7, and M0=3,0,1,0,0,0,0T. Assume that the observed sequence is v=t1t2t2t3t6t3t6t2. Upon each observed transition, Algorithm 1 executes the identification procedure. We analyse the transitions in v in sequence.
Initially, the observed sequencev is an empty string, Tu=∅, both Cu and y→ are null, and nu=0.
Occurrence of t 1: the relation M0≥Preo(·,t1) holds, and thus we do not have to solve ILPP 3 to find an unobservable transition. The algorithm sets v=t1.
Occurrence of t 2: M0+(Posto-Preo)·v→=2,2,1,0,0,0,0T≥Preo(·,t2)=0,1,1,0,0,0,0T holds. Thus the algorithm sets v=t1t2.Occurrence of the secondt2: since M0+(Posto-Preo)·v→≱Preo(·,t2), ILPP 3 is solved and the solution ε→1=0,0,1,-1,0,0,0T is found. Then the algorithm updates Cu, nu, and y→ with nu=1, y→=1T and adds ε1 to Tu. The Petri net PN=PNo⊗PNu is shown in Figure 4(b). Now v=t1t2t2.
Occurrence of t 3: since nu>0, we solve ILPP 1 and obtain the solution σ→u=0→, implying that t3 is enabled at the current marking, and y→=y→+0→ remains unchanged.
Occurrence of t 6: ILPP 1 has no feasible solution, i.e., a new unobservable transition should be introduced. Solving ILPP 3 and obtaining the solution ε→2=0,0,0,0,-1,1,0T, we add ε2 to Tu and update Cu. Now the net PN is shown in Figure 4(c) with y→=[1,1]T and v=t1t2t2t3t6.
Occurrence of the second t 3: ILPP 1 has a solution σ→u=0→. Thus we just need to increase the observed sequence, i.e., v=t1t2t2t3t6t3.
Occurrence of the second t 6: A solution to ILPP 1 is σ→u=0,1T, implying that t6 is enabled after firing unobservable transition ε2. The vector y→ is updated with y→=y→+σ→u=1,2T and let v=t1t2t2t3t6t3t6.
Occurrence of the third t 2: ILPP 1 has no feasible solution and a solution ε→3=0,1,0,0,0,0,-1T is found by solving ILPP 3. We add ε3 to set Tu and update the structure of unobservable subnet PNu. The net PN is shown in Figure 4(d). Furthermore, we have y→=1,2,1T and v=t1t2t2t3t6t3t6t2.Figure 4
(a) The observable subnetPNo, (b) the net identified after sequence t1t2t2, (c) the net identified after sequence t1t2t2t3t6, and (d) the net identified after sequence t1t2t2t3t6t3t6t2 by applying Algorithm 1.
(a) (b) (c) (d)As shown in Example13, an unobservable transition is introduced in some cases when a transition t is observed. An unobservable subnet PNu is recursively identified by Algorithm 1 and the Petri net PN=PNo⊗PNu is finally provided. The following theorem proves that the output of Algorithm 1 is a solution to Problem 6.Theorem 14.
Given the observable subnetPNo and the initial marking M0, under Assumption (A1), the identified Petri net PN=PNo⊗PNu by Algorithm 1 is a solution to Problem 6.Proof.
The proof is made by induction.
Basic Step. In this case, the observed sequence v is an empty string and incidence matrix Cu is null. If transition t is now observed, then we check the relation M0+Co·v→≥Preo(·,t), i.e., the relation M0≥Preo(·,t). If it holds, let w=vt=t, and w∈Ω(PN,M0) trivially holds. Otherwise, the solution ε→z is obtained by solving ILPP 3 and PNu is updated by adding an unobservable transition εz. Let w=t and PN=PNo⊗PNu. By Proposition 11, M0εzM′t is trivially verified, namely, w∈Ω(PN,M0).
Inductive Step. Assume that the observed sequence is v and the corresponding firing vector of unobservable transitions is y→∈Y(v). If t is now observed, two different situations are considered. (1)
nu equals 0, i.e., no unobservable transition is introduced during the period of observation v. If M0+Co·v→≥Preo(·,t) is true, then t is enabled at the current marking, i.e., w=vt∈Ω(PN,M0). Otherwise, a solution ε→z is found by solving ILPP 3 and the structure of PN is updated by adding a new unobservable transition εz whose incidence matrix column is ε→z. Let w=vt. By Proposition 11, M0vM′εzM′′[t〉 holds, where M′,M′′∈R(PN,M0), namely, w∈Ω(PN,M0).(2)
nu is greater than 0. In this situation, if ILPP 1 admits a solution, we update y→ and the observed sequence with w=vt. By Theorem 7, w∈Ω(PN,M0) holds. On the other hand, if ILPP 1 has no feasible solution, the solution including ε→z and σ→u is obtained by solving ILPP 3. We update the related variables with y→=y→+σ→u and Cu=[Cuε→z] and add a new unobservable transition εz to Petri net PN. Let w=vt, and then w∈Ω(PN,M0) holds by Proposition 11.
Hence, we conclude that the Petri netPN identified by Algorithm 1 is a solution to Problem 6.


### 3.4. Complexity of the Identification Algorithm

Obviously, the primary determinants of the computational difficulty of this algorithm are two integer linear programming problems ILPP 1 and ILPP 3. It is well known that an integer linear programming problem is NP-hard, but it can be solved easily if the number of variables is small. In Algorithm1, if necessary, ILPP 1 and ILPP 3 are solved serially. In addition, the number of variables in ILPP 3 is greater than that in ILPP 1. Thus we analyse the complexity of ILPP 3 only.We observe thatσ→u, ε→z, and r→ are the integer variables in ILPP 3 and S is a binary variable. Then the number of integer variables is u=nu+3m, where nu denotes the number of unobservable transitions and 3m denotes the sum of the dimensions of ε→z, r→, and S.In other words, the number of integer variables in ILPP 3 is linear (the coefficient is1) with respect to that of unobservable transitions. Thus ILPP 3 is a simple integer programming problem that can be solved efficiently. For example, the unobservable subnet with three unobservable transitions in Example 13 is identified using LPSOLVE (a mixed integer linear programming solver [24]) in 0.0541 seconds on a notebook computer with 2 GHz processor and 8 GB RAM. In addition, we test the presented algorithm on an observable subnet with 43 places, 40 transitions, 140 arcs. In this setting, 15 unobservable transitions are found by solving 25 integer programming problems in 0.3698 seconds on the same computer using LPSOLVE solver.


## 3.1. Problem Statement

Assume that the observable subnetPNo and the initial marking M0 are known. We monitor the system evolution and record the occurred event. Upon the occurrence of an event, a transition t∈To is observed and it is appended to the tail of the observed sequence. If the observed transition sequence is v, then two different situations are taken into account.(i)M0v holds, i.e., v∈L(PNo,M0). In such a case the observable subnet is sufficient to describe the observed transition sequence.(ii)M0v does not hold. We infer that one or more unobservable transitions not included in PNo occur.We can infer a netPN=(P,T,Pre,Post) with PN=PNo⊗PNu from the observed transition sequence v such that it can describe the observable and unobservable system behavior. To correctly identify the unobservable subnet, we make the following assumptions.(A1)
The unobservable behavior of a system can be characterized by an acyclic subnet, denoted byPNu=(P,Tu,Preu,Postu).Given an observable subnetPNo that models the observable behavior of a system, Assumption (A1) means that we can always find a solution of an acyclic unobservable subnet PNu such that the combined net PN=PNo⊗PNu describes the whole system. On the other hand, Assumption (A1) provides a necessary and sufficient condition for the reachability of the unobservable subnet PNu.To combine the known observable subnetPNo and the identified unobservable subnet PNu, the preincidence matrix of the whole net PN is computed by Pre=[PreoPreu], and its postincidence matrix is represented by Post=[PostoPostu]. Correspondingly, we have C=[CoCu].Problem 6.
Assume that an observable subsetPNo=(P,To,Preo,Posto) and the initial marking M0 are given and that the observed transition sequence is w∈To∗. Under Assumption (A1), the problem consists in finding a Petri net PN=(P,T,Pre,Post) such that PN=PNo⊗PNu and w∈Ω(PN,M0).The structure of a pure net can be represented by its incidence matrix. Thus, by Assumption (A1), we only need to compute the incidence matrixCu of the unobservable subnet PNu to determine its structure. On the other hand, the observable subset PNo is known, and thus we can obtain the net PN.


## 3.2. Main Results

Assume that the observable subnetPNo and M0 are given and that a sequence v has been observed. A Petri net PN is identified such that PN=PNo⊗PNu and v∈Ω(PN,M0). Now a new transition t∈To is observed. We can decide whether vt∈Ω(PN,M0) holds thanks to the following theorem, where vt denotes the observed sequence after transition t is recorded.Theorem 7.
Assume that Assumption (A1) is satisfied in a Petri netPN with PN=PNo⊗PNu. Let v∈Ω(PN,M0) be the current observed sequence and y→∈Y(v) be a corresponding firing vector of unobservable transitions. A new transition t is observed. If (8) admits a solution, then vt∈Ω(PN,M0).(8)M0+Co·v→+Cu·y→+Cu·σ→u≥Preo·,tσ→u∈NnuProof.
LetM′=M0+Co·v→+Cu·y→ be a marking of PN after sequence v fires. Clearly, M′∈R(PN,M0) holds. If (8) admits a solution, then there exists an nonnegative integer vector σ→u such that M′+Cu·σ→u≥Preo(·,t)≥0→. Let M′′=M′+Cu·σ→u. By Assumption (A1) and Theorem 3, there exists an unobservable transition sequence σu such that M′′∈R(PN,M0) and M′σuM′′. Since M′′≥Preo(·,t), M′σuM′′t holds. Thus the transition t can be observed after v by firing σu, i.e., vt∈Ω(PN,M0).The solution to (8) is not unique, and we can choose a performance index to select a solution among the set of admissible ones such that it is most suitable for the current situation. In particular, we can consider the performance index 1→nuT·σ→u which minimizes the sum of the firing times of unobservable transitions. We define the following ILPP:(9)ILPP1:min1→nuT·σ→us.t.Eq.8where 1→nuT is a row vector of dimension nu with each element being 1.Example 8.
Consider the net system in Figure2, where P=p1,p2,p3, To=t1,t2,t3, Tu=ε1, and the dashed lines represent the arcs connected with unobservable transitions. Assume that the observed sequence is v=t1 and that the corresponding firing vector of unobservable transitions is y→=1T. If the transition t2 is now observed, we find a solution σ→u=1T by solving ILPP 1. According to Theorem 7, we have v=t1t2∈Ω(PN,M0). In fact, there exists a firing sequence σ=ε1t1ε1t2 such that M0σ.Figure 2
A Petri net withTu=ε1.If (8) has no feasible solution, we can only add a new unobservable transition to Petri net PN to obtain a new Petri net PN′ such that vt∈Ω(PN′,M0). Assume that εz is the considered unobservable transition. Let PN′=PNo⊗PNu′; i.e., Petri nets PN and PN′ have the same observable subnet PNo; however the unobservable subnet PNu′ is obtained by adding the unobservable transition εz to PNu. By Assumption (A1), the structure of PNu can be determined by its incidence matrix Cu. Assume that ε→z is the column in the incidence matrix associated with εz and then the incidence matrix of PNu′ is Cu′=[Cuε→z]; i.e., PNu′ retains the structure of PNu but includes an additional transition εz. The following proposition provides a method to compute the unobservable transition.Proposition 9.
Given a net system〈PN,M0〉 with PN=PNo⊗PNu, let v∈Ω(PN,M0) be the current observed sequence and y→∈Y(v) be a corresponding firing vector of unobservable transitions. Assume that a new transition t is observed. If there exists a vector ε→z satisfying (10), then vt∈Ω(PN′,M0), where PN′ is a Petri net obtained by adding an unobservable transition εz with the corresponding incidence matrix column being ε→z to PN.(10)M0+Co·v→+Cu·y→+ε→z≥Preo·,tε→z∈Zmε→z≠0→where Z is the set of integers.Proof.
LetM′=M0+Co·v→+Cu·y→ be a marking of PN after firing sequence v. Obviously, M′∈R(PN′,M0) holds. If ε→z is a solution of (10), then M′+ε→z≥Preo(·,t) holds. Let M′′=M′+ε→z. Since Cu′=[Cuε→z], i.e., ε→z is the last column of incidence matrix Cu′, by Theorem 3, M′+Cu′(·,εz)=M′′≥Preo(·,t) holds, where εz denotes the new unobservable transition whose incidence matrix column is ε→z. Thus M′εzM′′t holds, i.e., vt∈Ω(PN′,M0).Let us consider (10) again. When the cardinality of set Tu is zero, i.e., Tu=0, the incidence matrix Cu is a 0×0 matrix and we can set Cu·y→=0→. On the other hand, there may be more than one solution satisfying the linear constraint set represented by (10), and we can define a performance index to select a solution among those solutions. In particular, if f=1→mT·abs(ε→z) is considered as a performance index which minimizes the sum of weights of the arcs connected with the unobservable transition εz, the following integer programming problem is formulated:(11)min1→mT·absε→zs.t.Eq.10S∈0,1m1→mT·S≤m-1-K·S+ε→z≤-1→mawhere K is a constant that is large enough.If the performance indexf=1→mT·abs(ε→z) is chosen, the solution of (11) is always ε→z≥0; namely, we can always obtain a source transition. In practical applications, because of the limited resources, a source transition that models unobservable behavior of a system is not common. In order to forbid the solution containing source transitions, we impose the additional constraints (a) on the unobservable transition to guarantee thatat least one component of the solution ε→z is a negative integer; i.e., the solution cannot be a source transition. Here, thatat least a component of a vector is less than or equal to zero can be characterized by the logical OR operator which can be easily converted into some linear constraints [23], such as constraints (a) in (11).On the other hand, the optimization problem represented by (11) is nonlinear because of the absolute value in the objective function. We have shown in Section 2.3 that the absolute value in a programming problem can be removed by adding additional variables and constraints. Thus (11) can be rewritten as follows:(12)ILPP2min1→mT·r→s.t.Eq.10S∈0,1m1→mT·S≤m-1-K·S+ε→z≤-1→ma-ε→z≤r→ε→z≤r→r→∈Nmbwhere r→ and (b) are, respectively, the additional variables and constraints associated with abs(ε→z) in (11).Example 10.
Consider the net systemPN,M0 in Figure 3(a), where To=t1,t2,t3 and Tu=ε1. Assume that the observed sequence is v=t1t2 satisfying v∈Ω(PN,M0) and that the corresponding firing vector is y→=2T. Suppose that t3 is now observed, but ILPP 1 has no feasible solution; i.e., we should add a new unobservable transition to PN such that t1t2t3∈Ω(PN,M0). The solution ε→2=1,1,-1T is found by solving ILPP 2. Let Cu=[Cu,ε→2] and update the structure of PNu by adding a new unobservable transition ε2. Figure 3(b) shows the obtained Petri net.Figure 3
(a) A net satisfyingt1t2∈Ω(PN,M0), (b) a net after ε2 is added, and (c) a net with a simpler structure than (b).
(a) (b) (c)Note that the net system in Figure3(c) is also a solution of Example 10. Moreover, it has a smaller sum of weights of the arcs connected with ε2. In fact, we can make use of the previously obtained unobservable transitions when we compute the new unobservable transition to obtain a simpler solution. The following proposition provides a technique to make use of the previously identified unobservable transitions.Proposition 11.
Assume that the net systemPN,M0 is given and v∈Ω(PN,M0) is the current observed sequence with y→∈Y(v). A new transition t is observed. If there exists a vector ε→z satisfying; (13a), (13b), (13c), and (13d), then vt∈Ω(PN′,M0), where PN′ is a Petri net obtained by adding εz to PN.(13a)M0+Co·v→+Cu·y→+σ→u+ε→z≥Preo·,t(13b)σ→u∈Nnu(13c)ε→z∈Zm(13d)ε→z≠0→Proof.
LetM′=M0+Co·v→+Cu·y→ be the marking after firing sequence v. M′∈R(PN′,M0) holds. The constraint (13a) can be rewritten as(14)M′+Cu·σ→u+ε→z≥Preo·,t.Since Cu′=[Cuε→z], (14) is rewritten as(15)M′+Cu′·σ→u1≥Preo·,t.Let M′′=M′+Cu′·σ→u1T. By Theorem 3, there exists an unobservable transition sequence σu′ such that M′σu′M′′. Since M′′≥Preo(·,t), M′σu′M′′t holds, i.e., vt∈Ω(PN′,M0).As shown in (10), the solution of (13a), (13b), (13c), and (13d) is neither unique. We still consider the performance index f=1→mT·abs(ε→z) and convert the absolute value in objective function into linear constraints. The final integer linear programming problem is shown as follows:(16)ILPP3:min1→mT·r→s.t.Eq.13a,13b,13c,and13dS∈0,1m1→mT·S≤m-1-K·S+ε→z≤-1→ma-ε→z≤r→ε→z≤r→r→∈NmbExample 12.
Consider again the net system in Figure3(a) and assume that v=t1t2 is the observed sequence and y→=2T. Now the transition t3 is observed and ILPP 1 has no feasible solution. We solve ILPP 3 to introduce a new unobservable transition. A solution ε→2=1,0,-1T is found. Let Cu=[Cuε→2]. The resulting net system is shown in Figure 3(c) such that t1t2t3∈Ω(PN,M0).


## 3.3. Online Identification Algorithm

There may be different approaches that can provide a solution to Problem6; however we propose an online identification algorithm that recursively determines the structure of the unobservable subnet. Upon each observed transition t, we record t and decide whether a new unobservable transition should be introduced by solving ILPP 1. If it is the case, we obtain the unobservable transition by solving ILPP 3 and update the structure of the unobservable subnet. The identification procedure is shown by Algorithm 1, which monitors the system evolution and waits until a transition is observed.Algorithm 1:Identification of an unobservable subnet.
Input: A net system 〈PNo,M0〉 Output: A Petri net PN with PN=PNo⊗PNu (1) Tu=∅, nu=0, Cu=, y→=, v=′′; (2) wait until transition t is observed; (3) ifnu==0then (4)ifM0+Co⋅v→≥Preo(⋅,t)then (5)v=vt; goto 2; (6)else (7) goto 13; (8)end if (9)else (10)ifILPP 1 admits a solution σ→uthen (11)v=vt; y→=y→+σ→u; goto 2; (12)else (13)ifILPP 3 admits a solution ε→nu and σ→uthen (14)nu=nu+1; Cu=[Cu,ε→nu]; Tu=Tu∪εnu; (15)y→=y→+σ→u; y→=y→1; (16)v=vt; (17)goto 2; (18)else (19)error:cannot find a solution satisfying ILPP 3 (20)return (21)end if (22)end if (23)end ifThe inputs of Algorithm1 are the observable subnet PNo and the initial marking M0, i.e., Preo, Posto, and M0, and its output is the unobservable subnet PNu such that we can obtain the whole net PN=PNo⊗PNu.In line (1), the algorithm initializes the variables. Initially, the unobservable subnetPNu is null, i.e., Tu=∅, Cu is a 0×0 matrix, and the vector y→ is also null. Note that the vector y→ is maintained and updated by Algorithm 1 when a transition is observed. In addition, nu denotes the number of unobservable transitions, and it is the subscript when we name the newly identified transition εnu.In line (3), ifnu equals zero, i.e., no unobservable transition is identified, it is not necessary to solve ILPP 1. Instead, the condition of line (4) is checked.In line (10), ILPP 1 has a feasible solution; then we only update the firing vectory→ and go back to line (2). In lines (14) and (15), a new unobservable transition is identified and we will update the corresponding variables. First, we add the solution ε→nu to Cu as the last column, and the corresponding unobservable transition is called εnu. Note that nu increases by one when a new unobservable transition is identified such that the unobservable transitions are named ε1, ε2, ε3,... We also obtain the value of variable σ→u that represents the firing vector of the previously identified unobservable transitions to enable the observed transition t. Hence we add y→ by σ→u and add the dimension of y→ by one, which means that the new identified unobservable transition εnu fires once.In line (19), it happens that ILPP 3 has no feasible solution, which probably stems from the necessity of a source transition or the inaccurate sensor reading.Example 13.
Consider the observable subnet in Figure4(a), where P=p1,p2,…,p7, To=t1,t2,…,t7, and M0=3,0,1,0,0,0,0T. Assume that the observed sequence is v=t1t2t2t3t6t3t6t2. Upon each observed transition, Algorithm 1 executes the identification procedure. We analyse the transitions in v in sequence.
Initially, the observed sequencev is an empty string, Tu=∅, both Cu and y→ are null, and nu=0.
Occurrence of t 1: the relation M0≥Preo(·,t1) holds, and thus we do not have to solve ILPP 3 to find an unobservable transition. The algorithm sets v=t1.
Occurrence of t 2: M0+(Posto-Preo)·v→=2,2,1,0,0,0,0T≥Preo(·,t2)=0,1,1,0,0,0,0T holds. Thus the algorithm sets v=t1t2.Occurrence of the secondt2: since M0+(Posto-Preo)·v→≱Preo(·,t2), ILPP 3 is solved and the solution ε→1=0,0,1,-1,0,0,0T is found. Then the algorithm updates Cu, nu, and y→ with nu=1, y→=1T and adds ε1 to Tu. The Petri net PN=PNo⊗PNu is shown in Figure 4(b). Now v=t1t2t2.
Occurrence of t 3: since nu>0, we solve ILPP 1 and obtain the solution σ→u=0→, implying that t3 is enabled at the current marking, and y→=y→+0→ remains unchanged.
Occurrence of t 6: ILPP 1 has no feasible solution, i.e., a new unobservable transition should be introduced. Solving ILPP 3 and obtaining the solution ε→2=0,0,0,0,-1,1,0T, we add ε2 to Tu and update Cu. Now the net PN is shown in Figure 4(c) with y→=[1,1]T and v=t1t2t2t3t6.
Occurrence of the second t 3: ILPP 1 has a solution σ→u=0→. Thus we just need to increase the observed sequence, i.e., v=t1t2t2t3t6t3.
Occurrence of the second t 6: A solution to ILPP 1 is σ→u=0,1T, implying that t6 is enabled after firing unobservable transition ε2. The vector y→ is updated with y→=y→+σ→u=1,2T and let v=t1t2t2t3t6t3t6.
Occurrence of the third t 2: ILPP 1 has no feasible solution and a solution ε→3=0,1,0,0,0,0,-1T is found by solving ILPP 3. We add ε3 to set Tu and update the structure of unobservable subnet PNu. The net PN is shown in Figure 4(d). Furthermore, we have y→=1,2,1T and v=t1t2t2t3t6t3t6t2.Figure 4
(a) The observable subnetPNo, (b) the net identified after sequence t1t2t2, (c) the net identified after sequence t1t2t2t3t6, and (d) the net identified after sequence t1t2t2t3t6t3t6t2 by applying Algorithm 1.
(a) (b) (c) (d)As shown in Example13, an unobservable transition is introduced in some cases when a transition t is observed. An unobservable subnet PNu is recursively identified by Algorithm 1 and the Petri net PN=PNo⊗PNu is finally provided. The following theorem proves that the output of Algorithm 1 is a solution to Problem 6.Theorem 14.
Given the observable subnetPNo and the initial marking M0, under Assumption (A1), the identified Petri net PN=PNo⊗PNu by Algorithm 1 is a solution to Problem 6.Proof.
The proof is made by induction.
Basic Step. In this case, the observed sequence v is an empty string and incidence matrix Cu is null. If transition t is now observed, then we check the relation M0+Co·v→≥Preo(·,t), i.e., the relation M0≥Preo(·,t). If it holds, let w=vt=t, and w∈Ω(PN,M0) trivially holds. Otherwise, the solution ε→z is obtained by solving ILPP 3 and PNu is updated by adding an unobservable transition εz. Let w=t and PN=PNo⊗PNu. By Proposition 11, M0εzM′t is trivially verified, namely, w∈Ω(PN,M0).
Inductive Step. Assume that the observed sequence is v and the corresponding firing vector of unobservable transitions is y→∈Y(v). If t is now observed, two different situations are considered. (1)
nu equals 0, i.e., no unobservable transition is introduced during the period of observation v. If M0+Co·v→≥Preo(·,t) is true, then t is enabled at the current marking, i.e., w=vt∈Ω(PN,M0). Otherwise, a solution ε→z is found by solving ILPP 3 and the structure of PN is updated by adding a new unobservable transition εz whose incidence matrix column is ε→z. Let w=vt. By Proposition 11, M0vM′εzM′′[t〉 holds, where M′,M′′∈R(PN,M0), namely, w∈Ω(PN,M0).(2)
nu is greater than 0. In this situation, if ILPP 1 admits a solution, we update y→ and the observed sequence with w=vt. By Theorem 7, w∈Ω(PN,M0) holds. On the other hand, if ILPP 1 has no feasible solution, the solution including ε→z and σ→u is obtained by solving ILPP 3. We update the related variables with y→=y→+σ→u and Cu=[Cuε→z] and add a new unobservable transition εz to Petri net PN. Let w=vt, and then w∈Ω(PN,M0) holds by Proposition 11.
Hence, we conclude that the Petri netPN identified by Algorithm 1 is a solution to Problem 6.


## 3.4. Complexity of the Identification Algorithm

Obviously, the primary determinants of the computational difficulty of this algorithm are two integer linear programming problems ILPP 1 and ILPP 3. It is well known that an integer linear programming problem is NP-hard, but it can be solved easily if the number of variables is small. In Algorithm1, if necessary, ILPP 1 and ILPP 3 are solved serially. In addition, the number of variables in ILPP 3 is greater than that in ILPP 1. Thus we analyse the complexity of ILPP 3 only.We observe thatσ→u, ε→z, and r→ are the integer variables in ILPP 3 and S is a binary variable. Then the number of integer variables is u=nu+3m, where nu denotes the number of unobservable transitions and 3m denotes the sum of the dimensions of ε→z, r→, and S.In other words, the number of integer variables in ILPP 3 is linear (the coefficient is1) with respect to that of unobservable transitions. Thus ILPP 3 is a simple integer programming problem that can be solved efficiently. For example, the unobservable subnet with three unobservable transitions in Example 13 is identified using LPSOLVE (a mixed integer linear programming solver [24]) in 0.0541 seconds on a notebook computer with 2 GHz processor and 8 GB RAM. In addition, we test the presented algorithm on an observable subnet with 43 places, 40 transitions, 140 arcs. In this setting, 15 unobservable transitions are found by solving 25 integer programming problems in 0.3698 seconds on the same computer using LPSOLVE solver.


## 4. Model Identification with Partial Observable Places

### 4.1. Problem Statement

In Section3, we assume that no place is observable. In such a setting, we may not be able to determine an unobservable transition that describes exactly the unknown behavior of a system by solving ILPP 3. The main reasons are the limited knowledge of system evolution and the possibility that there is more than one solution that satisfies the considered linear constraint set even if we choose a performance index. To determine a more authentic unobservable transition, more information on system evolution is needed. In this section, we consider that some of places are observable.Let us consider a net systemPN,M0, where PN=(P,T,Pre,Post) and T=To∪Tu. Assume that Po=Pα1,Pα2,…,Pαh⊆P with h≤m is the set of observable places. For each M∈R(PN,M0), the restriction of M to Po is called apartial marking denoted as Mpo, and Mpo=Mpo denotes that the restriction of M to Po is Mpo.If some of places in a Petri net model are observable, the observed information during system evolution includes not only the observed transitions but also the corresponding partial markings. We denote the output of the system with observable places byw=tβ1tβ2…tβk with k≥1 and the corresponding reached partial markings by M1poM2po…Mkpo, where tβi∈To and Mipo is the observed partial marking after transition tβi for i=1,…,k.Example 15.
Consider again the observable subnet shown in Figure4(a). If the set of observable places is Po=pα1,pα2,pα3=p1,p3,p7, for an observed sequence w=tβ1tβ2tβ3tβ4=t1t2t2t3, the corresponding partial markings can be M1po=2,1,0T, M2po=2,0,0T, M3po=1,0,0T, M4po=1,0,0T; i.e., the observed transition-partial-marking sequence is σ=M0t1M1pot2M3pot2M3pot3M4po. It is clear that the sequence σ cannot be generated by the net in Figure 4(a) and thus some unobservable transitions must occur.Problem 16.
Assume that the observable subnetPNo=(P,To,Preo,Posto) and the initial marking M0 are given and Po=Pα1,Pα2,…,Pαh⊆P with h≤m is the set of observable places. The observed output includes the transition sequence w=tβ1tβ2…tβk with k≥1 and the corresponding reached partial markings M1poM2po…Mkpo, where tβi∈To and Mipo is the observed partial marking after transition tβi for i=1,…,k. The problem consists in determining a Petri net PN with PN=PNo⊗PNu such that w∈Ω(PN,M0) and each marking Mi∈R(PN,M0) after tβi fires satisfies Mipo=Mipo for i=1,…,k.


### 4.2. The Solution to Problem16

This subsection discusses whether an unobservable transition has to be introduced or not under the assumption that some of places are observable. Moreover, we present a technique to show how the unobservable transitions can be introduced.Theorem 17.
Consider net systemPN,M0. Assume that Po=Pα1,Pα2,…,Pαh with h≤m is the set of observable places and the observed transition sequence is v with y→ being the corresponding firing vector. Assume that a transition tβk and the corresponding partial markings Mkpo are observed. If (17a), (17b), and (17c) admit a solution, then vtβk∈Ω(PN,M0) and the marking Mk after tβk fires satisfies Mkpo=Mkpo.(17a)M0+Co·v→+Cu·y→+Cu·σ→u≥Preo·,tβk(17b)A·M0+Co·v→+Cu·y→+Cu·σ→u+Co·,tβk=Mkpo(17c)σ→u∈Nnuwhere A is an h×m matrix such that A(i,αi)=1 for i=1…h and 0 otherwise. The matrix A is dedicated to projecting a marking M∈R(PN,M0) onto a partial marking based on the set of observable places Po.Proof.
If we do not consider the observable places and remove constraint (17b), then (17a), (17b), and (17c) are reduced to be (8). By Theorem 7, vtβk∈Ω(PN,M0) is trivially verified. However, if constraint (17b) is removed, there may be numerous solutions that satisfy vtβk∈Ω(PN,M0) but violate Mkpo=Mkpo. When the set of observable places is taken into account, constraint (17b) guarantees that these solutions that satisfy Mkpo=Mkpo are chosen only. Thus this theorem is verified.The solution of (17a), (17b), and (17c) is also not a singleton. We again choose the performance index 1→nuT·σ→u and obtain the following integer linear programming problem that minimizes the considered performance index:(18)ILPP4:min1→nuT·σ→us.t.Eq.17a,17b,and17cProposition 18.
Consider net systemPN,M0. Assume that Po is the set of observable places and the observed transition sequence is v with y→ being the corresponding firing vector. A transition tβk and the corresponding partial marking Mkpo are observed. If there exists a vector ε→z satisfying (19a), (19b), (19c), (19d), and (19e), then vtβk∈Ω(PN′,M0) and the marking Mk after tβk fires satisfies Mkpo=Mkpo, where PN′ is a Petri net obtained by adding εz to PN.(19a)M0+Co·v→+Cu·y→+σ→u+ε→z≥Preo·,tβk(19b)A·M0+Co·v→+Cu·y→+σ→u+ε→z+Co·,tβk=Mkpo(19c)σ→u∈Nnu(19d)ε→z∈Zm(19e)ε→z≠0→Proof.
If constraint (19b) is removed, then (19a), (19b), (19c), (19d), and (19e) are reduced to be (13a), (13b), (13c), and (13d). By Proposition 11, vtβk∈Ω(PN′,M0) is trivially verified. On the other hand, constraint (19b) guarantees that the solutions satisfying Mkpo=Mkpo are chosen only. Thus, this proposition is proved.Although constraint (19b) is imposed to choose the solutions satisfying the observed partial markings, the solution of (19a), (19b), (19c), (19d), and (19e) is still not unique. As shown in ILPP 3, we choose 1→mT·abs(ε→z) as the performance index and obtain the following programming problem:(20)ILPP5:min1→mT·absε→zs.t.Eq.19a,19b,19c,19d,and19eThe solution to Problem16 can be obtained by making slight changes to Algorithm 1, i.e., replacing ILPP 1 and ILPP 3 with ILPP 4 and ILPP 5, respectively.


## 4.1. Problem Statement

In Section3, we assume that no place is observable. In such a setting, we may not be able to determine an unobservable transition that describes exactly the unknown behavior of a system by solving ILPP 3. The main reasons are the limited knowledge of system evolution and the possibility that there is more than one solution that satisfies the considered linear constraint set even if we choose a performance index. To determine a more authentic unobservable transition, more information on system evolution is needed. In this section, we consider that some of places are observable.Let us consider a net systemPN,M0, where PN=(P,T,Pre,Post) and T=To∪Tu. Assume that Po=Pα1,Pα2,…,Pαh⊆P with h≤m is the set of observable places. For each M∈R(PN,M0), the restriction of M to Po is called apartial marking denoted as Mpo, and Mpo=Mpo denotes that the restriction of M to Po is Mpo.If some of places in a Petri net model are observable, the observed information during system evolution includes not only the observed transitions but also the corresponding partial markings. We denote the output of the system with observable places byw=tβ1tβ2…tβk with k≥1 and the corresponding reached partial markings by M1poM2po…Mkpo, where tβi∈To and Mipo is the observed partial marking after transition tβi for i=1,…,k.Example 15.
Consider again the observable subnet shown in Figure4(a). If the set of observable places is Po=pα1,pα2,pα3=p1,p3,p7, for an observed sequence w=tβ1tβ2tβ3tβ4=t1t2t2t3, the corresponding partial markings can be M1po=2,1,0T, M2po=2,0,0T, M3po=1,0,0T, M4po=1,0,0T; i.e., the observed transition-partial-marking sequence is σ=M0t1M1pot2M3pot2M3pot3M4po. It is clear that the sequence σ cannot be generated by the net in Figure 4(a) and thus some unobservable transitions must occur.Problem 16.
Assume that the observable subnetPNo=(P,To,Preo,Posto) and the initial marking M0 are given and Po=Pα1,Pα2,…,Pαh⊆P with h≤m is the set of observable places. The observed output includes the transition sequence w=tβ1tβ2…tβk with k≥1 and the corresponding reached partial markings M1poM2po…Mkpo, where tβi∈To and Mipo is the observed partial marking after transition tβi for i=1,…,k. The problem consists in determining a Petri net PN with PN=PNo⊗PNu such that w∈Ω(PN,M0) and each marking Mi∈R(PN,M0) after tβi fires satisfies Mipo=Mipo for i=1,…,k.


## 4.2. The Solution to Problem16

This subsection discusses whether an unobservable transition has to be introduced or not under the assumption that some of places are observable. Moreover, we present a technique to show how the unobservable transitions can be introduced.Theorem 17.
Consider net systemPN,M0. Assume that Po=Pα1,Pα2,…,Pαh with h≤m is the set of observable places and the observed transition sequence is v with y→ being the corresponding firing vector. Assume that a transition tβk and the corresponding partial markings Mkpo are observed. If (17a), (17b), and (17c) admit a solution, then vtβk∈Ω(PN,M0) and the marking Mk after tβk fires satisfies Mkpo=Mkpo.(17a)M0+Co·v→+Cu·y→+Cu·σ→u≥Preo·,tβk(17b)A·M0+Co·v→+Cu·y→+Cu·σ→u+Co·,tβk=Mkpo(17c)σ→u∈Nnuwhere A is an h×m matrix such that A(i,αi)=1 for i=1…h and 0 otherwise. The matrix A is dedicated to projecting a marking M∈R(PN,M0) onto a partial marking based on the set of observable places Po.Proof.
If we do not consider the observable places and remove constraint (17b), then (17a), (17b), and (17c) are reduced to be (8). By Theorem 7, vtβk∈Ω(PN,M0) is trivially verified. However, if constraint (17b) is removed, there may be numerous solutions that satisfy vtβk∈Ω(PN,M0) but violate Mkpo=Mkpo. When the set of observable places is taken into account, constraint (17b) guarantees that these solutions that satisfy Mkpo=Mkpo are chosen only. Thus this theorem is verified.The solution of (17a), (17b), and (17c) is also not a singleton. We again choose the performance index 1→nuT·σ→u and obtain the following integer linear programming problem that minimizes the considered performance index:(18)ILPP4:min1→nuT·σ→us.t.Eq.17a,17b,and17cProposition 18.
Consider net systemPN,M0. Assume that Po is the set of observable places and the observed transition sequence is v with y→ being the corresponding firing vector. A transition tβk and the corresponding partial marking Mkpo are observed. If there exists a vector ε→z satisfying (19a), (19b), (19c), (19d), and (19e), then vtβk∈Ω(PN′,M0) and the marking Mk after tβk fires satisfies Mkpo=Mkpo, where PN′ is a Petri net obtained by adding εz to PN.(19a)M0+Co·v→+Cu·y→+σ→u+ε→z≥Preo·,tβk(19b)A·M0+Co·v→+Cu·y→+σ→u+ε→z+Co·,tβk=Mkpo(19c)σ→u∈Nnu(19d)ε→z∈Zm(19e)ε→z≠0→Proof.
If constraint (19b) is removed, then (19a), (19b), (19c), (19d), and (19e) are reduced to be (13a), (13b), (13c), and (13d). By Proposition 11, vtβk∈Ω(PN′,M0) is trivially verified. On the other hand, constraint (19b) guarantees that the solutions satisfying Mkpo=Mkpo are chosen only. Thus, this proposition is proved.Although constraint (19b) is imposed to choose the solutions satisfying the observed partial markings, the solution of (19a), (19b), (19c), (19d), and (19e) is still not unique. As shown in ILPP 3, we choose 1→mT·abs(ε→z) as the performance index and obtain the following programming problem:(20)ILPP5:min1→mT·absε→zs.t.Eq.19a,19b,19c,19d,and19eThe solution to Problem16 can be obtained by making slight changes to Algorithm 1, i.e., replacing ILPP 1 and ILPP 3 with ILPP 4 and ILPP 5, respectively.


## 5. Conclusion

The paper addresses the problem of model identification of unobservable system behavior by assuming that the observable subnet model is known. We consider two different cases: first, no place is observable; second, a subset of places is observable. Two problems are discussed in both cases and an online algorithm is proposed which computes the unobservable transitions recursively and provides solutions for these two problems. The computational complexity of the algorithm is analysed and it can be executed efficiently because of a small number of unknowns of the integer programming problem.Further research will be twofold. First, we plan to develop an approach that provides a solution to the problem in this paper and minimizes the unobservable subset, e.g., minimizing the number of unobservable transitions or minimizing the sum of weights of the arcs connected with unobservable transitions. Second, we aim to explore the identification of unobservable transitions in the case that the given subnet includes unobservable transitions.



---

*Source: 2895685-2019-03-27.xml*