- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
This paper investigates the problem of large-scale lifelong multi-agent pathfinding, in which agents continuously receive new goals, and the system’s objective is to maximize long-term task throughput. A core contribution of this work is the implementation of map-level computation reuse across all agents; this allows policies trained on a scale of approximately one hundred agents to be deployed in much larger systems. The proposed method is evaluated across various environments—including warehouses, sorting centers, urban settings, and randomized grid layouts—with scenarios scaling up to 10,000–20,000 agents. The empirical validation includes comparisons against both learning-based and planning-based MAPF baselines, as well as comprehensive multi-dimensional ablation studies.
Critical strengths
-
The paper employs shared CNN features for global map and traffic state computation, which are then combined with target-aware soft shortest-path references, finite-depth route reweighting, and global destination assignment to generate actions. This design effectively leverages the structural property of Multi-Agent Path Finding (MAPF)—where numerous agents share the same spatial topology—thereby avoiding a scenario where computational overhead scales linearly with the number of agents based on the full cost of network inference.
-
Although the policy is primarily trained on scenarios involving several dozen to approximately 140 agents, it can be deployed in environments with up to 10,000 agents, achieving competitive throughput across various settings, including warehouses, sorting facilities, urban environments, and randomized maps.
Critical weaknesses
Focusing solely on optimizing and reporting aggregate throughput may effectively mask issues such as individual agent starvation or unfairness. For instance, the average number of completed tasks could remain high even if some agents complete tasks frequently while others remain stationary for extended periods. Consequently, it is currently unclear whether the proposed method improves overall traffic flow or if it achieves higher aggregate throughput at the expense of a subset of agents.
Questions for authors
see Weaknesses
We sincerely thank the reviewer for the positive assessment of our work. We agree that aggregate throughput cannot show how the completed tasks are spread over the agents.
The submission reported throughput only. For the revision we recorded the completed tasks and the longest stop of every agent, with 240,000 agent records per layout (Table 10, Appendix E.2). We summarise the spread by the coefficient of variation (CV, the standard deviation divided by the mean), as Jiang & Lu (2019) do.
The goal sequence of each agent also contributes to this spread, since some sequences need longer paths than others. To isolate the effect of the policy, we computed for every agent an upper bound, the number of tasks it would complete on shortest paths with no other agent on the map. The table gives the CV of this bound and the ratio of the completed tasks to it. The bound is built like the delay of one-shot MAPF, the number of steps a path takes beyond the shortest path (Li et al., 2021), and Asano et al. (2023) measure fairness in multi-robot navigation by a similar delay.
On warehouse, sortation and the two random layouts, whose structure is homogeneous, the CV is close to that of the upper bound and the ratio to the upper bound is nearly the same for all agents, so the spread comes mainly from the goal sequences. On Berlin and Paris, whose structure differs from region to region, the CV is more than twice that of the upper bound, the ratio varies widely between agents, and 0.6% and 0.3% of the agents complete no task within 2,500 steps. Figure 9 maps the delay of the tasks by goal location, and the delay is concentrated in some regions of each map. Agents that stand still for long are blocked by other agents in a local deadlock, and this occurs almost only on the two city layouts. We therefore hypothesise that the spread on the two city layouts comes from congestion at particular places, which the policy does not resolve, rather than from the objective as such. With the same objective, the spread on the other four layouts stays close to that of the upper bound.
Our policy gives no guarantee that every agent reaches its goal, such as the one PIBT has on graphs in which every pair of adjacent nodes lies on a simple cycle (Okumura et al., 2022). The revised conclusion states that we do not address fairness across agents and leaves a fairness-aware extension to future work (Jiang & Lu, 2019; Zimmer et al., 2021; Asano et al., 2023).
References
Hikaru Asano, Ryo Yonetani, Mai Nishimura, and Tadashi Kozuno. Counterfactual fairness filter for fair-delay multi-robot navigation. In Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 887–895, 2023.
Jiechuan Jiang and Zongqing Lu. Learning fairness in multi-agent systems. In Advances in Neural Information Processing Systems, volume 32, pp. 13854–13865, 2019.
Jiaoyang Li, Zhe Chen, Daniel Harabor, Peter J. Stuckey, and Sven Koenig. Anytime multi-agent path finding via large neighborhood search. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence (IJCAI), pp. 4127–4135, 2021.
Keisuke Okumura, Manao Machida, Xavier Défago, and Yasumasa Tamura. Priority inheritance with backtracking for iterative multi-agent path finding. Artificial Intelligence, 310:103752, 2022.
Matthieu Zimmer, Claire Glanois, Umer Siddique, and Paul Weng. Learning fair policies in decentralized cooperative multi-agent reinforcement learning. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 12967–12978, 2021.