Petri Net-based Set Traversal And Deadlock Research Based On Binary Decision Graph

The system reachable states is exponentially increasing by the scale of Petri net,so the combinatorial state explosion problem of Petri net has become the bottleneck in Petri net application.Therefore,it is very important,that how to obtain the Petri net reachable state set and strictly minimal siphons in shorter time and smaller space,for the application of Petri nets in large scale system.In this paper,we study the application of binary decision diagram(BDD)in Petri net.Obtaining strictly minimal siphon plays a key role in deadlocks prevention.We propose a method to fast obtain strictly minimal siphons of Petri net based on BDD,and optimize the algorithms of obtaining reachable set and minimal siphons.Firstly,focusing on existing algorithm of obtaining the Petri nets reachable set based on BDD,we find the shortage of sub-functions' frequently using when passing and processing parameters with single transition.And proposing the method of passing and processing parameters with multiple transition.We can greatly reduce the using of sub-functions,to speed up the obtaining of reachable set.Then,in view of the fact that BDD has not been used to obtain the strictly minimal beacon in the existing literature,we creatively propose a fast method for obtaining the strictly minimal siphons based on BDD.This method is easy to comprehend and realize.The strictly minimal siphons can be obtained by directly obtaining and processing minimal siphons and traps of Petri nets with BDD.Which not only needs shorter time and smaller space,but also is suitable for large-scale Petri net.In addition,we propose the concept of maximal inclusion for a shortage that siphons can not be judged and removed multiplely when processing siphons'relationship in the existing algorithm,making it more quickly to obtain strictly minimal siphons.Finally,we develop a simulation software platform based on BDD,to obtain strictly minimal siphons and so on of Petri net.At the same time,some experiments are carried out based with this software.And comparing the obtaining results with the Petri net analysis software INA.The results show that the proposed methods require shorter time and smaller space.In addition,the deadlock prevention of S3PR model in automatic manufacturing system(AMS)is realized based on strictly minimal siphons.