Designing Liveness-Enforcing Supervisors for Manufacturing Systems by Using Maximally Good Step Graphs of Petri Nets

Many deadlock control methods rely on reachability graphs of Petri nets (PN), thus suffering from state-space explosion issues. This paper proposes a novel approach to designing liveness-enforcing supervisors for PN by constructing its maximally good step graphs (MGSG), a class of partial order techniques in mitigating the aforementioned issues. Specifically, we first categorize the MGSG markings into allowed and unallowed ones. Then, we define good and risky transitions at allowed markings. Through the execution of risky transitions, the initial marking cannot be reachable from the allowed ones. Next, we design a maximal number of risky transitions (MNRT) problem to compute control places. In MNRT, all allowed markings and the firing of all good transitions are permitted, while risky transitions are forbidden. The objective is to maximize the prevention of risky transitions by using a single control place, which can be achieved by solving an integer linear programming problem. MNRT problems are recursively solved for unforbidden risky transitions until their resulting markings are prohibited. Finally, a controlled PN is generated and has been demonstrated to retain liveness. The experimental results show that our approach effectively reduces the number of control places and mitigates state-space explosion issues over its state-of-the-art peers.