Hierarchical {{Decentralized Multi-Agent Path Finding}} with {{Congestion-aware Cost Heuristics}}

This paper addresses scalable Multi Agent Path Finding (MAPF) for large fleets of Automated Guided Vehicles (AGVs) in warehousing and production environments, where centralized planning becomes intractable due to NP-hard complexity and exponential growth of the joint state space. We propose a hierarchical decentralized planning approach, which leverages the functional structure of the environment to decouple and parallelize planning and is guided by novel congestionaware cost heuristics on a high-level metagraph representation. To efficiently cope with local changes in the planning problem resulting from parallel planning, we further present CARP-LPA*, combining time-window-based planning of Context Aware Route Planning (CARP) with localized replanning of Lifelong Planning A* (LPA*). In simulation studies, we evaluate our methods on representative scenarios and compare the effectiveness of three proposed heuristics in approximating the impact of congestion on planning decisions. We find that the proposed hierarchical decentralized structure while inheriting scalability and flexibility of the decentralized MAPF algorithms, delivers promising trajectory accuracy compared to the ground-truth centralized solution, with accuracies between 66.7\% and 100\%. The novel cost functions introduced in this work improve these results even further, leading to a minimum accuracy of 83.3\%.