Reachability Analysis And Deadlock Control For Flexible Manufacturing Systems Using Petri Nets

Flexible manufacturing systems(FMSs) are computer-controlled systems that consist of computer numerically controlled machine tools, bu?ers, ?xtures, robots, automated guided vehicles(AGVs), and other material-handling devices, some of which are recognized as their shared resources. Deadlocks may occur due to the competition for limited shared resources among concurrently-executed processes, which greatly decrease the e?ciency of the system. Therefore, the analysis and control of deadlock in FMSs are imperative As a mathematical tool, Petri nets have been widely used for modeling analysis and deadlock control of FMSs for their compact and graphical representation. In recent years, in the framework of Petri nets, researchers develop many policies to deal with the deadlock problem in FMSs. Generally, there are three very important criteria in evaluating the performance of a deadlock control policy: behavioral permissiveness, structural complexity and computational complexity. From a technical perspective, most of the control policies resolving deadlocks are developed via structural analysis or reachability graph analysis of Petri nets. The former always derives a deadlock prevention policy by structural objects of Petri nets, such as siphons or resource-transition circuits, which can lead to a computationally e?cient livenessenforcing supervisor in general but always exclude a part of permissive behaviors The latter can always obtains an optimal or suboptimal liveness-enforcing supervisor with highly behavioral permissiveness while su?ers from a state explosion problem since it requires generating all or a part of reachable markings.This thesis focuses on developing an e?cient method to compute the set of reachable markings and designing liveness-enforcing supervisors for FMSs. The main results of this research are as follows.1. For a class of Petri nets, which is called pipe-line nets(PLNs), this thesis proposes a novel and computationally e?cient approach to compute the set of reachable markings by using P-invariants and strict minimal siphons. Based on the set of minimal P-semi?ows, we obtain the set of invariant markings which may include spurious markings due to the existence of shared resources. In this case, strict minimal siphons are extracted from resource circuits. Then, a su?cient and necessary condition to identify the spurious markings is driven by analyzing the number of tokens in operation places of strict minimal siphons and their bounds. Finally, the set of reachable markings can be obtained by removing all the spurious markings from the set of invariant markings.Experimental results show the e?ciency of the proposed method.2. A linear system of simple sequential process with resources(LS3PR) is a more general class of Petri nets than PLNs. This thesis extends the approach of computing the set of reachable markings of PLNs by using P-invariants and strict minimal siphons to an LS3 PR with speci?c resource places. Then a more general su?cient and necessary condition to identify the spurious markings is driven by analyzing the number of tokens in the operation places of strict minimal siphons and their bounds. Finally, the reachability set of the net is generated by removing all the spurious markings from the set of invariant markings. Experimental calculations and analysis validate the e?ectiveness of the proposed method.3. Most existing deadlock prevention polices tackle the deadlock issue arising in FMSs modeled with Petri nets by adding control places. Based on the reachability graph analysis, a maximally permissive supervisor is always obtained with all legal markings reachable and all ?rst-met bad markings(FBMs) forbidden. In this thesis, based on the reachability graph analysis, we present a novel deadlock control policy converting deadlock markings to legal markings by adding control transitions on the plant, which preserves all the reachable markings of the plant and does not introduce extra markings in the controlled system. In order to reduce the structural complexity of the supervisor,we develop a set covering technique, aiming to minimize the number of control transitions. The resulting net preserves all reachable markings of the plant and converts all deadlock markings to legal ones, i.e., it is an optimal liveness-enforcing supervisor with minimal control transitions. Compared with existing place-based deadlock prevention polices, the transition-based deadlock control policy has more permissive markings.4. For a system of simple sequential process with resources(S3PR), this thesis proposes a deadlock avoidance policy that only prohibits the transitions that lead a strict minimal siphon to be emptied. Then, by analyzing the markings in the reachability graph of an S3 PR, we derive a su?cient and necessary condition under which a maximally permissive liveness-enforcing supervisor can be obtained by the deadlock avoidance policy. Finally,we can conclude that when a special class of S3 PR, which are called weakly-dependent S3 PR, satis?es a special condition with respect to its net structure, an optimal livenessenforcing supervisor can be obtained by the deadlock avoidance policy.