A Deadlock Prevention Policy Based On The Theory Of Regions

As a deadlock prevention strategy based on the reachability graph (RG), the theory of regions can promise the maximally permissive liveness-enforcing behavior of the net system to be controlled. However, the major hurdle of the theory of regions for deadlock prevention in a Petri net formalism is the exponential increase of the reachable states and the number of linear programming problems to be solved. This thesis investigates generalized Petri nets, takes S~3PR and S~4PR, two classes of generalized Petri nets, as examples and proposes an improved use of theory of regions for the deadlock prevention for flexible manufacturing systems (FMS), from which a maximally permissive liveness-enforcing supervisor can be derived with inexpensive computational cost. However, the proposed strategy can be used to other classes of Petri nets.In this research, we first introduce the elimination process just based on the fact that different marking/transition separation instances may have the same separation condition, from which the redundant marking/transition separation instances can be removed. Then the stratrgy proceeds in an iterative way. And for a feasible solution of a linear programming problem, it is then used to verify whether it is the solution of other marking/transition separation instances that are unsolved, which can avoid solving a large number of linear programming problems. The iterative process is repeated until the computed monitors implement all marking/transition separation instances of a plant Petri net model. Futhermore, redundant control places can be removed in some extent so that a structurally simple Petri net supervisor can be obtained.