Chinese Journal of Computers   Full Text
Title	Combined Supervisor Synthesis for a Class of Forbidden State Problems in Petri Nets
Authors	LUO Ji-Liang
Address	(College of Information Science and Engineering, Huaqiao University, Quanzhou, Fujian 362021)
Year	2008
Issue	No.2(291—298)
Abstract &   Background	Abstract A class of forbidden state problems in which the influence uncontrollable subnets are state machines for the given general mutual exclusion constraint(GMEC) on plant Petri nets is addressed. A method of designing the observers is proposed, and an algorithm of synthesizing the optimal supervisors is obtained based on the observers. It makes it possible to transform a GMEC with multi forbidden places into that with only one forbidden place and to reduce the control problem with uncontrolled transitions into that without any uncontrolled transition. The computational complexity of the supervisor synthesis is then efficiently reduced. A metro line supervisory example illustrates the theoretic results. keywords Petri nets； discrete event systems; supervisory control; forbidden states; combined supervisor background The supervisory control theory was introduced in as a conceptual framework for studying the supervision of discrete event systems (DESs). Its objective is to synthesize a supervisor blocking some events to realize the given specified controlled behavior of the controlled system. Petri nets are a common formalism for the supervisor synthesis for DESs. And Petri nets have been successfully proposed as modeling formalism for DESs control as an alternative to controlled automata.The generalized mutual exclusion constraint(GMEC) is introduced to express a set of forbidden states for a Petri net in which conflicts caused by restricted resource occur, such as the collisions of the trains in metro lines, the collisions of the pallets in manufacturing systems, resource conflicts, deadlocks, sequencing specification, and buffer overflow and operation rules in manufacturing systems. This paper studies a class of Petri net control problems to enforce a conjunction of GMECs on State Machines with uncontrollable transitions, and proposes a method to design the optimal combined supervisor. For this kind of problems, there have been methods to design the structure supervisor and the mapping supervisor. For Petri nets with uncontrollable transitions, there is not always the optimal structural supervisor, and the computation complexity of mapping supervisors is high and it is difficult to analyze the closed systems under mapping supervisors utilizing Petri net theory. For this class of control problems, the optimal combined supervisor synthesis method is proposed. The observer net is designed, and then, the optimal control policy is calculated based on the states of the observer net. The observer net makes it possible to transform a GMEC with multi forbidden places into that with only one forbidden place and to reduce the control problem with uncontrolled transitions into that without any uncontrolled transition. The computational complexity of the supervisor synthesis is then efficiently reduced. This research is supported by the National Natural Science Foundation of China(60503027), Fujian Provincial Youth Project(2006F3087), and the Natural Science Foundation of Fujian Province of China(A0710010). These projects are to develop the Petri net control theory which can be utilized to solve the conflict problems such as the collisions of the trains in metro lines, the collisions of the pallets in a manufacturing systems, resource conflicts, deadlocks, sequencing specification, and buffer overflow and operation rules in manufacturing systems. In the past research, the authors have proposed a series of supervisor synthesis methods which include the combined supervisor for Marked Graphs, the optimal mapping supervisor for forward synchronization free and forward conflict free nets, the optimal mapping supervisor for forward synchronization free and backward conflict free nets, the optimal mapping supervisor for forward concurrent free nets and so on. The theoretic results of this paper is a part of the theory that the authors with develop to design the combined supervisor for Petri nets with uncontrollable transitions. And it may be the base of this theory.