The Probabilistic Liveness Decision Method of Unbounded Petri Nets Based on Machine Learning
针对无界Petri网活性判定难题，提出基于深度神经网络的概率预测方法，通过有限状态近似无限空间，利用图卷积和门控循环单元提取特征，实验验证了有效性。
The liveness of Petri nets (PNs) means that every event can occur in any state, establishing a close relationship with the deadlock-free property of existing systems. Due to the problem of state space explosion and the infinite state space of unbounded PNs (UPNs), the time complexity and space complexity of the liveness decision are difficult to give accurate measures; at least, they are both NP-hard. Except for some particular subclasses of UPNs, there has not been an accurate method to decide the liveness of generalized UPNs. Thus, a liveness decision method from a machine learning perspective is proposed to predict probability values about UPNs’ liveness within a finite time. The method aims to learn the feature information on UPNs by deep neural networks and establish the mapping relationship between the UPNs and the liveness. First, the concept of approximating infinite space with finite states is applied to generate reachability graphs at different moments, following the firing rules of a UPN. Then, the graph convolutional network (GCN)-based reachability graph feature representation module and the gated recurrent unit (GRU)-based UPN feature representation module are designed to map the reachability graphs at different moments into the low-dimensional feature space. And the feature vector that can characterize the UPN’s liveness is obtained to decide the liveness probabilistically. Finally, three datasets, including 50000 samples, are constructed. Based on these datasets and some case studies, the experimental results validate the method’s ability to make liveness decisions for UPNs, demonstrating its strong performance in terms of effectiveness and generalization.