Time based deadlock prevention for Petri nets. (March 2022)

• Record Type: Journal Article
• Authors: Boucheneb, Hanifa; Barkaoui, Kamel; Xing, Qian; Wang, KuangZe; Liu, GaiYun; Li, ZhiWu
• Is Part Of: Automatica. Volume 137(2022)
• Publication Date: 2022-03
• Subjects: Petri net -- Time petri net -- Deadlock prevention -- Time based deadlock prevention -- Supervisory control; Automatic control -- Periodicals; Automation -- Periodicals; 629.805
• DOI: 10.1016/j.automatica.2021.110119
• Languages: English
• ISSNs: 0005-1098

Abstract

Abstract: This paper investigates the deadlock prevention problem for Petri nets (PN), in which the control is performed by appropriately setting time constraints on transitions, in terms of firing intervals. We show that this time based deadlock prevention (TBDP) problem is decidable for bounded PN and can be formalised as a parametric model checking problem. However, in this context, the parametric model checking faces a severe state explosion problem. To deal with this limitation, we propose a symbolic approach that abstracts firing order constraints and bypasses the use of parameter domains with their associated very costly operations. Both approaches can handle, as an input model, a (time) PN with controllable/uncontrollable transitions. In such a case, they expose whether or not the firing intervals of the controllable transitions of the input model can be restricted so as to force the deadlock freeness (i.e., there is no marking with no enabled transitions).