Bo Huang, Senior Member, IEEE, MengChu Zhou, Fellow, IEEE, Cong Wang, Member, IEEE,Abdullah Abusorrah, Senior Member, IEEE, and Yusuf Al-Turki, Senior Member, IEEE

Abstract—In this paper, a deadlock prevention policy for robotic manufacturing cells with uncontrollable and unobservable events is proposed based on a Petri net formalism. First, a Petri net for the deadlock control of such systems is defined. Its admissible markings and first-met inadmissible markings (FIMs)are introduced. Next, place invariants are designed via an integer linear program (ILP) to survive all admissible markings and prohibit all FIMs, keeping the underlying system from reaching deadlocks, livelocks, bad markings, and the markings that may evolve into them by firing uncontrollable transitions. ILP also ensures that the obtained deadlock-free supervisor does not observe any unobservable transition. In addition, the supervisor is guaranteed to be admissible and structurally minimal in terms of both control places and added arcs. The condition under which the supervisor is maximally permissive in behavior is given.Finally, experimental results with the proposed method and existing ones are given to show its effectiveness.

I. INTRODUCTION

ROBOTIC manufacturing cells play an important role in the manufacturing industry, including automobiles,semiconductors, etc. For instance, cluster tools and track systems are typical robotic manufacturing cells that perform core processes in semiconductor fabrication [1]. In such systems, available resources (such as machines and robots) are shared among concurrently running processes (such as vehicles and parts). The competition for the limited resources by different processes may lead to deadlocks where two or more processes are each indefinitely waiting for the other to release their acquired resources. Deadlocks can lead to unnecessary economic costs and sometimes catastrophic results.

To handle deadlocks in these systems, Petri nets (PNs) are widely used since they are suitable to graphically describe concurrency, conflict, and synchronization as well as conveniently detect behavioral properties of such systems[2]-[7]. Based on PNs, the theory of regions [8] is adopted in[9] to derive optimal (maximally permissive) and deadlockfree supervisors for plant nets where such supervisors exist.Some improvements are made in [10]-[12] to design optimal and structurally simple supervisors.

Many studies in the literature assume that all events in the systems are controllable and observable. However,controllability and observability are two properties that should never be taken for granted in practice since machine and sensor downtime is inevitable. To prevent deadlocks in the plant nets with uncontrollable transitions, an optimal(maximally permissive in behavior) supervisor synthesis method based on event separation instances is proposed in[13]. For a kind of ordinary nets with uncontrollable transitions, a bottom-up optimal supervisor synthesis approach is presented in [14] and a linear constraint transformation approach is given in [15]. For the nets with both uncontrollable and unobservable transitions, an approach that transforms a given generalized mutual exclusion constraint into an admissible one is proposed in [16]. Based on it, an efficient method about the equivalent transformation of a class of constraints is given in [17]. Focusing on LS3PR, which is a kind of ordinary PN, Qin et al. [18] develop a method to design supervisors by enforcing constraints on minimal siphons of the net model. In [19], an optimal supervisory control policy with polynomial complexity is proposed to handle a particular class of ordinary PNs with uncontrollable and unobservable transitions.

Besides behavioral permissiveness, structural complexity is also an important criterion that should be considered in the deadlock-free supervisor synthesis. Usually, a structurally minimal supervisor has the lowest implementation cost in the implementation of its control places and added arcs.Practically, control places are usually implemented by processing devices such as computers, microcontrollers, and programmable logic controllers, while added arcs are often implemented by sensors or actuators.

This paper proposes a deadlock prevention method to obtain admissible and structurally minimal supervisors for robotic manufacturing systems with uncontrollable and unobservable events. First, Petri nets and their admissible markings and first-met inadmissible markings (FIMs) are defined for the systems with uncontrollable and unobservable events. Next,place invariants (PIs) are designed in an integer linear program (ILP) to survive all admissible markings and forbid all FIMs to keep the system controllably running in the admissible markings. When compared with the existing work,the proposed method can deal with uncontrollable transitions,unobservable transitions, and structural minimization in the supervisor synthesis for generalized Petri nets. In addition, the obtained supervisor is guaranteed to be admissible in theory,i.e., all admissible markings survive in the controlled net. The condition under which the supervisor is maximally permissive in behavior is also given.

II. PETRI NETS WITH CONTROLLABILITY AND OBSERVABILITY

To handle deadlocks in manufacturing systems, many different classes of Petri nets [20] have been proposed, such as S3PR, ES3PR, LS3PR, ELS3PR, GLS3PR, S*PR, S4PR,S3PGR2, and S3PMR. The main differences among them are the number of resources required by an operation and the net structures of process subnets. In the following, their definitions are summarized and extended as in Definition 1 for systems with uncontrollable and unobservable events, which generalizes these Petri nets while preserving their design philosophy. For the basic definitions of Petri nets, please refer to [21].

VIII. CONCLUSIONS

This paper presents an ILP-based deadlock prevention method to design behaviorally admissible and structurally minimal supervisors for the robotic manufacturing cells with uncontrollable and unobservable events based on Petri nets.The method is not confined to ordinary Petri nets and its obtained supervisor is guaranteed to be deadlock free,admissible, and structurally minimal. The condition under which the supervisor is behaviorally optimal is given. In addition, the proposed method can be applied to the systems whose optimal supervisors do not exist and/or crucial transitions may be uncontrollable or unobservable.

A problem of reachability graph-based approaches is that,like those in [20], [25], it needs to generate an entire reachability graph and then solve ILP. Thus, how to efficiently generate reachability graphs and fast solve ILP is important. Future work should answer how to combine the proposed method with a structural analysis method [27] and apply redundancy elimination strategies [28] to ILP to further accelerate supervisor synthesis and seek new applications[29]-[34].