Research On Multi-AGV Path Planning For Logistics Sorting Based On CBS Algorithm

The introduction of “Internet plus” and “Industry 4.0” has driven the development of traditional manufacturing to intelligent manufacturing.Various logistics companies have introduced Automated Guided Vehicles(AGVs)to replace the traditional “conveyor belt+ labor” to achieve fully automatic intelligent sorting.The use of AGV for sorting parcels has led to multi-AGV path planning problems.It is necessary to plan non-conflicting paths for all AGVs in the environment and to improve sorting efficiency as much as possible.This is just the problem to be studied in this thesis.We mainly completed the following aspects for this problem:According to the application characteristic,the existing multi-agent path finding model is choosen as the problem model,the optimization goal of this thesis is to minimize the total cost of AGV paths.Under this model,two parallel algorithms based on CBS algorithm: PCBS and its enhanced version EPCBS are proposed in this thesis.Parallel algorithms could use multiple thread to solve problems theoretically,so as to better leverage the computing power in the real envrionment.By registering the cost value of the expanding nodes,the algorithms can conditionally select the node to be extended,and finally obtain the approximate optimal solution of the problem.Through the randomized conflict selection strategy,the probability of finding the solution between the nodes is approximately mutual independent,substantially enhancing the efficiency of parallel algorithms.Considering the dynamic characteristic of the logistics sorting scenario,a dynamic multi-agent path finding model is proposed in this thesis,which considers the number of agents executing tasks in the environment.In this thesis,an incremental search algorithm LPCBS is designed to solve this dynamic problem and its optimality is proved.Incremental search could plan the paths of the “new arrival” agents and quickly adjust the paths of the “on the way” agents by reusing the constraint tree generated in the previous search process of CBS.Further more,we give a new constraint tree implementation in LPCBS,which effectively saves the memory needed in the search process.Finally,for the proposed parallel algorithms,we make comparison of the proposed parallel algorithms with the serial algorithms from different aspects,under different environment and with different agent size.It can be found that with the increase of the number of agents,the increment extent of the search time for parallel algorithm is smaller than the serial algorithms,and its searching efficiency is significantly enhanced when using multiple threads.To validate our design of the incremental search algorithm LPCBS,we simulated a logistics sorting scenario.By simulating multiple agents to perform sorting tasks in the environment,experiment results show that LPCBS is more efficient than CBS in solving dynamic problems from different aspects,and the quality of the solution has obvious advantages over the typical distributed solver HCA*.