Research On Path Finding Algorithm Of Four-way Shuttle System Based On Conflict Based Search

With the development of e-commerce,logistics and automation,automated logistics equipment is under a rapid iterative updating stage.As a new type of automated warehousing system proposed in recent years,four-way shuttle system has gradually become a popular automated warehousing solution because of its strong flexibility,cross-aisle and cross-tier operations.The four-way shuttle can move in four directions along the fixed guideway,so the conflict-free paths for multiple four-way shuttles in the same tier become particularly important.Aimed at the path finding problem of the four-way shuttle system,this paper puts forward a path finding algorithm based on the improved conflict-based search to find a conflict-free path solution for the four-way shuttles,which is of great significance to the distribution center and warehousing system.Firstly,the composition structure of the four-way shuttle system and the operation process of inbound/outbound tasks are separately introduced.It lays a theoretical foundation for the establishment of the path finding model of the four-way shuttle system.Conflict based search(CBS)and A*algorithms are introduced as the solution framework of the four-way shuttle system path finding problem.Secondly,the conflict-free path finding model of four-way shuttle system is established with the goal of minimizing the total task finished time.And the improved CBS based on A*algorithm is proposed to find the conflict-free path for each four-way shuttle and calculate the total task finished time.The improved A*algorithm with turning strategy and extended node selection strategy is proposed to find the optimal path for each four-way shuttle as the low-level search algorithm.The dynamic potential search is used to improve the high-level search of CBS to solve the conflict between two four-way shuttles.Experiments verify the effectiveness and search efficiency of the improved algorithm.Finally,by analyzing the characteristics of the target location of the four-way shuttle inbound/outbound tasks and considering the kinematic constraints of the four-way shuttle,an improved safe interval path planning algorithm based on speed and multi-label is designed as the low-level search algorithm.A multi-shuttle collision detection mechanism based on speed and size of four-way shuttle is proposed for conflict detection of the high-level search,and the priority strategy is used to optimize high-level search to constrain the splitting of constraint tree nodes.The experimental results verify the effectiveness of the algorithm,which can be used as a reference for the operation of the actual four-way shuttle system.