Optimal deadlock avoidance Petri net supervisors for automated manufacturing systems

Deadlock avoidance problems are investigated for automated manufacturing systems with flexible routings. Based on the Petri net models of the systems, this paper proposes, for the first time, the concept of perfect maximal resourcetransition circuits and their saturated states. The concept facilitates the development of system liveness characterization and deadlock avoidance Petri net supervisors. Deadlock is characterized as some perfect maximal resource-transition circuits reaching their saturated states. For a large class of manufacturing systems, which do not contain center resources, the optimal deadlock avoidance Petri net supervisors are presented. For a general manufacturing system, a method is proposed for reducing the system Petri net model so that the reduced model does not contain center resources and, hence, has optimal deadlock avoidance Petri net supervisor. The controlled reduced Petri net model can then be used as the liveness supervisor of the system.

A Deadlock-Avoidance Dispatching Method for Multiple-Load AGVs Based Transportation System

In recent years,multiple-load automatic guided vehicle(AGV)is increasingly used in the logistics transportation fields,owing to the advantages of smaller fleet size and fewer occurrences of traffic congestion.However,one main challenge lies in the deadlock-avoidance for the dispatching process of a multiple-load AGV system.To prevent the system from falling into a deadlock,a strategy of keeping the number of jobs in the system(NJIS)at a low level is adopted in most existing literatures.It is noteworthy that a low-level NJIS will make the processing machine easier to be starved,thereby reducing the system efficiency unavoidably.The motivation of the paper is to develop a deadlock-avoidance dispatching method for a multiple-load AGV system operating at a high NJIS level.Firstly,the deadlock-avoidance dispatching method is devised by incorporating a deadlock-avoidance strategy into a dispatching procedure that contains four sub-problems.In this strategy,critical tasks are recognized according to the status of workstation buffers,and then temporarily forbidden to avoid potential deadlocks.Secondly,three multiattribute dispatching rules are designed for system efficiency,where both the traveling distance and the buffer status are taken into account.Finally,a simulation system is developed to evaluate the performance of the proposed deadlock-avoidance strategy and dispatching rules at different NJIS levels.The experimental results demonstrate that our deadlock-avoidance dispatching method can improve the system efficiency at a high NJIS level and the adaptability to various system settings,while still avoiding potential deadlocks.

Deadlock-free dynamic resource assignment in multi-robot systems with multiple missions:application in wireless sensor networks

In unstructured environments, dynamic resource assignment is required for effective cooperation of robot teams. In some scenarios, robots are in charge of executing multiple missions simultaneously. This creates risks of deadlock due to the presence of shared resources among various missions. The main contribution of this paper is the development of a novel approach that combines the one-step look-ahead deadlock avoidance policy with dynamic resource assignment. The dynamicresource assignment is achieved using greedy resource assignment for multi-mission robot teams in the framework of a matrix-based discrete event controller. Simulation results are presented in MATLAB to discuss in detail the proposed control strategy. The paper also discusses the toolkit developed in LabVIEW which is used to implement this control framework using a suitable example.

Optimization of Waterway with Multiple Locks and Canals by Integration of Petri Net and Genetic Algorithm

This paper presents the possibilities of job optimization in waterway with multiple locks and canals, in order to increase the system productivity. Safe navigation in such complex waterway system is very demanding. Some of the problems that need to be solved are： How to control traffic in a way that vessels move in opposite directions; How to resolve possible conflicts in case that more vessels try to acquire particular lock at the same time; How to avoid possible deadlocks; How to ensure the vessel passage in the shortest possible time？ It is necessary to apply adequate control policy to avoid deadlocks and blocks the vessels＇ moving only in the case of dangerous situation. The motion of vessels can be described as the set of discrete events and states. Herein we propose deadlock avoidance algorithm for complex waterway system with multiple key resources and we use multiple re-entrant flowlines class of Petri net （MRF^PN）. The solution represents deadlock prevention supervisor in a sense that vessels are stopped only in a case of immediate dangerous situation in dense traffic. The goal of this paper is to find optimal, conflict and deadlock free job schedule in CWS. In this sense, the authors developed the algorithm which integrates MRF^PN with a genetic algorithm. The algorithm deals with multi-constrained scheduling problem with shared resources. The final goals are minimization the total travel time of vessels through the waterway system.

A novel motion coordination method for variable-sized multi-mobile robots

Multi-mobile robot systems(MMRSs)are widely used for transportation in industrial scenes such as manufacturing and warehousing.In an MMRS,motion coordination is important as collisions and deadlocks may lead to losses or system stagnation.However,in some scenarios,robot sizes are different when loaded and unloaded,which means that the robots are variable-sized,making motion coordination more difficult.The methods based on zone control need to first divide the environment into disjoint zones,and then allocate the zones statically or dynamically for motion coordination.The zone-control-based methods are not accurate enough for variable-sized multi-mobile robots and reduce the efficiency of the system.This paper describes a motion coordination method based on glued nodes,which can dynamically avoid collisions and deadlocks according to the roadmap structure and the real-time paths of robots.Dynamic features make this method directly applicable to various scenarios,instead of dividing a roadmap into disjoint zones.The proposed method has been applied to many industrial projects,and this study is based on some manufacturing projects for experiments.Theoretical analysis and experimental results show that the proposed algorithm is effective and efficient.