Deadlock Analysis And Control Using Petri Net Decomposition Techniques

An automated manufacturing system(AMS)is a production process with no or little manual intervention.Due to the lack of human intervention,it is liable to cause deadlocks because of unreasonable resource allocation.In order to make automated manufacturing systems run stably and safely,the deadlock problem of manufacturing systems must be handled.Petri nets,as a mathematical modeling and analysis tool,can accurately and effectively model,analyze and control deadlocks for automated manufacturing systems.Based on Petri nets,researchers have proposed many control methods for deadlock problems in automated man-ufacturing systems.Generally,these control methods need to calculate either reachability graphs or siphons of the net systems.Thus,the computational complexity is a problem that needs to be concerned.Aiming at the problem of computational complexity,this thesis puts forward a decomposi-tion control method for Petri nets,taking S~3PR as models.It first decomposes a Petri net model into two(or several)subnets via shared transitions and designs a liveness-enforcing Petri net supervisor for each subnet.Then we analyze the cause of deadlocks when merging the two controlled subnets.Finally,control places are adjoined to the merged net to obtain a liveness-enforcing Petri net supervisor.The method proposed in this thesis only needs to calculate the reachability graphs of the subnets.Since the size of reachability graph has an exponential relationship with that of the Petri net,the sizes of the reachability graphs of the subnets are greatly reduced compared with that of the whole net system.Thus,this method can effectively reduce the computational overhead.The main contributions of this thesis are as follows:1.Aiming at the deadlock problem when merging two controlled subnets,we find that some special states of the two controlled subnets will mutually inhibit the firing of shared transi-tions in the merged net system through analyzing the states of the subnets.As a consequence,all shared transitions are unenabled,causing a deadlock.Against the reason of deadlocks,this thesis presents a method to prevent it.2.By decomposing a Petri net in a multi-level way,the size of each subnet can be small enough,hence the computational cost can be further reduced.The study finds that some Petri net models can be decomposed into n live subnets in a multi-level way.Thus,there is no need to use the existing methods to design liveness-enforcing Petri net supervisors for subnets in the first step,and we just need to design liveness-enforcing Petri net supervisors with this method level by level.3.Using the technique of vector covering approach to reduce the number of special states that need to be considered can effectively reduce the redundant control places,which makes the structure of supervisors smaller and also reduces the computational burden to a certain extent.4.By subdividing the special states,and studying the more specific correspondence relations between the special states of the two controlled subnets,we have optimized the control strat-egy.The optimized control strategy can more effectively control the deadlock problem of Petri nets.Finally,a liveness-enforcing Petri net supervisor with more permissive behavior can be obtained.