ABSTRACT
The theory of regions is an eective approach that can derive a maximally permissive supervisor for a Petri net model by adding monitors if such a supervisor exists (Ghaari et al., 2003). Thus it has been widely used for deadlock prevention (Li et al., 2008; Uzam, 2002). However, its computation is rather inecient because it requires the reachability graph of a net, which always suers from the state explosion problem. Furthermore, its monitors are designed by solving a large number of sets of inequalities, which suers from the computational complexity problem. Uzam and Zhou (2006) develop an iterative approach for the deadlock control in AMSs. In their study, a reachability graph is classified into a deadlockzone including deadlock and critical bad markings that inevitably lead to deadlocks, and a live-zone representing the legal markings in the reachability graph. An FBM
the graph at each and then a control place is designed to prevent the FBM from being reached via constructing a PI of a Petri net by using a well-established invariant-based control method to compute a control place for the PI (Lautenbach and Ridder, 1994; Yamalidou et al., 1996). Although the method proposed in (Uzam and Zhou, 2006) is easy to use and intuitive, it cannot guarantee the optimality in general for an AMS that is modeled by Petri nets. Piroddi et al. (2008) develop a selective siphon control approach that proceeds with an iterative way. At each iteration, the relations between uncontrolled siphons and critical markings (at which at least one siphon is empty) are identified and a set of siphons is selected by solving a set covering problem. Once the selected siphons are controlled, all the critical markings are accordingly forbidden, which indicates that all the uncontrolled siphons are controlled. The selective siphon technique can provide a structurally small-sized supervisor. Piroddi et al. (2009) provide an improved method to avoid a full siphon enumeration and greatly reduce the overall computational time. Although for every example presented by Piroddi et al. (2008, 2009), they can find a maximally permissive supervisor, it is a pity that their policy is not proven to be maximally permissive in theory.
