Clustered Reverse Resumable A* Algorithm for Warehouse Robot Pathfinding

Robots are widely used to carry goods in automated warehouses. Planning collision-free paths for multiple robots which are continuously given new goals is called Lifelong Multi-Agent Pathfinding. In a lifelong environment, conflicts may emerge among the robots, and continuous replanning is needed. We propose, develop, implement, and evaluate the novel approach called the Clustered Reverse Resumable A* (CRRA*) algorithm to enhance the continuous computation of the shortest path from the changing position of a robot to its goal. The Priority Inheritance with Backtracking (PIBT) algorithm is the currently known most efficient algorithm to handle the pathfinding of thousands of robots in a warehouse. The PIBT algorithm requires that in each step each robot evaluates the distances from its surrounding positions to its goal; therefore, we integrate the CRRA* algorithm with the PIBT algorithm to evaluate CRRA*. The evaluation results show that the CRRA* leads to a significant reduction in computation time, especially in larger warehouses where the obstacles form well-separated spaces. At the same time, the degradation in solution quality is minimal. The CRRA* algorithm is more efficient in larger warehouses than the plain Reverse Resumable A* (RRA*) algorithm. The faster computation of slightly suboptimal paths can be useful in many practical applications, especially in situations where real-time planning is more important than finding the optimal paths. CRRA* can also be used as a heuristic in any multi-agent pathfinding solution to obtain a faster, nearly accurate heuristic.