Calculation and Analysis of Petri Net Reachability Graphs by a Think-Globally-Act-Locally Method

Li Cheng-zong, Fubao Jin, Yufeng Chen, Zhiwu Li, Murat Uzam, Huimin MaMathematics 2025 · DOI

TL;DR

This paper introduces a novel "Think-Globally-Act-Locally" (TGAL) approach to efficiently compute and analyze the reachability graphs (RGs) of complex discrete event systems modeled with Petri nets. By strategically introducing a "global idle place" (GIP) and iteratively updating token counts, the method significantly reduces redundant calculations and computational cost, addressing the notorious "state explosion" problem.

What Problem Does This Paper Address?

Discrete event systems (DESs) are ubiquitous in modeling complex systems, and Petri nets are a powerful tool for their analysis and control. A crucial aspect of Petri net analysis is the computation of the reachability graph (RG), which enumerates all possible states (markings) a system can reach. However, for large and complex systems, the number of reachable markings can grow exponentially, leading to the "state explosion" problem. This makes traditional RG analysis computationally intractable. Existing methods, while attempting to mitigate this, often suffer from repeated calculations of states and transitions, wasting computational resources. This paper aims to provide a more efficient and less redundant method for computing and analyzing RGs, particularly for large-scale DESs.

Methods

The core of this paper is a TGAL-based method that iteratively computes the RG. The key innovation is the introduction of a "global idle place" (GIP) into the Petri net model. This GIP doesn't alter the fundamental properties of the original system but acts as a control mechanism for the iterative RG generation.

Here's how it works:

  • Iterative Generation: The RG is built step-by-step. In each iteration, the GIP's token count is incremented. This controlled increment ensures that only a limited number of new states are generated per iteration.
  • Leveraging Previous States: Crucially, the method reuses previously computed reachable markings (RMs) and legal markings (LMs) from prior iterations. This avoids recomputing states that have already been analyzed.
  • "Think-Globally-Act-Locally" Principle: The "think globally" aspect comes from considering the overall system's state space, while "act locally" refers to the iterative, step-by-step generation and analysis of states, focusing on the immediate impact of the GIP's token increment.
  • Reduced Redundancy: By classifying states as legal (LM) or illegal (ILM) and ensuring that each state is computed and classified only once, the method significantly reduces computational redundancy compared to previous TGAL-based approaches.

The paper also presents algorithms for computing RMs and for classifying LMs and ILMs based on this TGAL framework.

Datasets

The paper does not introduce new datasets. Instead, it uses four typical Petri net models from existing literature ([14], [29], [25], and another unnamed source) to demonstrate and evaluate the proposed method. These models vary in size and complexity, allowing for a comprehensive performance comparison.

Key Insights and Ideas

  • The GIP as a State-Space Navigator: The global idle place (GIP) is a clever mechanism. By incrementally adding tokens to it, the method effectively "navigates" the state space in a controlled manner, preventing the explosion of states in a single step.
  • Eliminating Redundant Computations: The most significant insight is the focus on computing and classifying each system state only once. This directly tackles the inefficiency of previous methods that re-analyzed already processed states, leading to substantial computational savings.
  • Guaranteed Correctness with Efficiency: The TGAL approach, by design, preserves the original net system's properties. This means the efficient RG computation doesn't come at the cost of accuracy or completeness.
  • Scalability Potential: The iterative nature and reduced redundancy suggest that this method is particularly well-suited for analyzing larger and more complex Petri net models, where traditional methods fail.

Key Results

The paper demonstrates the effectiveness of its TGAL-based method through extensive experimental results on several benchmark Petri net models. The key findings are:

  • Significant Reduction in Computational Cost: Compared to existing TGAL-based methods ([24, 26]), the proposed approach drastically reduces the number of RMs and LMs that need to be computed and analyzed. For instance, in one example, it computed only 19.5% of the RMs and 18.6% of the LMs.
  • Improved Time Efficiency: This reduction in computation directly translates to significant speedups. The proposed method achieved time savings of up to 70.0% and 24.7% compared to other methods in one case, and even more substantial savings in others (e.g., saving 8,792.3 seconds compared to one method).
  • Effective State Classification: The method successfully partitions the computed RMs into legal (LMs) and illegal (ILMs), which is crucial for supervisory control design.

Limitations and Future Work

The authors acknowledge a primary limitation:

  • State Storage and I/O Overhead: The iterative nature of the algorithm involves frequent reading and writing of a large number of states, which can lead to significant I/O overhead and impact efficiency for extremely complex systems.

Future research directions suggested by the authors include:

  • Improving State Storage: Developing more efficient state storage mechanisms to mitigate the I/O bottleneck.
  • Extending to Other Petri Net Variants: Adapting the proposed method to other types of Petri nets, such as time Petri nets, colored Petri nets, and object Petri nets, to broaden its applicability.

Summary updated

Abstract

A think-globally-act-locally (TGAL) technique is proven to be an effective method to address the state explosion issue for complex discrete event systems modeled with Petri nets. This paper introduces a TGAL-based method for computing and analyzing the reachability graph (RG) of Petri net models. Given a net system, the TGAL technique strategically introduces a global idle place (GIP) to iteratively generate its RG by updating the token count. At each step, the reachable markings (RMs) and legal markings (LMs) obtained by the previous iterations are considered to calculate the corresponding states of the current step. According to the enforced control requirement, a system state is required to be computed and classified only once during an iterative process. This method only calculates the necessary number of RMs and reduces computational redundancy, which minimizes the computational cost. Four typical Petri net models from existing studies are employed to demonstrate the method.
BibTeX
@inproceedings{chengzong2025calculation,
  author = {LI Cheng-zong and Fubao Jin and Yufeng Chen and Zhiwu Li and Murat Uzam and Huimin Ma},
  title = {{Calculation and Analysis of Petri Net Reachability Graphs by a Think-Globally-Act-Locally Method}},
  booktitle = {Mathematics},
  year = {2025},
  doi = {10.3390/math13050793},
}
Figure