Research On Transition Sequence Estimation And Initial Identification Estimation Of Discrete Event Systems Based On Petri Nets

Discrete event systems(DESs)are a kind of dynamic system whose state will change at some random time points.With the development of the times,the level of information technology continues to improve,and the scale of DESs continues to increase.Therefore,the research on various estimation problems of DESs in life becomes particularly important.Petri nets have two forms of expression,graphical and mathematical,which is suitable for DESs modeling and analysis.In this thesis,Petri nets are used as a modeling tool to study the estimation of the least-cost transition sequences and the estimation of the minimum initial markings.1.Aiming at the estimation of the least-cost transition firing sequences,the basic reachability graph(BRG)of Petri net model is searched to get the least-cost transition sequences.Firstly,given the structure of Petri net model,which is assumed to be bounded,and the unobservable transitions in the Petri net form an acyclic subnet,and each transition in the Petri net has a positive integer cost.Secondly,BRG is constructed according to the concept of basic marking,which avoids traversing all the states of the system and reduces the scale of the solution space.Then,two algorithms are proposed for labeled Petri nets and general Petri nets,and the corresponding algorithm complexity analysis is given.For the first algorithm,given a labeled Petri net and a labeled sequence,the least-cost transition sequences can be found by searching BRG.For the second algorithm,given the Petri net structure and initial marking of Petri net,the final state of the system is specified.The least-cost transition firing sequences of the system from the initial marking to the final marking can be obtained by executing the algorithm proposed in this thesis.Finally,two application examples of the two designed algorithms are given:a system of simple sequential processes with resources(S~3PR)and a wireless sensor network(WSN).The effectiveness and correctness of the algorithms in this thesis are verified by these two examples.The results show that some time-consuming computations can be moved off-line by searching the constructed BRG,and a lot of computational time can be saved.2.In order to determine the minimum resources needed to complete the specified task sequence during the initialization of the manufacturing system,this thesis chooses to use the labeled Petri net to model the manufacturing system,transforms the objective problem into the minimum initial markings estimation problem in the labeled Petri net.An algorithm based on dynamic planning is proposed by this thesis.Given a labeled Petri net model,and the unobservable transitions in the Petri net form an acyclic subnet.When a label is observed,at most two unobservable transitions are allowed to fire before the observable transition.According to the proposed algorithm,the node evolution diagram is constructed for the initial markings with the minimum number of tokens,which avoids the exhaustive calculation of the minimum initial marking estimations.The main contributions of this thesis are as follows:an algorithm based on BRG is proposed to estimate the least-cost transition firing sequences,and then an algorithm based on dynamic programming is proposed to estimate the minimum initial markings.At the end,the work of this thesis is summarized,and the future research of estimation problem of the least-cost transition firing sequences and the minimum initial markings in Petri nets is prospected.