Why Solving Multi-agent Path Finding with Large Language Models has not Succeeded Yet

Thank you for your reviews. Here we answer your question one by one:

1. As our study has broken down the failing reasons into three aspects, i.e., context length, understanding obstacles, and general reasoning capability related to pathfinding. All three aspects are known as LLM challenges, and all these challenges are also known to be not prompt-sensitive and can be solved with prompt engineering. Thus, we believe that introducing other baselines will definitely keep our conclusion the same and there is very little point in introducing them.
2. Thanks for pointing this out. These are papers that work on LLM for planning problems, [1,2,3]. We will add them to our paper.
3. The stepwise local information is changed between different designs. Given the page limit, we can only include the prompt and the examples in our appendix, as you pointed out in the weakness. However, we still invite you to look at Fig. 8, which gives an example of this.
4. In the current paper, we have primarily focused on the success rate because it is still too low, and the only successful scenarios are those that do not require many detours. This means that, even with single-step information, the solution quality (or global optimality, as you mentioned) is not significantly affected. Since the current successful scenarios stop at an agent count of 8 on maps like "room," and the number of instances tested is limited to 5 per setting due to the high cost, metrics other than success rate that contribute to measuring solution quality exhibit a high standard deviation. Furthermore, as the LLM solver is currently unable to find a solution in many cases, we believe it is more critical at this stage to focus on achieving any solution rather than prioritizing a good solution while exploring the potential of LLMs as alternative solvers for MAPF.
5. While we do not have clear evidence and it is difficult to justify, there is a small possibility that breaking down the process could also help the LLM reason more thoroughly, similar to the Chain-of-Thought prompting [4], which enables LLMs to think step-by-step in solving difficult math problems. However, it is not possible to decouple this effect from the context window length issue in the MAPF problem, so we cannot verify this hypothesis. Thus, we can only conclude that SBS is better than OS when the success rate is the sole consideration. However, SBS could potentially have a downside in terms of solution quality—for instance, requiring a greater number of total steps—compared to OS in scenarios where both could generate solutions. Nonetheless, since OS fails to provide a solution in those cases, this cannot be verified.
6. Figure 4 shows the output from the LLM that we have not changed. In this context, the “validated" one refers to no collision at the current step.

[1]. Kambhampati S, Valmeekam K, Guan L, et al. Position: LLMs Can’t Plan, But Can Help Planning in LLM-Modulo Frameworks[C]//Forty-first International Conference on Machine Learning.

[2]. Kalyanpur A, Saravanakumar K K, Barres V, et al. Llm-arc: Enhancing llms with an automated reasoning critic[J]. arXiv preprint arXiv:2406.17663, 2024.

[3]. Chen, Y., Arkin, J., Zhang, Y., Roy, N., & Fan, C. (2024, May). Scalable multi-robot collaboration with large language models: Centralized or decentralized systems?. In 2024 IEEE International Conference on Robotics and Automation (ICRA) (pp. 4311-4317). IEEE.

[4]. Wei J, Wang X, Schuurmans D, et al. Chain-of-thought prompting elicits reasoning in large language models[J]. Advances in neural information processing systems, 2022, 35: 24824-24837.

Thank you for your review. Here we address your concerns point by point:

since the environment is Markov, shouldn’t it be able to decide actions for the agents just based on their current states?

Indeed, the MAPF problem itself is Markov, however, because LLM is not perfect, the LLM can leverage the past history to change its preferred action in the same state, and potentially escape from a local stuck. We invite you to look into the case study in our appendix where such a behavior, instead of improving the performance, decreases the performance of o1-series, but perfectly demonstrates how LLM is leveraging the past history.

Including comparisons to more advanced modular architectures, such as those incorporating memory modules and decentralized planners (e.g., [1, 2, 3])

Thank you for pointing them out. We want to clarify that we have cited the third paper you have cited, and their conclusion that decentralized planners are no better than a centralized planner has guided us to focus on the centralized design given that we are currently focusing on the success rate itself.

the paper feels more akin to a research proposal

Indeed, our paper is, in fact, a position paper on what the future research on LLM for MAPF should be. We sincerely hope you could potentially reevaluate the significance in this case.

Could the authors provide further insights by comparing single-agent and multi-agent tasks While the three factors analyzed in this paper also apply to single-agent planning, the multi-agent setting introduces additional challenges due to the output length increasing at least linearly with the number of agents. Longer outputs expand the total context length, necessitating a restart mechanism in our algorithm. This mechanism reinitializes the entire LLM system with a new problem, using the current locations of all agents as their starting points when context length limits are reached. While this approach addresses the immediate problem, it negatively impacts final solutions by causing the algorithm to lose earlier information, such as each agent's preferred direction and potential map locations that the LLM initially struggled to encode. These losses further exacerbate the other two challenges discussed.

In single-agent settings, the LLM's extended input context can help avoid repeated paths, even when the model does not perfectly understand obstacle locations. Similarly, the solution checker can guide the LLM in producing viable paths even if the generated path is suboptimal. However, in multi-agent settings, the limited capabilities of LLMs lead to more frequent mistakes, resulting in additional restarts. Each restart compounds the loss of historical information, such as agent preferences and map details, ultimately increasing failure rates.

Our experiments demonstrate that on an empty map, where collision avoidance is the only constraint, LLM solvers can effectively scale to handle up to 16 agents (one agent for every four cells on the map). However, on larger maps with fixed obstacles, LLM solvers struggle even with only eight agents. Comparing these results suggests that agent collisions are not the primary factor driving the performance gap. Instead, the increased output length appears to be the main reason for the performance differences between single-agent pathfinding and multi-agent pathfinding (MAPF).

Besides, it is also possible that the reasoning capabilities of current LLMs are also contributing to the failure. As our case study on o1-models showed, LLMs can sometimes fail to use past history to guide future actions correctly, which is an observation that has not happened in the single-agent scenario. However, we believe that this is a smaller issue as even if we have manually regenerated incorrect steps to resolve this problem, the performance of MAPF problems is still worse than single-agent task, so we believe that the main issue is still the complexity caused by multi-agent settings.

Thank you for your review. Here we address the weaknesses you pointed out one by one:

1. Regarding the comparison with traditional MAPF algorithms, the success rate of typical MAPF algorithms like CBS or EECBS will be 100% under 0.1 seconds. While there is currently no advantage for LLM right now, we are the first to explore the possibility of solving MAPF with LLM, and our objective of the paper is to demonstrate that LLMs can solve small problems simply through prompting and discussing what is stopping them from solving larger scenarios. We hope our paper can inspire future research to enable LLMs to function as solvers, offering the significant advantage of leveraging the rapid advancements in LLM technology while eliminating the need for additional training required by current RL-based methods.

2. Our results (Table 3) show that already with 8 agents all methods fail to find feasible solutions (0-20% success rate). When the generated solution is infeasible, it does not make sense to measure quality - one cannot focus on quality before consistently achieving feasibility. Therefore, as the LLM solver is currently not even able to find feasible solutions consistently for high number of agents, we believe it is more important to focus on getting a feasible solution in the harder scenarios (with 8 agents) than getting a better solution in easy scenarios (with 2-4 agents) that do not need many detours and thus not have a huge improvement margin, in the current stage of pushing LLM as an alternative solver of MAPF.

Thanks for your review. Here, we answer your concerns about the weaknesses (as labeled W1-W4 sequentially ) and questions (as labeled Q1-Q3).

Q1. W4. These questions are related to whether the proposed prompt method is the best and whether no other prompting method can address the MAPF problem. Our study has broken down the failing reasons into three aspects, i.e., context length, understanding obstacles, and general reasoning capability related to pathfinding. All three aspects are known LLM challenges as you already acknowledged, and all these challenges are also known to be not prompt-sensitive and can be solved with prompt engineering. Thus, we believe that whether our prompt is the best one is less important, and even if there is a better prompt, our conclusion will still remain the same.

Q2. W1. W2. These are questions about the contribution of our work in comparison to both current work on MAPF and current work on LLM.

From the perspective of MAPF researchers, while the current LLMs show no advantage compared to existing search-based methods or RL-based methods for MAPF, we hope our paper can enable research on LLM-based MAPF solvers that can take advantage of the rapid advancements in LLM technology. More importantly, from the perspective of LLM researchers, the problem of MAPF remains one of the challenging tasks that LLMs still perform very poorly on. When the Blocksworld benchmark (which is related to MAPF) was first introduced to the LLM community, it was hard for LLMs at the time and yet now it can be solved much better by the latest o1 model published by OpenAI . We hope that by introducing MAPF as an LLM planning benchmark in our paper, we can provide a useful next frontier to challenge the abilities of LLMs in the domain of long-context, symbolic understanding, and planning/reasoning capabilities.

Q3. We have included the results of SAPF in section 2.2 of our paper, where the success rate of LLMs as the solver for SAPF is much better than for MAPF with the same workflow that involves a rule-based checker. That is why we moved beyond SAPF to MAPF where the challenges of context length compound with the other challenges to significantly reduce the success rate.

W3. We are currently using the scenarios from the MAPF benchmark [R1]. The benchmark is the most commonly used benchmark that captures the key challenges in real-world MAPF problems, and in general, the MAPF research community believes a good performance on the MAPF benchmark can be generalized to real-world MAPF tasks with relatively easy adaptations.

[R1]. Stern R, Sturtevant N, Felner A, et al. Multi-agent pathfinding: Definitions, variants, and benchmarks[C]//Proceedings of the International Symposium on Combinatorial Search. 2019, 10(1): 151-158.