Research On Deadlock Prevention Method For Automated Guided Vehicle Systems By Using Colored Resource-oriented Petri Nets

Automated Guided Vehicle scheduling systems are one of the most important components in the automated manufacturing systems.Deadlocks,leading to standstill of some processes or whole systems,must be fully avoided in the AGV scheduling systems.Colored Resourceoriented Petri net(CROPN)-based methods for deadlock resolution for AGV scheduling systems are widely used and studied.However,their disadvantages lie in that they will suffer from computational complexity problems.To cope with these problems mentioned above,this paper improves the CROPN-based methods such that the computational complexity is reduced while achieving the same control purpose.To achieve the control purpose,one must first design a deadlock detection method to check the deadlock structures in the system for all reachable states,leading to a set of deadlock states called deadlock state set.Then,one must design a deadlock avoidance method to realize the deadlock-free constraints from the set of deadlock states obtained by the detection method,thus makes the system deadlock-free.To reduce the computation complexity of deadlock detection methods,based on the concept of deadlock structure that we call knots,this paper defines a Deadlock marking Structure(DMS)-based deadlock detection method.Moreover,to reduce the computation complexity of deadlock avoidance methods,a colored capacity-based deadlock avoidance method is then proposed.Compared with the current methods,the novel method presented in this paper requests much less computational complexity for large-scale AGV scheduling systems.The main content of this paper is as follows:(1)DMS-based deadlock detection methodFirstly,the concept of DMSs is given.Based on this structure,sufficient and necessary condition for the detection of deadlocks at a given marking in interactive subnets are proposed.By revealing the relationships among places?transitions?markings and the identifying ofthe process-enabled transitions,the binary variables and the corresponding linear constraints are developed,resulting in a mixedinteger programming(MIP)approach to determine the maximal nonempty set DMS in an interactive subnet at a given marking.Finally,based on the above results,a deadlock-detection method is developed.The proposed deadlock-detection method needs a much less computational complexity than those depending on structure knot,and is more suitable for large-scale AGV scheduling systems.A classical CROPN cell example is used to illustrate the proposed method.(2)Colored capacity-based deadlock avoidance methodFirstly,the formal concept of colored capacity in a CROPN is given.Based on this concept,the new execution rule of the transitions is proposed.Then,a procedure is developed such that the colored capacity function of each place in a CROPN can be obtained.By colored capacity function,all control policies that are used to forbid illegal markings in interactive subnets in a CROPN are realized by using the new execution rule such that the CROPN is made deadlock-free.The proposed deadlock-avoidance method needs a much smaller computational complexity than those depending on control place and arc,and is more suitable for large-scale AGV scheduling systems.A classical CROPN example is used to illustrate the proposed method.