Maximally Permissive Deadlock and Livelock Avoidance for Automated Manufacturing Systems via Critical Distance

The problem under consideration in this paper is how to avoid deadlocks and livelocks in the paradigm of Petri nets (PNs). Although deadlock and livelock avoidance has been extensively studied in existing literature, fewer results can be applied to practical automated manufacturing systems (AMSs) due to expensive computations and reduced permissiveness. In this paper, we propose an efficient and maximally permissive control scheme to avoid deadlocks and livelocks by using critical distance. From the perspective of the reachability graph of a PN, critical distance is equal to the maximum number of transitions among all transition sequences from any critical state to its corresponding deadlock or livelock state. First, we show how to calculate the critical distance of a PN in an efficient way by using a portion of reachable states. Then, local reachability graphs are established based on critical distance to avoid deadlocks and livelocks. The provided policy is maximally permissive since only the necessary minimum number of illegal transitions are forbidden at each state. Several representative examples are presented to illustrate our approach. Note to Practitioners—Deadlock and livelock avoidance is a crucial problem in automated manufacturing systems (AMSs). Various methods have been proposed to deal with deadlocks and livelocks by researchers and practitioners. However, there exist fewer works that focus on deep exploration regarding how long a deadlock or livelock will occur from a safe state. As a consequence, the existing works suffer from the disadvantages of being too aggressive or conservative, i.e., checking the whole state space or forbidding many acceptable states when avoiding deadlocks and livelocks. Through the analysis of a partial of reachable states, this paper derives the critical distance of Petri nets modeling AMSs, which is equal to the maximum number of transitions among all transition sequences from any critical marking to its corresponding deadlock or livelock marking. All deadlocks and livelocks, if exist, can be detected at any given marking within the critical distance. Our approach not only is maximally permissive but also explores only a partial of states, thereby mitigating state explosion problem.