Design Of Liveness-enforcing Supervisor And Enumeration Of Reachable States For Petri Nets

Deadlock prevention is an inevitable issue when using Petri nets to model and analyze a flexible manufacturing system (FMS). Behavioral permissiveness, structural complexity, and computational complexity are three universal criteria for reflecting the performance of a liveness-enforcing supervisor. Out of the many possible technical solutions available, structural and reachability analysis are two popular techniques used to deal with deadlock prevention by Petri nets. The former recognizes a special structure, usually a siphon that is a set of special nodes of a net system rendering deadlocks arise, and impose a constraint upon the structure to prevent the net system from reaching deadlock states. The latter is an effective and accurate method to analyze and verify a net system and always based on reachability graphs (RG), which can provide a global reachability information of the net system. A state that can lead a system to a deadlock state can be probed by RG and controlled by imposing a constraint to make the system far away from deadlocks. Structural analysis based liveness-enforcing supervisors always possess the superiority of low structural and computational complexity but most of them lost the character of maximal permissiveness. A highly or even maximally permissive liveness-enforcing supervisor can always be obtained by reachability analysis while the problems of high computational and structural complexity are what we have to deal with.According to the analysis of the above two techniques, considering their respective advantages, the thesis proposes siphon based deadlock prevention policies and methods for enumerating the reachable states for Petri nets, respectively.First, a siphon based deadlock prevention policy is developed for a class of Petri net, where the mixed integer programming (MIP) technique is iteratively applied to check liveness and find siphons of a given net. The policy mainly contains two stages: siphon control stage and extended siphon control stage. At the first stage, monitors are added upon the complementary sets of obtained siphons to reserve legal states at large. However, the monitors added at the first stage may co-produce new unmarked siphons with resource and operation places. Hence, at the second stage, the monitors are added with their output arcs pointed to the source transitions to avoid the generation of new unmarked siphons. Moreover, an output arc moving algorithm is proposed to release legal states of controlled models. The policy requires few computational amount but can provides a highly or even maximally permissive liveness-enforcing supervisor with relatively simple control structure. Second, for a class of Petri nets with only elementary and weakly dependent siphons, a maximally permissive policy is designed. If conditions are satisfied, a weakly dependent siphon is controlled as long as its elementary siphons are controlled. Monitors are added upon on the complementary sets of the elementary siphon to ensure that the final supervisor is optimal. And above all, the newly generated siphons are proved to be controlled and never be unmarked. Hence, we need not to add conservative monitors for the newly generated siphons to avoid generating new unmarked siphons and the final supervisor is optimal.The generation of RG is a time and resource consuming task. It may take a week even a month but at last stop in the midway due to exhausted memory in the worst case. Hence, for the drawback of high computational complexity of generating RG, an algebra based method is proposed to enumerate the reachable states for a class of Petri nets-marked graphs. A marked graph can be divide into several blocks. First, a block is selected and the interconnected relation between it and its neighbouring block is determined. The two blocks constitute a new block. Repeat the process until there has no new block can be added and the final block is the marked graph. Then, successively calculate the number of reachable states of each block. Finally, the number of reachable states of the biggest block is the desired result. It can count the reachable states in a very short time, which can help one to predict whether it is possible to complete the generation of an RG under the current computational conditions.Finally, the application of the enumerative method is extended to a more compli-cated class of Petri nets-S3PR. First, a upper bound of reachable states is determined by combinatorics. Different from marked graphs, S3PR allows conflicts, which makes unreachable states arise. Hence, then we construct a subnet basing on siphons with two resources from resource circuits, decide the unreachable states of the subnet and obtain the number of unreachable states derived from the subnet by combinatorics. Finally, we can find the number of reachable states of the S3PR by removing the unreachable ones from the upper bound. Example calculations and analyses verify the effectiveness of the proposed method.