Multi-AGV pathfinding for automatic warehouse applications

Optimal coordination and scheduling of multiple automatic guided vehicles (AGVs) is one of the key issues of automatic warehouse systems. However, the existing algorithms perform unsatisfyingly on the large-scale number of agents and the map size due to the excessive time required for optimal scheduling. This paper proposes an alternate iterative conflict-based search (AICBS) algorithm. In this algorithm, path extension and conflict resolution are performed alternately, that is, checking whether there is a conflict at each step of the extension, and if there is a conflict modifying the routes of the two conflicting agents to avoid invalid plans caused by the path extension after the conflict, so as to save search time. In addition, the algorithm also reduces the time cost of conflict resolution by fixing the priority of agents on the vertexes and edges of the graph which is constructed from the map of the warehouse. The algorithm can be implemented on a general topology map, not only on a raster map, so that the time cost can be further reduced by compressing the map size. We compare the proposed algorithm with the conflict-based search algorithm in a raster map and apply it to a general topology map. Experimental results show that the algorithm can effectively reduce the time for task coordination and scheduling of multi-AGV.