Liveness-enforcing Supervisor For Petri Nets With Uncontronllable And Unobservable Transitions

There exist many deadlock prevention policies to deal with fexible manufacturingsystems based on Petri nets, which have already been established. They are extensivelyused to solve deadlock problems in Petri nets. Most of them are developed underthe assumption that all the transitions are controllable and observable. However, theexistence of uncontrollable and unobservable transitions is a common phenomenon inreal world. Deadlock prevention policies for a plant under the assumption that all thetransitions are controllable and observable may not prevent the system from deadlocksin a Petri net with uncontrollable and unobservable transitions. This is due to the factthat a supervisor can neither control uncontrollable transitions nor observe unobservabletransitions. Consequently, the existing policies cannot be used to deal with the systemwith uncontrollable and unobservable transitions. Therefore, it is important to consideruncontrollable and unobservable transitions when we design monitors for a plant.The main results of this research are as follows：1. In the present researches of deadlock problems, most work focuses on the as-sumption that all the transitions are controllable and observable. Only a minorityof prevention policies involve uncontrollable and unobservable transitions. While forthe policies which take no account of the uncontrollable and unobservable transitions,there is no literature that gives a general method to discuss the applicability of theexisting deadlock prevention policies when there exist uncontrollable and unobservabletransitions. However, this thesis presents a method to evaluate the applicability of theexisting deadlock prevention policies in Petri nets with uncontrollable and unobserv-able transitions. In a controlled system derived from a deadlock prevention policy, analgorithm is developed to identify a set of critical controllable transitions and a set ofcritical observable transitions. According to these transitions, a sufcient condition isdeveloped to decide the applicability of a deadlock prevention policy when there existuncontrollable and unobservable transitions, that is, the policy is applicable if criticalcontrollable transitions are in fact controllable and critical observable transitions are infact observable. Combined with the existing policies, the evaluation method that wedeveloped can be used to design a supervisor for a Petri net with uncontrollable andunobservable transitions. Given a plant to be controlled, a deadlock prevention policyis applied to design a supervisor for it under the assumption that all the transitions arecontrollable and observable. Next, the evaluation method is adopted to decide whetherthe policy is applicable. If so, the supervisor derived from the policy can successfully prevent the system from deadlocks. If it is inapplicable, we have to try other deadlockprevention policies until an applicable one is found. In our research, the method canbe used to deal with diferent kinds of deadlock prevention policies for generalized Petrinets. There is no restriction to these deadlock prevention policies, in which the methodin this study can be applied.2. For a class of Petri nets in FMS, liveness constraints are represented as a setof inequalities via supervision based on place invariants (SBPI) for emptiable minimalsiphons. These constraints are frst enforced by considering unobservable transitions viamonitors. Next, for uncontrollable transitions that belong to the postset of monitors,a linear programming problem is formulated to identify a set of risky transitions anda set of fully secure transitions. It is legal that there are arcs from monitors to fullysecure transitions while it is illegal that there are arcs from monitors to risky transitions.Then, the output arcs of monitors are imposed to frst-met controllable transitions ofthe identifed risky transitions. A frst-met controllable transition of an uncontrollabletransition t is the frst controllable transition that t meets in an elementary path in thedirection from t to a source transition. Moreover, we propose a sufcient and necessarycondition to decide the existence of a monitor enforcing a liveness constraint. A newcontribution of this thesis lies in that unobservable and uncontrollable transitions aresuccessively considered.3. Elementary siphons have been extensively used to deal with deadlocks in Petrinets under the assumption that all the transitions are controllable and observable. Fora more general class of Petri nets in FMS, we develop an elementary siphon-based dead-lock prevention policy for the nets with uncontrollable and unobservable transitions.First, all emptiable minimal siphons are computed. They are divided into elementaryand dependent ones. The control depth variables of elementary siphons are assigned tobe one. The complementary set of an elementary siphon is frst expanded by consideringunobservable transitions. Monitors are added for these expanded ones. Then, the ex-panded complementary set is expanded again by considering uncontrollable transitions.Arcs rearrangement is made according to the expanded complementary set with un-controllable transitions. The reassignment of control depth variables is also made suchthat the dependent siphons can be controlled. Moreover, the controllability of elemen-tary and dependent siphons is analyzed. We show that the elementary and dependentsiphons are always marked in the controlled system derived from the proposed methodwhen there are uncontrollable and unobservable transitions.