Online Fault Diagnosis of Labeled Petri Nets Based on Reachability Graphs and Topological Sorting

Abstract

In this article, we propose an online fault diagnosis approach for labeled Petri nets. When observing an event, the reachability graph of the unobservable subnet (i.e., the net consisting of all places, unobservable transitions, and the attached arcs between them) is first constructed and then a topological sort (i.e., an ordered list of markings) of the reachability graph is obtained. According to the topological sort, each marking in the reachability graph is associated with a vector that contains diagnosis information to form a new graph, called a diagnosis graph. Based on the diagnosis graph constructed for each observed event, an online algorithm is developed to perform diagnosis. When the considered Petri net systems have a small amount of unobservable transitions, the proposed approach enjoys a high computational efficiency compared with the existing ones using integer linear programming.

Keywords

• Petri net
• reachability graph
• topological sort
• discrete event system