The Probabilistic Liveness Decision Method of Unbounded Petri Nets Based on Machine Learning

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.

I. Introduction

Petri net (PN) offers a flexible and intuitive graphical representation for modeling and analyzing concurrent and distributed systems [1]. The boundedness property of PNs indicates the resource capacity of systems. PNs are classified into bounded PNs and unbounded PNs (UPNs) based on the presence of finite and infinite markings. The PNs are used to model discrete event systems, such as flexible manufacturing systems, traffic systems, fault diagnosis, operating systems, human-computer interaction, etc. [2], [3], [4], [5].