Research On Online Collision-free Route-planning Algorithm For Agv In Large Automated Storage And Retrieval Systems

The Large Automated Storage and Retrieval Systems(LAS/RSes)require a small number of people to complete the transportation of goods by using Automated Guide Vehicles(AGVs).AGV route planning is a multi-objective combination optimization problem,the requirements are as follows:(1)the computation speed of the algorithm is fast;(2)the distance of routes are shortest;(3)the travel time is minimized time;(4)the energy cost should also be minimized.In multi-AGV scenarios,we need to guarantee no collisions between AGVs.With the rapid development of LAS/RSes,the efficiency of route planning becomes the bottleneck to restrict the development of warehouse systems.The main contents of this paper are as follows:1.Modeling the storage environment is the precondition of route planning,and the traditional storage environment modeling method is as follows:the warehouse is measured manually.Then we summary the results and classify the environmental functional areas according to the requirements(e.g.,size of AGV/shelf).But this method needs a lot of human/material resources.In this paper,an automatic environments modeling method based on computer vision is proposed.First,a common monocular camera is used to collect ground images;Then,the standard rectangular image of storage environment was obtained via perspective correction;The approximate range of the storage area is drawn and its outer rectangle is calculated;Second,according to the size of AGV/shelf,the size of workstations are calculated,and the storage environment is rasterized.Finally,finishing modeling the warehouse,i.e.,establishing the warehouse environmental map.The effectiveness of the proposed method is verified by simulation examples.2.AGV scheduling and route planning are both belonging to the route optimization problem.They are inseparable and determine the efficiency of LAS/RSes.Since the common scheduling algorithms(i.e.,k-NN-based and Manhattan distance-based algorithms)are not suitable for LAS/RSes,this paper proposes an AGV scheduling algorithm to satisfy the characteristics of the LAS/RSes.Firstly,the infeasibility of the above two scheduling algorithms in LAS/RSes are compared and analyzed.Then,the classical path-finding algorithm(Dijkstra’s algorithm)is improved by adding turning weights and applied to AGV scheduling problems.Simulations show that the proposed scheduling algorithm based on the improved Dijkstra’algorithm can determine the AGV can reach the target as soon as possible and compute the shortest route in the obstacle environments.3.For the single-AGV route-planning problem,this paper proposes a route-planning method by combining Dijkstra’s algorithm and Reinforcement Learning(RL):First,the adjacency matrix of Dijkstra’s algorithm and the Reward matrix of Q-learning algorithm are combined to establish the Adjacency-Reward matrix(A-R).The iterative efficiency of Q-learning algorithm is improved by introducing the adjacency relationship between nodes;Second,according to the start/goal nodes of AGVs,a low dimensional A-R matrix is established to further improve the efficiency of route search by reducing the number of nodes in the environment.Third,the distance-time shortest route is selected by calculating the angular deviation between AGV and feasible path.4.The process of establishing A-R matrix is tedious and it has low scalability of the proposed improved Q-learning algorithm.This paper proposes a single-AGV route-planning method based on Dynamic Programming(DP)and Monte Carlo Tree Search(MCTS)---Region Segmentation DP-MCTS algorithm.Also,the classical MCTS algorithm lacks selection mechanism in the process of node search,and cannot balance exploration and utilization.Its“blind-search”mechanism makes the algorithm inefficient.Based on this problem,the following improvements are proposed:First,leading the expansion of search tree towards the goal node of the AGV to increase the single search speed;Second,each node expansion is evaluated to avoid the waste of time in the process of back propagation;Third,combining the idea of multi-stage optimization problem of Dynamic Programming(DP)with the improved MCTS algorithm to further improve the efficiency of single AGV route planning.The computational complexity of the proposed algorithm is compared with existing algorithms,and the results are as follows:As for LAS/RSes with n nodes,the complexity of the common algorithm is O(n~2),while the complexity of the proposed algorithm is O(nlog(n)).Simulation results show that this method can shorten the AGV route-planning time,reduce the energy cost of LAS/RSes,and improve the real-time performance of the whole storage systems.5.When multiple AGVs drive simultaneously,collisions may occur,and in order to address the problem that the traditional time-window method cannot adapt to the detection accuracy according to the types of conflicts,a multi-AGV route conflict detection method based on gene sequencing is proposed:First,the nodes and sections in LAS/RSes are number by environment formatting;Second,according to the formatting results,the path and time score matrices of AGV are established;Third,trace back the score matrix of path and time to get the conflict area.6.The traditional multi-AGV route-planning method can not satisfy the requirements of multi-objective optimization and ignores the problems of system throughput and energy cost.An adaptive and dynamic multi-AGV collision-free route-planning method based on the conflict critical section is proposed,which solves the problem that the system throughput and energy cost are not considered:First,determine the conflict resolution strategy adopted by the AGV according to the priority of the AGV(i.e.,wait for a period of time before the critical section of the conflict or directly select the alternative route),and determine the waiting time in real time according to the position of the task goal node;Second,when there is an emergency(such as a sudden appearance of a person or a sudden drop of goods on the route of AGV),it can determine whether the AGV needs to wait in front of the obstacle adaptively;Third,when a new transportation task is issued,LAS/RSes real-time scheduling can make the idle AGV reach the task starting point fastest,reduce the task waiting time of LAS/RSes and improve the dynamics of LAS/RSes.The simulation examples demonstrate that the proposed method can be used in LAS/RSes multi-AGV route planning,and can plan the collision-free distance-time shortest route for AGV,solve the problem of potential and temporary path conflicts caused by multiple AGVs driving at the same time,effectively reduce the energy consumption of LAS/RSes,and improve the real-time performance of the whole LAS/RSes.