Structural Analysis Of And Supervisor Design For Petri Nets Of Automated Manufacturing Systems

Analysis and control of deadlocks play an important role in the design and op-eration of automated manufacturing systems (AMS). Partially, locally or completely crippled systems caused by deadlocks are a highly undesirable situation. In many cases, they not only reduce productivity, but also cause fatal economic cost such as in semi-conductor fabrication systems, and catastrophic results such as in manipulation systems of nuclear power station. Along with the increasing automatization and complexity, the description, analysis, control, and resolution of deadlocks in AMS have been the topics of high interest. Petri nets have been widely used for modeling, analysis, and dead-lock control of AMS for their compact and graphical representation. Over the last two decades, a number of deadlock control policies based on Petri nets have been proposed. Traditionally, a deadlock control policy can be evaluated by three performance criteria: structural complexity, behavioral permissiveness, and computational complexity. From a technical perspective, most of the control policies resolving deadlocks are developed via state space analysis or structural analysis of Petri nets. Generally, deadlock control policies based on the former can approach the maximal permissive behavior, but may encounter highly computational complexity and a state explosion problem. Deadlock control policies based on the latter can avoid a state explosion problem successfully, but cannot lead to the maximal or near maximal permissive behavior of the systems in most cases. Siphons, as a special structural object of a Petri net, are closely interrelated with deadlocks. Deadlock control theory based on siphon is not an apple-pie grown-up theory. For ordinary Petri nets, the current theory is fairly mature, while for generalized Petri nets, it is presently at an early stage.On the other hand, in recent years, most of deadlock control policies based on Petri nets for AMS have had a premise that the resources in the systems under consideration are reliable. Actually, resource failures are inevitable in most AMS, which may also cause processes to halt. Therefore, it is a necessary requirement to develop an effec-tive and robust deadlock control policy by considering unreliable resources. Currently, the technology to design robust liveness-enforcing supervisors for AMS with unreliable resources is very much lacking.This thesis aims to tackle the limitations mentioned above and the main results of this research are presented as follows.Firstly, for system of sequential systems with shared resources (S4R), this thesis reviews the concepts of max and max'-controllability conditions of siphons and their limitations. Based on mixed integer programming (MIP), the concept of max"-marked siphons is defined, and then the concept of max"-controlled siphons is formulated. We conclude that an S4R is live if all its siphons are max"-controlled. Compared with the existing ones, the proposed one is more general.Secondly, for S4R, this thesis analyzes the limitation of the current MIP that can test their liveness based on deadly marked siphons (DMS). The concept of extended deadly marked siphons (EDMS) is defined on the basis of max"-controllability condition of siphons. Accordingly, a more general MIP testing approach that can detect the minimal EDMS that cause deadlocks or livelocks in S4R is presented to lay foundations for further analysis and control of deadlocks. We conclude that an S4R is live if there is no feasible solution to this new MIP test. Compared with the existing methods, the proposed one is more general and powerful.Thirdly, this thesis proposes a class of manufacturing-oriented Petri nets, M-nets for short, with strong modeling capability. Combining control theory based on siphons and theory of regions, we develop a deadlock prevention method that makes a good trade-off between optimality and computational tractability for M-nets. The theory of regions guides our efforts towards the development of near-optimal solutions for deadlock prevention. Given a plant net, a minimal initial marking is first decided by structural analysis, and an optimal live controlled system is found. Then, a set of inequality constraints is derived with respect to the markings of monitors and the places in the model such that no siphon can be insufficiently marked. A method is proposed to identify the redundancy condition for a constraint. For a new initial marking of the plant net, a deadlock-free controlled system can be obtained by regulating the markings of the monitors such that the inequality constraints are satisfied, without changing the structure of the controlled system. The near-optimal performance of a controlled net system can be obtained via the proposed method.At last, this thesis designs robust liveness-enforcing supervisors for AMS with unre-liable resources in real-world. For systems of simple sequential processes with resources (S3PR), in the first place, a monitor is added for each emptiable strict minimal siphon (SMS) to obtain a liveness-enforcing supervisor. In the second place, to improve the robustness of the supervisor, we add recovery subnets, normal arcs, and inhibitor arcs to the system obtained by the first stage such that liveness is still preserved. The proposed method bridges the gap between existing Petri net control policies and their application to real systems with unreliable resources.This research is of significance both in theory and in practice to the supervisory control of AMS in a Petri net formalism.