Decentralized Multi-Agent Path Finding in Dynamic Warehouse Environments

Abstract

In many real-world applications of robot fleets, the robots must be able to operate efficiently in a dynamic environment where obstacles stochastically appear. While the related Multi-Agent Path Finding (MAPF) problem has been widely studied, most of the existing approaches primarily rely on offline planning as well as simplistic assumptions that make them ill-suited for dynamic environments. In this paper, we expand the application domain for efficient warehouse robots to non-highly controlled environments. For this purpose, we propose a decentralized approach that can coordinate large fleets of mobile robots through the use of local priority rules. The approach consists of two stages, namely: (i) path planning and (ii) plan execution and motion coordination. A* is initially used to plan the shortest path for each robot, ignoring potential conflicts and not considering the paths of other robots. For plan execution, we implement priority rules to coordinate the robots in a decentralized manner, enabling them to solve conflicts locally as they occur. We conduct extensive experiments to assess the robustness of the proposed approach in handling transient obstacles and variations in robot speeds. Computational results confirm that the approach is effective and robust.