CROTPN Based Collision-free And Deadlock-free Path Planning For AGV In Logistics Center

Efficient path planning of automated guided vehicle(AGV)is significant for industrial scenarios such as smart warehouse,unmanned wharf and automated factories.In particular,in recent years,with the development of e-commerce,online shopping has become more and more popular.In order to accelerate the delivery process for consumers,the logistic center needs to intelligently sort those packages with high efficiency,which can be achieved through multiple AGV rather than artificially.which usually has tens of thousands of express packages to sort and transport every day.In order to enhance the efficiency of sorting,multiple AGV have been used to transport as many express packages as possible in a given time.However,there may exist collisions and deadlocks when two or more AGV are trying to pass through a shared area at the same time.This thesis studies the collision-free and deadlock-free path planning problem of multi-AGV automatic sorting in logistics center.For the given plant layout,our goal is to transport and sort as many packages as possible during the system operation and use as few AGV as possible.To solve the problem of multi-AGV collision-free and deadlock-free path planning in logistics center,the main work of this thesis is as follows:This thesis first analyzes and summarizes the advantages and disadvantages of the existing multi-AGV path planning method,and based on the existing multi-AGV path planning research,it studies the layout characteristics of the existing sorting center scenario.Based on the graph theory model,the layout of the scenario is abstracted into an undirected graph.In the theory of undirected graphs,the path planning problem of the multi-AGV automatic sorting system is described in detail.In this thesis,we study collision-free and deadlock-free path planning of multiple AGV with the objective of minimizing the makespan,that is,the maximum time of the AGV to finish a round of delivery.For AGV collision-free path planning problems with a small number of AGV,this thesis proposes a heuristic search algorithm and coordination algorithm which can quickly estimate the direction of the shortest path.Collisions may occur when multiple AGV search for paths.This thesis avoids path collsion with other AGV by using a coordination algorithm to allow AGV to wait and turn.For complex scenatios with a large number of AGV in the collision-free path planning problem,this thesis first proposes a candidate path generation algorithm to generate several paths for each AGV,from which a combination of the paths is selected based on optimal path combination selection(OPCS)algorithm,such that the collisions and deadlocks can be minimized.Then,we construct a colored resource-oriented timed Petri net(CROTPN)model for dynamic changing AGV routes after slicing the scheduling period into timeslots.Based on this model,various deadlocks and collisions are analyzed and solved,such as node collision,cycle,cycle chain,interactive cycle chain and circuit.Through SlotControl policy,All kinds of collisions and deadlocks can be effectively avoided.Our experiment is simulated based on CPNtools.Experiment results show that the method based on CROTPN model can achieve a high sorting throughput using the least AGV.