Path Planning Methods for Four-Way Shuttles in Dynamic Environments Based on A* and CBS Algorithms

Abstract

In the four-way shuttle system, the efficiency of path planning directly affects the overall effectiveness of logistics and warehousing operations. Traditional path planning methods for multiple four-way shuttles do not take into account the fact that the map status will change as the inbound and outbound tasks are completed. To address this issue, a path planning algorithm for dynamic environments based on an improved Conflict-Based Search (CBS) mechanism is proposed. Firstly, by introducing turning constraints and a node expansion strategy, the A* algorithm is improved, reducing the number of turns and optimizing the node expansion process. Secondly, based on the improved A* algorithm, a path planning algorithm for dynamic environments based on CBS is designed. This algorithm adopts the inbound/outbound task priority strategy and the nearby-task priority strategy to resolve conflicts. It effectively manages the changes in the map status by establishing and maintaining a “ChangeList” and revises the path set of the four-way shuttles. Based on the layout of the intelligent vertical warehouse with four-way shuttles of a certain enterprise, simulation experiments were carried out using a rasterized map. The algorithm was compared with the DCBS-PFM and RRT-A algorithms, verifying the effectiveness and superiority of the algorithm.

Keywords

• four-way shuttle
• path planning
• A* algorithm
• CBS algorithm