An algorithm is proposed to equivalently transform original linear constraints on Petri nets, where the uncontrollable subnets are forward-concurrent free nets, into admissible ones. Consequently, this algorithm can be used to design both efficient and optimal supervisors for enforcing linear constraints on Petri nets since the problem on how to enforce admissible constraints has been well solved. Further, the supervisor synthesis procedure is presented using this algorithm. Lastly, it is illustrated by an example where an optimal supervisor is designed for a flexible manufacturing system.
TopIntroduction
A discrete Event System (DES) is a system in which events drive state transitions, and therefore, it is suitable for modeling the logic aspects of any system. An event often involves the occupation or release of some resource, such as a machine, buffer, or tool in flexible Manufacturing Systems (FMS); a piece of track in railway systems; and a channel in network-communication systems. With an improvement in the resource efficiency, more forbidden states, caused by the scarcity of resources, might arise. Examples of forbidden states are deadlocks, collisions between trains, and data loss because of buffer overflow. It is necessary to prevent a system from reaching such forbidden states in order to avoid potential losses, such as human ones. Forbidden-state-avoidance control is difficult because real DESs such as FMSs, and underground systems, are often large and complex and they consist of numerous subsystems. Furthermore, the total number of states is the combination of the numbers of the states of the subsystems. Therefore, the design, verification, and validation of control programs are very difficult, time-consuming, and laborious in the absence of formal methods, simulation tools and verification tools. In particular, a DES control theory is required to guarantee that a closed-loop system is maximally permissive (optimal) and free of deadlocks.
Petri nets provide a formal tool for developing the DES control theory. Accordingly, the control specification is formalized as a logic expression of linear constraints, also called generalized-mutual-exclusion-constraints by Giua, DiCesare, and Silva (1992). In recent years, researchers have realized good progress in enforcing linear constraints on Petri nets (Holloway, Krogh, & Giua, 1997; Iordache, & Antsaklis, 2006).
For a conjunction of constraints on Petri nets in which each transition is controllable, Giua, DiCesare, and Silva (1992), and Yamalidou, Moody, Lemmon and Moody (1996) proposed an optimal supervisor synthesis method using monitor places. For a disjunction of constraints on Petri nets without any uncontrollable transition, Moody and Antsaklis (2000) proposed a structural supervisor synthesis method and Luo, Wu, Su and Chu (2009) presented a mapping supervisor synthesis method.
However, the computational complexity is greatly increased because of the presence of uncontrollable transitions, since it becomes necessary to restrict the system’s behavior within a subset of the legal-marking set, called the admissible-marking set. Thus, obtaining the criterion for admissible markings is the precondition for designing the optimal supervisor. Depending on the method used to find this criterion, the supervisor-synthesis methods reported thus far are different.
Linear algebra approach based on the incidence matrix: Li and Wonham (1994) noted that the criterion for admissible markings is a nonlinear programming with an unstructured feasible set, and this is reduced to a linear integer programming for acyclic nets. Using the concept of S-decrease, Chen (2000) obtained a sufficient condition for admissible markings. Moody and Antsaklis (2000) introduced an admissible linear constraint whose admissible-marking set is equal to its legal-marking set. Hence, the implementation of such admissible constraints is as easy as a control problem where each transition is controllable and observable. Further, they proposed an algorithm for transforming an original constraint into an admissible one. However, since the new constraint may not be the necessary condition for admissible markings, the supervisor may not be optimal. Iordache and Antsaklis (2003) later extended this method to enforce constraints containing firing-vector terms and Parikh-vector terms. Basile, Chiacchio and Giua (2006) improved Moody and Antsaklis’s method and provided an algorithm for designing suboptimal supervisors.
Reachability-graph-based method: Ghaffari, Rezg, and Xie (2003a) identified admissible markings using reachability graphs. Uzam (2004) introduced net reductions within this method.