Solving Multi-agent Path Finding as an LLM Benchmark: How, How Good and Why
Authors: Weizhe Chen
Sven Koenig
Bistra Dilkina
Venue: Accepted by TMLR ()

Abstract: The rapid success of large language models (LLMs) has spurred extensive research into their ability to solve a wide range of tasks. However, their potential in multi-agent planning remains underexplored. Multi-agent planning presents unique challenges due to the combined complexity of coordination and long-horizon reasoning, often making it difficult to leverage external tools for assistance. In this paper, we introduce Multi-Agent Path Finding (MAPF), also known as multi-robot route planning, as a novel benchmark for evaluating the reasoning capabilities of LLMs. We first describe how the MAPF benchmark can be adapted for LLM-based evaluation, including dataset curation and an agentic workflow for LLMs. We show the motivating success of single-agent planning and multi-agent pathfinding in an empty room map without obstacles, then the failure to plan on the harder room map and maze map of the standard MAPF benchmark. We present our position on why directly solving MAPF with LLMs has not been successful yet, and we use various experiments to support our hypothesis. Based on our results, we discussed how researchers with different backgrounds could help with this problem from different perspectives.

Sven Koenig Published in Transactions on Machine Learning Research (06/2025)
Solving Multi-agent Path Finding as an LLM Benchmark: How, How Good and Why
Weizhe Chen
weishech@usc.eed
University of Southern California
svenkdruci. edu
University of California, Irvine
Bistra Dilkina
dilkina Busc. edu
University of Southern California
Reviewed on OpenReview: https: // openreview. net/ net/forunt forum? id= ShAZEFRVQT
Abstract
The rapid success of large language models (LLMs) has spurred extensive research into their ability to solvo a wide range of tasks. However, their potential in multi-agent planning re- mains underexplored. Multi-agent planning presents unique challenges due the combined complexity of coordination and long-horizon reasoning, often making it difficult to lever- age external tools for assistance. In this paper, we introduce Multi-Agent Path Finding (MAPF), also known multi-robot route planning, the reasoning capabilities of L.M.s. We first describe how the MAPF benchmark can be adapted for LLM-based evaluation, including dataset curation and an agentic workflow for LLMs. We show the motivating success of singlo-agent planning and multi-agent pathfinding an emply room map without obstacles, then the failure plan on the harder room map and maze map of the standard MAPF benehmark. We present our position on why directly solving MAPF with LLMs has not been successful yet, and we use various experiments to support our hypothesis. Based on results, discussed how researchers with different backgrounds could help with this problem from different perspectives.
novel benchmark for evaluating
1 Introduction
Since ChatGPT came out, large language models (LLMs) have been shown to go beyond strictly language- related tasks like translation, and to be a powerful tool in all kinds of domains. Training with very rich and diverse datasets, LLMs incorporate a large variety of knowledge and do not require fine-tuning before generating good solutions in many real-world applications. Over time, recent studies have shown that com- bining LLMs with different ways of prompting can help solve problems that have some aspects of reasoning, including examples from logical problems Yao ct al. (2022); Liu et al. (2023) to controlling robot dog without finetuning Wang al. (2023a).
Motivated by the success of LLMs, people are studying how well pre-trained models perform in all different kinds of domains, and propose benchmarks. Some recent works studied the performance of LLMs on multi- agent problems and showed LLMs can also help mulli-agent coordination Chen el al. (2023b); Agashe et al. (2023). However, they barely cover multi-agent route planning and do not look specifically into the difficulties the domain. In this paper, we consider the problem of multi-agent path finding (MAPF), also known as multi-agent route planning. MAPF is the problem of moving group of agents from their respective start locations to their goal locations without collisions, and can be used directly to formulate real-world

---

Published in Transactions on Machine Learning Research (06/2025)
Complete Solution
[[System Prompt]] Task Description
[[User Prompt]] Scenario description
[[User Prompt]] Step Description
Valid but not finished
Finished
One-step Solution
LLM as Solver
Solution
Checker
Invalid
[[User Prompt]]
Error Information
Figure 1: An illustration of our workflow.
applications like warchouse management Sharon et al. (2015); Han & Yu (2020), swarm control Li et al. (2020), among others. In a typical warehouse scenario, around thousand warehouse robots (agents) could be running simultaneously in warehouse room (scenario), and each agent needs to plan its path, which could be as long as hundred timesteps.
MAPF is a unique multi-agent coordination problem where coordination must be embedded within the planning process. This makes it particularly challenging to enable LLMs to reason about coordination effectively. While using LLMs to generate high-level guidance combined with a low-level path planner has been effective in environments like Overcooked Agashe al. (2023), this approach unlikely to work for MAPF, as effective coordination must be tightly integrated into the planning itself rather than treated as separate guidance layer. On the other hand, path planning is one of the easiest aspects of finding solution in planning problems, as special case compared to more general problems like Blocksworid Valmeekam et al. (2024a), due to its more interpretable state space and coistsaints that only involve obstacle avoidance and movement contimuity. Due to the unique challenges inherent in the MAPF problem, the effectiveness of LLMs solving MAPF remains uncertain.
In this paper, we aim to introduce the Multi-Agent Path Finding (MAPF) problem the machine learning community as new benchmark, with particular focus on the reasoning-intensivy setting of solving MAPF using large language models (LLMs) directly without relying traditional heuristic-based solvers any additional task-specific training. We test the LLMs by giving the scenario information to the LLM, and let the LLM recommend the actions for each agent every single timestep. We use a high-level checker that checks collisions between agents and obstacles to ensure the solution is valid in each step, provides error messages to the LLM when violations occur, and iterales with the LLM until a valid solution generated. We first show that single-agent pathfinding can be solvable and then evaluate the performance of LLMs the empty map, the room map, and the maze map, which are classic maps from the standard MAPF benchmark Stern et al. (2019). We show that LLMs can solve MAPF problems when the scenario is relatively easy, and LLMs fail to generate any valid solution, no matter what the solution quality is, when the scenario becomes harder. While LLMs are evolving extremely fast, and current failures may not apply to the next generation of LLMs, we elaborate on the current failing scenarios and give our position on three aspects as a breakdown of what kind of capability is currently missing in the LLM workflow, namely 1) the capability to understand the scenario, 2) the context length limit, and 3) the reasoning capability. We incorporate a list of experiments featuring various prominent prompt design alternatives, such as image-based and text- only inputs, and with or without single-step observation information, among others. Finally, we provide a discussion on the challenges of using LLMs for MAPF in the real world, and discuss how different rescarchers could contribute to the problem from different directions.
We hope our work can serve as a building block for future research in foundation models for MAPF. And more importantly, we hope this paper introduces LLM rescarchers the unique and persistent challenges of MAPF. We envision MAPF becoming a benchmark for evaluating future LLM advancements, particularly in methods addressing the failure modes identified in this study.
2

---

Published in Transactions on Machine Learning Research (06/2025)
2 LLMs for Multi-agent Path Finding
2.1
Preliminary
The multi-agent path finding (MAPF) problem the problem of finding a set of collision-free paths for a set of agents in a known environment while minimizing their travel times. Specifically, in this paper, we consider the problem in Stern et al. (2019); Li et al. (2022), which is four-connected grid map, where each agent is given a start cell and goal cell. A scenario is defined as the combination of the description of the map, indicating which cells have obstacles, and the start cells and goal cells of each agent. At each timestep, an agent can move to an adjacent cell or stay in its current cell. A collision happens if two agents end up in the same cell at the same timestep. Each agent remains at its goal cell after it arrives until all agents arrive at their goals. The objective is to minimize the makespan of the solution, ie., minimize the time when the last agent arrives at its goal location.
With the number of parameters of LLMs being exponentially larger than the degrec of freedom in small reasoning problems, LLMs have the polential to solve some easy problems in reasoning with certain prompts Wei et al. (2022), and break down harder problems into smaller ones to get suboptimal solutions Yang et al. (2023). When applying to MAPF, we hope LLMs can be an alternative model to the current MAPF reinforcement learning- based models without any additional training.
2.2
Benchmark Protocol
2.2.1
Dataset Files
Multi-Agent Path Finding (MAPF) is well-established research domain within classical planning, supported by a comprehensive benchmark dataset introduced by Stern et al. Stern et al. (2019).
The dataset comprises 33 maps, each provided both as an image and as a corresponding symbolic textual representation, where '8' denotes fixed obstacles and represents free cells. For each map, two class of scenario files are available, corresponding to different agent distribution strategies: (i) agents distributed uniformly across the map, and (ii) agents placed based on random coordinate generation, resulting in a less uniform spatial distribution. By default, we will use the first setting in this paper. Each scenario file contains list of start and goal positions for agents. When evaluating scenario with n agents, the first n entries in the scenario file are used to specify the corresponding start and goal locations. For repeated evaluations on the same map with different start-goal combinations, scenario files are used in sequential order, beginning with scenario file 1.
The maps in the dataset can be categorized into several distinct layout types, each presenting unique chal- lenges and requiring different planning capabilities. Every map is assigned a descriptive name that encodes its structural characteristics. For instance, "Maze-32-32-2" indicates that the map belongs to the maze class, has dimensions of 32 x 32, and is the second instance of this type in the benchmark. In this work, due to the current limitations of LLMs in complex spatial reasoning tasks, we focus our experiments on three representative maps: EMPTY-8-8, ROOM-32-32-4, and MAZE-32-32-2. We encourage the community to also use the same map we are using as a starting point, and use the remaining maps and more scenarios when the capability of LLMs becomes better. For potential training, the map can be used, but the scenario files should not be directly trained on to avoid overfitting.
2.2.2 Evaluation Metrics
The metrics of the problem primarily consists of success rate and solution quality. Success rate is about whether the solver can find a complete solution for the given scenario that is collision-free and every agent has reached their goal. The solution quality is defined as the makespan, i.e., the time spent from when all the agents start moving to when the last agent reaches its goal. There is also the variant of the sum of cost, defined as the total sum of time all agents spent to reach their goal, respectively. Given the current success rate of LLMs, we will leave the solution quality metrics for future research.
3

---

Published in Transactions on Machine Learning Research (06/2025)
While the objective of the problem is to let LLM solve the problem through the workflow, we cannot allocate infinity budget on the problem and infinitely loop in the magnetic workflow. Thus, we define solution generation to be successful if it does not fail because of any of the following, and early-stop the generation correspondingly:
Fails to generate a plan whose number of steps is at most times that of the optimal plan.
2. Fails 5 consecutive times in a single step after we provided the first round of feedback, specifying whether the current solution is correct or not.
2.3 Methods
In this paper, we focus on using LLMs to solve the MAPF problem directly. However, it is obvious that current ML models cannot be perfect solvers in their first trial, and we introduce high-level collision checker to ensure the plan generated by the LLM is valid. We inform the LLM about the mistake in the current solution, if any. Unlike some previous works Yao et al. (2022); Yang et al. (2023), our checker is not another LLM both because it is extremely casy and efficient to detect collisions by a rule-based detector in linear time, and also because the LLM fails to always correctly identify the collisions. A detailed comparison is provided the appendix. In this checker, we not only check for agent-to-agent collisions but also check for any collision with the fixed obstacles. We do not provide any additional guidance on how the LLM should resolve this. By default, all the information, like coordinates, is provided in text, and will later discuss the performance difference caused by different input formats.
Following the common practice of LLMs Kambhampati et al.; Chen et al. (2023b), we build an agentic workflow shown in Fig. 1. As existing learning based approaches Damani et al. (2021), we give LLMs stepwise local information and let the LLM choose the actions of agents step-by-step. This step-by-step (SBS) generation different from the popular chain-of-thoughts idea Wei et al. (2022) used in LLMs by not introducing more intermediate reasoning processes in the generation. Instead, it breaks down the whole planning task into smaller single-step tasks, the LLM does not need to be fully correct before we can use some results from it. Later in the paper, we compare SBS with a variant that generates the whole plan in one shot (OS) with the help of chain-of-though prompts and show the comparison in Table, 2. We start by giving the LLM the system prompt to become a solver for the MAPF problem. This part is fixed within each map, and differs in the map description part in different maps. Then, we start the user prompt by providing the scenario information, which includes where the obstacles are, as well as the start location and the goal locations of each agent. We found that providing LLMs with specific local information about viable actions for the immediate next step significantly helps them avoid collisions with static obstacles, provide a single-step observation (SSO) in the prompt by default. Then we start to read the output of the LLM, use the checker to determine whether the output of the LLM is valid, and either output the errors to let the LLM correct on the current step, or tell the LLM to move on to the next step with the information that is specifically for the next step. To address the total token limit, we leverage the fact that MAPF is a Markov decision process where each state is independent of its previous states, and we restart the prompt from scratch, ie., treat the current agent locations as their starting point, whenever the current context to be fed into the LLM is longer than the model limits.
we
Although there are numerous possible strategies for constructing prompts for LLMs, we defer a detailed discussion to the next section, where we use different prompt designs to help analyze the causes of failure. The prompts used in our experiments are provided in the appendix.
2.4
Benchmarking Results
2.4.1
General Experiment Settings
Each setting in the experiment tested on 5 different scenarios in the standard MAPF benchmark Stern et al. (2019). By default, we are using the GPT-4-1106. model, also known as the GPT-4-turbo model with temperature 0 and seed 42.
4

---

Published in Transactions on Machine Learning Research (06/2025)
Success Rate (%)
Map
Dist
Success Rate (%)
OS
SBS
A*
Map
OS
SBS
CBS
[2, 8)
80
100
100
2
20
100
100
Room
88 16)
40
100
100
[16, 32)
40
80
100
Empty
0
100
100
8
0
100
100
32, 100)
20
40
100
16
0
60
100
Maze
2, 8)
20
80
100
20
100
100
[8, 16)
20
100
Room
0
80
100
Table 1: The success rate of solving single-agent
20
100
path finding with GPT-4-Lurbo on ROOM-32-32-4 and MAZE maps with varying ground-truti short- est path distance (Dist). OS and SBS are different prompt versions for LLMs, while A is search- based baseline that is purely included to demon- strate the failure of LLMs compared to previous algorithms. The names of the methods are simpli- fied. For OS, is combined with GO and TOM, and for SBS, it combined with GO+SSO and TOM. All the details for these settings are de- scribed later.
Maze
2
0 0
100
Table 2: The success rate of solving MAPF with GPT-4-turbo on EMPTY-8-8, ROOM-32-32-4 and MAZB-32-32-2 maps with varying numbers of agents (u). OS and SBS are different prompt ver- sions for LLMs, while CBS is a search-based algo- rithm that is commonly used in MAPF. For OS, it is combined with GO and TOM, and for SBS, it is combined with GO+SSO and TOM. All the details for these settings are described later.
We do not consider any token limit error in this paper because we restart at each step to clean its travel history if the token limit is too long, and 5 times in single step guarantees that the message length in one step is within the token limit.
2.4.2 dingle-agent Path Finding Results
As discussed in previous work Valmeckam et al. (2024a), while LLM might not know how to generate optimal plan, our results show that it could generate some plan regardless of the optimality. As shown in Table. 1, we found that LLM could generate plan after few iterations in relatively easy scenarios. We observe that with the growing groud-truth shortest path length, the success rate of LLM drops significantly, especially in the one-shot settings (OS). In the maze scenario, it is hard to find one solution even in the smallest case, and we will discuss the reasons in the next. section. In contrast, traditional search-based algorithms like A* solve the problem at the same scale very easily.
We also found that the cause of failing in pathfinding is different from the cause of failing in general planning tasks where the generated plan is invalid, usually by breaking requisite constraints Valmeekam et al. (2023). In path planning, the only constraint is that one agent needs to move to an adjacent cell and cannot jump across the map. This is a very easy task for LLM to follow, and thus, in our experiments, we never see the LLM failing due to that constraint, even if the only instruction about this constraint is 'in a 4-connected grid'. Building on our findings in single-agent path planning, we posit that large language models (LLMs) hold promise for generating effective solutions to multi-agent path finding (MAPF) problems. In particular, small-scale MAPF scenarios may serve as both a practical application domain and a distinctive benchmark for evaluating the reasoning and planning capabilities of LLMs.
2.4.3 Multi-agent Path Finding Results
We start by showing that LLMs can be a promising solver in easy domains. We test the performance of LLMs on the EMPTY map from the MAPF benchmark Stern et al. (2019), which has no obstacles at all and only requires the agents to not collide with each other. The results are shown in Table. 2. We observe that for smaller-scale problems that have fewer agents, GPT-4 can successfully generate valid solutions with the workflow. However, GPT-4 with the same workflow fails to generate valid solutions when more agents are on the same map, while classic algorithms like conffict-based search (CBS) casily maintain a perfect success rate in solving the problem. We also observe that one-shot (OS) generation fails to generate solutions even
5

---

Published in Transactions on Machine Learning Research (06/2025)
1
3
2 S1
311
1
91
92
0
92
(a)
(b)
Figure 2: The ROOM-32-32-4 map (left) and the MAZE-32-32-2 map (right). The picture is vertically flipped to match the common knowledge that higher vertical positions in- dicate greater values.
Figure 3: Two examples of the MAPF problem, which are also known as the symmetry breaking examples for MAPF community, where black denoles a fixed obstacle. In 3a, every pair of shortest path will collide with each other. 3b, every pair of shortest paths will collide cell (2, 1).
in scenarios with 4 agents. This is because the whole plan is quite long, and the total number of possible failures is the product of possible failure at each step, making it inefficient to find a valid solution.
Motivated by the success on the EMPTY map, we tested the same workflow on the 200M-32-32-1 map and the MAZE-32-32-2 map, which shown Fig. The results are shown Table. 2. In this case, we found that LLMs fail to generate solutions when the number of agents already quite small, and that LLMs completely fail on the MAZF-32-32-man
with only agents. Motivated by the superior performance of SBS over OS, we adopt SBS for the remainder of the paper without further specification.
In our experiments, we observe that LLMs fail in the empty map scenario with 16 agents due to a rare case of consecutive missteps in a single planning step. In all other cases, failures arise from overly long solution paths. Specifically, 77% of the failures are caused by oscillatory behavior, where agents repeatedly move within a confined area, while the remaining failures result. from unnecessarily long detours.
3 Cause of Failures
Given the rapid pace of advancement in large language models, it remains uncertain how long current limi- tations will persist. Nonetheless, systematically analyzing these failures and identifying their root causes is essential for progress. Specifically, we categorize the failure modes into three underlying sources from the per- spective of natural language models: general reasoning capability, long-context capability, and understanding symbolic information.
3.1 Reasoning Capability
In this paper, focus optimizing the makespan of the MAPF solution, and making the agents prefer to wait rather than detour in small scenarios that do not lead to endless waiting. We calculate the average ratio of makespan to the maximum length among the single agent shortest paths (a standard normalization practice in MAPF as this provides valid lower bound on the optimal MAPF solution), and in scenarios that are successfully solved as denoted by the ones in Table 2, this average is 1.5. This means that LLMs can mostly succeed in scenarios that do not need a lot of waiting, and in most steps, they only need to go in the two dircctions aligned with the goal's direction. LLM fails other scenarios bocause noeds pathfinding complex environments. A simple example of the failure of path finding is shown in Fig. 3, and we provide the output of the first step in Fig. 4. While waiting for step can clearly lead to the optimal solution that has a makespan of 5, the LLM chose to move agent 2 to the left and resulting in total makespan of 6. This example shows that LLM does not understand what makespan is and how to optimize for makespan.
On the other hand, when we look at the average number iterations for prompts with both global obstacle obscrvation the first user prompt and singlo-step obstacle Anservations(GO+SS not very close to 1 which means no iterations all. This is because even if we have explicitly let the LLM list. all the coordinates of agents, it does not have the capability check the answers itself without the use
in Table. 3, it still

---

Published in Transactions on Machine Learning Research (06/2025)
Step 1: Agent
Current: (0,2)
Goal: (3,1)
Move: Right to (1,2)
Agent 2:
Current: (1,3)
Goal: (2,0)
Move: Down to (1,2)
After the move, the coordinates of the agents are:
Agent 1: (1,2)
Agent 2: (1,2)
There is collision between Agent 1 and 2. will regenerate another solution immediately.
Agent 2:
Current: (1,3)
Goal: (2,0)
Move: Left to (0,3)
Figure 4: Part of the output from GPT-4-turbo for the symmetry breaking example in Fig. 3b. Full example is provided in the appendix.
of external tools. More specifically, LLMs are not guaranteed to tell whether a list of tuples of numbers has any duplicates, and can often fail because of this. We also observe that the GPT-4-8K model requires more iterations compared to the GPT-4-Turbo model, which we attribute either to increased information retention challenges in the former to the enhanced capacity of the latter.
In many problems, limited reasoning capabilities are often addressed through tool use. However, finding a good way to use tools in MAPF remains particularly challenging, as it requires not only pathfinding in a complex environment but also the strategic and efficient avoidance collisions among all agent pairs. The coordination between agents is required each step, and each step only. we let the tool, in this case, a single-agent planner like A include collision avoidance, the problem alrcady solved as CBS Sharon et al. (2015), where LLM did help. On the other hand, the tools must know how collisions are supposed to be avoided and add those constraints into the heuristic search algorithm. This paradox makes it very difficult to use LLM with tools in MAPF.
We have also lested the ol-preview model from OpenAT, which has been shown to significantly improve the reasoning and planning capability Valmeekam et al. (2024b). Compared to the standard based checker, which is the default for other experiments, we introduce a human checker that analyzes the explanation and chooses to retry when the current explanations could lead future failure. We observe that such improved checker can also facilitate the generation lot, which further indicates that the current reward model used in training and, potentially, the inference is not correct for MAPF, Examples and more explanations on why ol-preview leads to worse performance compared to GPT-4-turbo in the default settings are provided in the appendix.
3.2 Long-context capability
Because the underlying architecture popular LLMs is transformers, which further rely on self-attention, longer context in the input will significantly increase the computing complexity the process. Therefore, in their training process, they maximum limit of tokens on the input and trained specifically on them. Current large language models released will also provide context. length limit, which is long 200K

---

Published in Transactions on Machine Learning Research (06/2025)
Success Rate (% )
Avg. Iterations
Model
GO
GO+SSO
GO
GO+SSO
2
80
100
2.7
1.6
Checker Type
Success Rate (%
GPT-4-8K
4
20
60
3.0
2.3
8
0
0
N/A
N/A
based
Human
40
2
100
100
2.1
1.2
GPT-4-128K
4
60
80
2.7
1.4
8
20
N/A
2.4
Table 4: The success rate of ol-preview (OpenAI) with different checker type on 8 agent scenarios (n = 8) with GO+SSO+SBS+TON in room-32-32-4 map.
The success rates and average iterations per step used until proceed to next step in success scenarios for GPT-4 and GPT-4 Turbo, whose token limits are 8K and 128K respectively, on the room-32-32-4 map with different number of agents(n). The name of the variants are simplified. Both variants are tested under SBS and TOM, with details described in other parts of the paper.
Table 3:
tokens, and any request with a longer context length will be rejected. This is a long enough length for many tasks and even able to read a textbook, and many users are satisfied with the length. Recent studies have demonstrated that the performance of large models, such as GPT-4 Turbo with 128K context length, is not consistent when processing inputs of 8K versus 128K tokens 1. What is even worse is that in the real-world applications of MAPF, the total number of agents running in the environment could be up to a few thousand. Even in the ideal case that our prompt will grow linearly to the number of agents, an environment with a 5M
thousand agents will require total context length of 250(tokens/ogg) /agent step)+50( +50( 11000 tokens, which is much bigger than the current limit even without considering the related reasoning capability under those length. Because the token limit is strict, we have introduced the restart mechanism in our methods, and in our current experiment scale, we have to restart the LLM around every 7-10 steps in large or complex scenarios. We also observed that the mumber of tokens used grows non-lincarly with regard to the number of agents due to the increasing number of ilerations, and we have put the numbers in the appendix.
In table. 3, we show our results on the ROOM map, and test with different GPT-4 models with different context lengths, in the setting of global observation (GO) only and the version with single-step observation (SSO). We will talk about these two settings in the next section. We found that when the context length limit grows, the success rate also increases. This is especially helpful when the single-step observation information that tells what valid actions each agent has is not provided. The failures here are not direct failures by exceeding the context length limit, but from the forgetting in restart caused by reaching the context length limits. Because of these restarts, our models often completely forget that they have been to certain locations, and then go back and forth in certain areas with dead ends like the center room in the ROOM map. We have also included the ol-preview model from OpenAl Jaech et al. (2024) in the experiment on the biggest scale, To our surprise, it is even worse than the GPT-4-turbo version. In the appendix, we provide case study with more detailed explanations. And because the ol models are equipped with the capability of writing programs that help them determine in the process, their failure of them also indicates that LLMs currently cannot naturally link the problem of MAPF as one of the problems they can write a program to solve, e.g.. write a CBS algorithm and solve the problem. While manually instructing the LLMs to write a code CBS is very easy for LLM ?, in this paper we focus on the underlying capability of LLMs to find a way to solve MAPF themselves without any guidance.
3.3 Understanding Symbolic Information
MAPF scenarios can be broken down into a pair of start location and goal locations, together with the map information. While understanding the coordinate version of start goal location pairs is relatively casy, understanding the map information hard. Trained with publicly available text, LLM learns what specific
httpps:/ htom hat.uuu..oooo/ggaaaataaaa ggaagaaammtttan. Beaamrrdt/IILMMTess /LL NeedleInA
Latest LLMs have a 100% success rate when explicitly required to write the CBS algorithm.
8

---

Published in Transactions on Machine Learning Research (06/2025)
n
MM
TOO
TOM
2
100
100
100
map fellows, where desote the lecation ageat deanie enppty agent pass. battem-left (8J), right cell (4/%
4
20
60
80
8 0
0
20
obstacles are: (11,0), (3.21).
-
Table 5: The success rate (%) of dif- ferent ways of inputting the map in- formation to LLM on RooM-32-32-4 map with different number of agents (n). All settings are combined with SBS+GO+SSO.
RR..
TOO
Figure 5: An illustration of the difference between multimodal input (MM), text that describes the whole map (TOM), and text that describes the obstacles (TOO).
map means by finding similar contexts online, which mostly comes from other related fields in planning, like solving a maze. However, one problem is that people barely provide any such information online since people have the common knowledge of what do with a map with code and preprocess the map information in the code rather than explicitly provide the set of where the obstacles are as the original input. Therefore, this leads a lack of training data with related context about the information in the pictures or in a symbol- based input. As mentioned earlier, 77% of the overall failure is caused by agents detouring back and forth in certain area blocked by obstacles. These failures directly indicate that the LLM fails to understand the map information provided.
Because of this, our main prompt included guidance on what action could be taken in the current step to increase the success rate little bit. In Table. 3, we find that while global observation can achieve a high win rate with the support of our high-level checkers, it also increases the average number of iterations per step. Furthermore, it fails in scenarios where SSO would be effective, as it exceeds the step limits defined in Sec. 2.2.2. In general, LLMs fail in medium complexity maps like ROOM, and completely fail in much harder maps like MAZE, even with the help of SSO.
In all the experiments above, we use pure-text-based input because of the popularity and simplicity of pure- text input. However, this was not the case before: In earlier work reinforcement learning for MAPF, people transformed the input into image-based input within the field of view and used neural networks like convolutional neural network (CNN) to read the information. Therefore, as shown in Fig. 5, we propose three different methods, which all share the same prompt of describing the problem definition and use different versions of the prompt describing the scenario:
A multimodal-basee method MM where we use an image give the picture of the map, and text to describe the problem and the scenario.
2. A text-only method TOO that describes the map by listing the coordinates of the obstacles.
3. A text-only method that describes the map by feeding the text version of the map with "@' denoting the obstacles and ? denoting an empty space, named TOM.
We test the performance of these three variants, and show the results in Table. 5. We found that with image-based input, the results are even worse. For example, large models only have high-level idea that there is a wall in the middle area, rather than knowing there is wall exactly from (3, 10) to (20, 10). The failure of TOO further indicates that LLMs do not know how to combine high-level intuitions of where obstacles are with concrete reasoning during planning. Overall, in complex environments such as mazes and real-world city maps, LLMss cannot offer any form of guidance, not necessarily the specific action recommendations tested in this paper, until they can accurately comprehend the relationship between obstacles and the paths of agents.
9

---

Published in Transactions on Machine Learning Research (06/2025)
4 Discussion
We would like to note that the methods in this paper are not designed to either outperform the state-of-the- art classic solvers or surpass the performance of learning-based solvers. Instead, the goal is to demonstrate that LLMs can solve small problems simply through prompting and to analyze the factors limiting their ability to handle larger scenarios. Specifically, current heuristic-based algorithms like conflict based search Sharon et al. (2015) can solve all the scenarios tested in the paper in less than 0.1 sccond. Moving on, we believe the three reasons for failures can each independently relate to different research directions. Improving capability in long context already a popular direction in NLP, and many papers are also looking into improving the general reasoning capability. We believe that much ongoing research has the opportunity to improve the performance of LLMs on MAPF, and we are pleased to have more researchers test this unique problem. Also, the recent development of building foundation models that combine language and image generation could potentially help with the reasoning in MAPF. Image generation models like stable diffusion Rombach et al. (2022) have shown to be a strong tool in single agent path finding Janner et al. (2022). While these diffusion models are not designed for multi-agent planning and are even hard to apply to MAPF, strategically using them could partially help the lack of reasoning capability. Regarding potential finetuning, we believe more annotated data are needed to help foundation models connect the abstract description to concrete coordinate-level knowledge of where obstacles are, and how to coordinate between agents. Future research could finetune using their data, or at least open their data to the general public, and let the next version of released models from industry companies include such data by automatically getting data online. Hopefully, such data could help foundation models know that position encodings are more important in planning problems. Additionally, our results on current rule-based checker v.s. human checker also indicate that future rescarch could work on building good checker, i.c., a reward model in large language models, to improve the performance of LLMs. However, we still acknowledge the fact that while some certain more advanced way of solving the problems, e.g., more advanced prompts, cannot directly address all the obstacles mentioned in the paper, it is still possible that they can be beneficial to the domain and might lead to some additional gaps to be solved. Overall, we believe that as unique domain, MAPF can be a useful benchmark for general LLM researchers to test their idea on.
While our current prompt has already included a lot of common tricks for prompting the LLMs, there are some other tricks that we found not as helpful as others on GPT-4-turbo, and we did not include them in the final version. Specifically, this include ReAct Yao et al. (2022), CoT Wei et al. (2022) upon SBS, vision of thoughts Wu et al. (2024), adding a whole example to the prompt in-context learning examples, and breaking the instructions into bullet points.
Although the success rate is one of the most important factors in measuring the performance of a solver, there are also other challenges that need to be addressed before using LLMs in real-world scenarios. First of all, success does not indicate anything about the quality of the solution. In our experiment, we found that the success scenarios usually come from easier scenarios that agents mostly only need to follow their direct shortest path. When planning gets harder, the success rate gets much worse. To improve the reasoning capability, future researchers and users could choose to make a dataset of scenarios and their good solutions publicly available on the internet, so when training with newer data, this specific problem could be directly included in the training set. Furthermore, the current workflow does not include any heuristics or tool use during the generation but only as a solution checker. Although the best approach for incorporating these aspects remains uncertain, we believe this presents a highly challenging yet meaningful research direction. For potential rescarchers going in this dircction, we want to remind them to keep looking at the consistency of the deconflict of agents, which could be seen as moving obstacles, and the deconflict of the fixed obstacles on the map. A successful method should consider both difficulties in similar manner.
On the other hand, latency is always a problem for LLMs when used in real-world production. If one wants to use their own models, which is currently 500 tokens per second after using stale-of-the-art system-wise optimization like vLLM Kwon et al. (2023) for LLAMA-2 Touvron et al. (2023). However, this speed is not enough as a typical round of output will have 1500 tokens, and it may take a few rounds before the LLM generates a valid solution. If one wants to use models provided through API like GPT-4 from OpenAI, the latency of the models will depend on list of factors like network connection and server availability. In our
10

---

Published in Transactions on Machine Learning Research (06/2025)
paper, we typically need to wait around 15-30 seconds for one step to get completed, where less than 0.1 seconds are used for local processing.
5 Related Works
LLM for Reasoning Since the release of GPT-3, researchers have studied the effect of how they are performing on diverse sets of problems. Ideas like chain of thought Wei et al. (2022), in context learning Ye et al. (2023) have been shown to significantly improve the performance of LLMs different lasks related to reasoningFu et al. (2022); Shum et al. (2023). A recent line of work has been introduced use natural language feedback in the process to introduce iterations and give LLMs more than one chance to generate correct solutions, which has been shown to significantly help in code generation and reasoning Chen el al. (2023a); Yang et al. (2023); Shinn et al. (2023). Specifically in LLMs for planning, there is a line of work that shows how bad LLMs are in general planning domains Valmeekam et al. (2023; 2024a), some works on benchmarking the performance of LLMs on task planning or travelplanning, which while share the name of planning, focus more on reasoning Zheng et al. (2024); Xie et al. (2024), and a few papers on combining the LLMs with search and cvolutionary algorithms and improve the performance of LLMs on reasoning problems, especially on planning problems where search are traditionally performming well Chen et al. (2024); Su al. (2024); Lee et al. (2025). In this paper, are specifically looking into specific problem in planning.
LLM for Multi-agent Systems While there is extensive research using LLMs for many different problems, there is little work that addresses the problem of LLM for multi-agent systems in the beginning, As time proceeds, there has been a list of works that promote research in social behavior by creating multi- agent environment powered by a lot of LLM agents Tan et al. (2023), create dialogue-based games with LLM Schlangen (2023). Recent work has shown that dialogue between multiple agents can help remove factual errors Du et al. (2023); Wang et al. (2023b). When it comes to solving problems related to multi-agent some works that are related to robotics Zhang et al. (2023); Mandi et al. (2023) while
system, there limited to the scale of two to three agents. Chen et al. (2023b) studied whether using more decentralized controller can help to solve the context. length limit problem when the number of agents is higher, and concluded that in a centralized controller environment, creating separate LLMs for different agents does not help improve the success rate. While they succeed in their domains, in this paper, we specifically look at the problem of MAPF, and we show the cause of failure in the MAPF problem because of its unique challenges.
Multi-agent. Path Finding Multi-agent path finding (MAPF) is a problem that has won much attention in recent years because of its close relationship to real-world applications. It has previously been solved with more classic methods like heuristic search algorithms Sharon et al. (2015); Li al. (2021); Okumura (2023), rule-based algorithms Han & Yu (2020), and reduction- based algorithms Surynek et al. (2016). While learning-based based approaches have not yet outperformed classic approaches, they have also begun to win a lot more focus for their fast inference time and generalizability. PRIMAL Sartoretti et al. (2019) proposed to learn a policy for MAPF using a combination of reinforcement learning and imitation learning. Following that, a group of works proposed a diverse set of methods from building curriculum Damani et al. (2021) to follow guidance from classic methods in each step Skrynnik et al. (2023). In this paper, we focus on using LLM, which is a Marning-based approach but is not specifically fine-tuned for MAPF problems.
6 Conclusion
In this work, we introduce the Multi-Agent Path Finding (MAPF) problem as novel and structured bench- mark for evaluating the reasoning capabilities of large language models (LLMs). We present a framework for formulating MAPF as a benchmark lask and empirically demonstrate that, while LLMs can solve sim- ple MAPF instances, their performance degrades significantly as problem complexity increases. To better understand the specific challenges posed by this benchmark, we analyze the failure modes of LLMs and categorize them into three distinct capability gaps, namely reasoning capability, long-context capability, and understanding symbolic information. Through extensive experiments, we validate this categorization and
11

---

Published in Transactions on Machine Learning Research (06/2025)
discuss how addressing these challenges may require insights from diverse research communities, including planning, representation learning, and natural language understanding.
Acknowledgements
The National Science Foundation (NSF) supported the research under grant number 2112533: "NSF Artificial Intelligence Research Institute for Advances in Optimization (AI4OPT)'.
References
Saaket Agashe, Yue Fan, and Xin Eric Wang. Evaluating multi-agent coordination abilities in large language models. arXiv preprint orXhv:2S10.08900, 2023.
Xinyun Chen, Maxwell Lin, Nathanael Schärli, and Denny Zhou. Teaching large language models to self- debug, arXiv preprint orXiv:2304.05126, 2023a.
Yanan Chen, Ali Pesaranghader, Tanmana Sadhu, and Dong Hoon Yi. Can we rely on Ilm agents to draft long-horizon plans? let's take travelplanner as an example. arXiv preprint Xiv:2408.06314 2024.
Yongchao Chen, Jacob Arkin, Yang Zhang, Nicholas Roy, and Chuchu Fan. Scalable multi-robot collaboration with large language models: Centralized or decentralized systems? arXiv preprint M.Xiv:2309.1594.. 2023b.
Mchul Damani, Zhiyao Luo, Emerson Wenzel, and Guillaume Sartoretti. PrimalS 28: Pathfinding via reinforcement and imitation multi-agent learning lifelong. IEEE Robotics Autom. Lett., 622):2666-2673, 2020.00222222222222
2021. doi: 10.1109/LLR (...9/TR...00 2...2.2.... 3021.30620 URL.
Yilun Du, Shuang Li, Antonio Torralba, Joshua B. Tenenbaum, and Igor Mordatch. Improving factuality and reasoning in language models through multiagent debate. CoRR, abs/ 0bss/2305.14322 2023. doi: 10.
48550/ARXTV. WwW..335.11110 URL sttps://doi... wwtp.......0//aa........ 48550/arXiv.....////// 2305. 14325.
Yao Fu, Hao Peng, Ashish Sabharwal, Peter Clark, and Tushar Khot. Complexity-baser prompting for multi-step reasoning. arXiv preprint arXiv:2210.00720, 2022.
Shuai D. Han and Jingjin Yu. DDM: fast near-optimal multi-robot path planning using tiiersified-pate and optimal sub-problem solution database heuristics. IEEE Robotics Autom. Lett., 2:1350 1357, 2020.
Aaron Jaech, Adam Kalai, Adam Lever, Adam Richardson, Ahmed El-Kishky, Aiden Low, Alec Helyar, Alek- sander Madry, Alex Beutel, Alex Carney, et al. Openai ol system card. ar preprint arXiv:2412. 2024.
Michael Janner, Yilun Du, Joshua. B Tenenbaum, and Sergey Levine. Planning with diffusion for flexible behavior synthesis. arXiv preprint arXic:2205. 09991, 2022.
Subbarao Kambhampati, Karthik Valmeckam, Lin Guan, Mudit Verma, Kaya Stechly, Siddhant Bhambri, Lucas Paul Saldyt, and Anil Murthy, Position: Lims can't plan, but can help planning in Im-moouulo frameworks. In Forty-first International Conference Machine Learning.
Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph E. Gon- zalez, Hao Zhang, and Ion Stoica. Efficient memory management for large language model serving with pagedattention. In Proceedings of the ACM SIGOPS 29th Symposium on Operating Systems Principles, 2023.
Kuang-Hue Huei Lee, Ian Fischer, Yuch-Hua Wu, Dave Marwood, Shumeet Baluja, Dale Schuurmans, and Xinyun Chen. Evolving deeper 1mm thinking. Xixiv preprint arXiv:2501.0889/ 2025.
12

---

Published in Transactions on Machine Learning Research (06/2025)
Jiaoyang Li, Kexuan Sun, Hang Ma, Ariel Felner, T. K. Satish Kumar, and Sven Koenig. Moving agents in formation in congested environments. In Daniel Harabor and Mauro Vallati (eds.), Proceedings of the Thirteenth International Symposium on Combinatorial Search, SOCS 2020, Online Conference [Vienna, Austrial, 26-28 May 2020, pp. 131-132. AAAI Press, 2020. doi: 10.100//SOC..VII.I.555 V1111.18525. URL https: //doi. orggoo////// 10. 1009/ v11i1. 18525.
Jiaoyang Li, Wheeler Ruml, and Sven Koenig. Eecbs: A bounded-suboptimall search for multi-agent path finding. In Proceedings of the AAAT conference on artificial intelligence, volume 35, pp- 12353-12362, 2021.
Jiaoyang Li, Zhe Chen, Daniel Harabor, Peter J. Stuckey, and Sven Koenig. MAPF-LNS2: fast repairing for multi-agent path finding via large neighborhood search. In Proceedings of the Thirty-Sizth Conference on Artificial Intelligence (AAAI), pp. 10256 10265. AAAI Press, 2022.
Zijun Liu, Yanzhe Zhang, Peng Li, Yang Liu, and Diyi Yang. Dynamic llm-agent network: An Ilm-agent collaboration framework with agent team optimization. arXiv preprint [xXi::3310.02100 2023.
Zhao Mandi, Shreeya Jain, and Shuran Song. Roco: Dialectic multi-robot collaboration with large language models. arxiv preprint orXiv:2307.04 738, 2023.
Keisuke Okumura. Lacam: Search-based algorithm for quick multi-agent pathfinding. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp. 11655- 11662, 2023.
Robin Rombach, Andreas Blattmann, Dominík Lorenz, Patrick Esser, and Björn Ommer. High-resolution image synthesis with latent diffusion models. In Proceedings of the IEEE/CVF conference computer vision and pattern recognition, pp. 10684-10695, 2022.
Guillaume Sartoretti, Justin Kerr, Yunfei Shi, Glenn Wagner, T. K. Satish Kumar, Sven Koenig, and Howie Choset. PRIMAL: pathfinding via reinforcement and imitation multi-agent learning, IEEE Robotics Autom. Lett., 4(3):2378-233) 2385, 2019. doi: 20A.2019.200 2903261.
http:LLRA.211.90322222 URL attps://aoi.org/00.111 org//0.1109/
David Schlangen. Dialogue games for benchmarking language understanding: Motivation, taxonomy, strat- egy. arXiv preprint arXin:2304.07000 2023.
Guni Sharon, Roni Stern, Ariel Felner, and Nathan R. Sturtevant. Confliet-based search for optimal multi- agent pathfinding. Artif. Intell., pp. 40-66, 2015.
Noah Shinn, Beck Labash, and Ashwin Gopinath. Reflexion: an autonomous agent with dynamic memory and self-reftection. ar preprint arXiu:2303. 11366, 2023.
KaShun Shum, Shizhe Diao, and Tong Zhang. Automatic prompt augmentation and selection with chain- of-thouuhh from labeled data, arXiv preprint arXiv:2302.1882 12822, 2023.
Alexey Skrynnik, Anton Andreychuk, Maria Nesterova, Konstantin Yakovlev, and Aleksandr Panov. Learn follow: Decentralized lifelong multi-agent pathfinding via planning and learning. arxiv preprint arXiv:2310.01220 2023.
Roni Stern, Nathan R. Sturtevant, Ariel Felner, Sven Koenig, Hang Ma, Thayne T. Walker, Jiaoyang Li, Dor Atzmon, Liron Cohen, T. K. Satish Kumar, Roman Barták, and Eli Boyarski. Multi-agent pathfinding: Definitions, variants, and benchmarks. In Proceedings of the Twelfth Annual Symposium on Combinatorial Search (SoCS), pp. 151-159. AAAI Press, 2019.
DiJia Su, Sainbayar Sukhbaatar, Michael Rabbat, Yuandong Tian, and Qinqing Zheng. Dualformer: Controllable fast and slow thinking by learning with randomized reasoning traces. arXiv preprint urXiv:2410.0900 2024.
Pavel Surynck, Ariel Felner, Roni Stern, and Eli Boyarski. Efficient SAT approach to multi-agent path finding under the sum of costs objective. In 22nd European Conference on Artificial Intelligence (ECAI), volume 285 of Frontiers in Arlificial Intelligence and Applications, pp. 810-818. IOS Press, 2016.
13

---

Published in Transactions on Machine Learning Research (06/2025)
Shuhan Tan, Boris Ivanovic, Xinshuo Weng, Marco Pavone, and Philipp Krachenbuchl. Language conditioned traffic generation. arXiv preprint or arXin:2307.009) 2023.
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaci, Nikolay Bash- lykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, Dan Bikel, Lukas Blecher, Cristian Canton- Ferrer, Moya Chen, Guillem Cucurull, David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Brian Fuller, Cynthia Gao, Vedamuj Goswami, Naman Goyal, Anthony Hartshorn, Saghar Hosseini, Rui Hou, Hakan Inan, Marcin Kardas, Viktor Korkez, Madian Khabsa, Isabel Kloumann, Artem Korenev, Punit Singh Koura, Marie-Anne Lachaux, Thibaut Lavril, Jenya Lee, Diana Liskovich, Yinghai Lu, Yuning Mao, Xavier Martinet, Todor Mihaylov, Pushkar Mishra, Igor Molybog, Yixin Nie, Andrew Poulton, Jeremy Reizenstein, Rashi Rungta, Kalyan Saladi, Alan Schelten, Ruan Silva, Eric Michael Smith, Ranjan Sub- ramanian, Xiaoqing Ellen Tan, Binh Tang, Ross Taylor, Adina Williams, Jian Xiang Kuan, Puxin Xu, Zheng Yan, Tlyann Zarov, Yuchen Zhang, Angela Fan, Melanie Kambadur, Sharan Narang, Au- rélien Rodriguez, Robert Stojnic, Sergey Edunov, and Thomas Scialom. Llama 2: Open foundation and fine-tuned chat models. CoRR, abs/2307. 0092889 2023. doi: 10.48550 ARXIV 2307.09228. URL bttps://doi... http///d..orr//////// 48550/805iii 2307 09288.
Karthik Valmockam, Matthew Marquez, Sarath Sreedharan, and Subbarao Kambhampati. On the planning abilities of large language models a critical investigation. arXiv preprint orXiv:2305.1571. 2023.
Karthik Valmeekam, Matthew Marquez, Alberto Olmo, Sarath Sreedharan, and Subbarao Kambhampati. Planbench: An extensible benchmark for evaluating large language models on planning and reasoning about change. Advances in Neural Information Processing Systems, 36, 2024a.
Karthik Valmeekam, Kaya Stechly, and Subbarao Kambhampati. Lims still can't plan; can Irms? a prelim- inary evaluation of openai's ol on planbench. arXiv preprint XxXx:2409.13375 2024b.
Yen-Jen Wang, Bike Zhang, Jianyu Chen, and Koushil Sreenath. Prompt a robot to walk with large language models. arXiv preprint orXiv:2309.0000 099699 2023a.
Zhenhailong Wang, Shaoguang Mao, Wenshan Wu, Tao Ge, Furu Wei, and Heng Ji. Unleashing cognitive synergy in large language models: A task-solving agent through multi-persona self-collaboration. CoRR, 0t5/23007.03000 2023b. 2307.0538
doi: 10.48550/ARXII ww..XII...30.0000 2307.05300000 URL https: oeeeiiorrr111. 10. 48550/arXiv.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed H. Chi, Quoe V. Le, and Denny Zhou. Chain-of-thought prompting clicits reasoning in large lan- guage models. In NewrIPS, 2022. URL http://papers wwwpeerrrr.iis........e....e cwwpaper_ppppppcceeccccccee. waarrfffleeeppppeeeeeeeee haapperr/222//aaa/ 04500911554eeff44555f177711113.1
Abstract-Confereemn html.
Wenshan Wu, Shaoguang Mao, Yadong Zhang, Yan Xia, Li Dong, Lei Cui, and Furu Wei. Mind's eye of Ilms: Visualivattion-f-thouggg elicits spatial reasoning in large language models. In The Thirly-eighth Annual Conference Neural Information Processing Systems, 2024.
Jian Xie, Kai Zhang, Jiangjie Chen, Tinghui Zhu, Renze Lou, Yuandong Tian, Yanghua Xiao, and Yu Su. Travelplanner: A benchmark for real-world planning with language agents. arXiv preprint arXiv:2402.01632 01622, 2024.
Chengrun Yang, Xuezhi Wang, Yifeng Lu, Hanxiao Liu, Quoc V Le, Denny Zhou, and Xinyun Chen. Large language models optimizers. arXiv preprint arXiv:2309.08.4 2023.
Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting in language models. arXiv preprint ar (xX6:22100000222 2022.
Seonghyoon Ye, Hyconbin Hwang, Sohee Yang, Hyeongu Yun, Yireun Kim, and Minjoon Seo. In-context instruction learning. Xix preprint ar Niv:230.. 14691, 2023.
14

---

Published in Transactions on Machine Learning Research (06/2025)
Hongxin Zhang, Weihua Du, Jiaming Shan, Qinhong Zhou, Yilun Du, Joshua B Tenenbaum, Tianmin Shu, and Chuang Gan. Building cooperative embodied agents modularly with large language models. arXiv preprint arXiv:2307.02485 2023.
Huaixiu Steven Zheng, Swaroop Mishra, Hugh Zhang, Xinyun Chen, Minmin Chen, Azade Nova, Le Hou, Heng- Heng-Tze Cheng, Quoe V Le, Ed Chi, al. Natural plan: Benchmarking llms on natural language planning. arXiv preprint ar Xiv:24400 (tl:2240600420, 2024.
A Complete Prompts
You are a decision-maker warehouse system that is running as a 4-connected grid-based multi-agent path finding system of [[Map Description]]- You will be provided with the current scenario in which you need to choose actions for each agent, ie., the detailed information that provides where the obstacles are, together with each agent's current location and goal locations. The objective to minimize the time of the agent who arrives at its goal location at the latest while keeping no agents from colliding with each other at any timestep. You only need consider collision between two agents located in the same cell after each move. On each timestep, you could choose one action from moving up, moving down, moving left, moving right, and staying without moving. current timestep also look ahead to few timesteps
You should lry to avoid collisions not only is important to avoid future collisions.
Remember that avoid a collision, normally, only one agent needs to change their action from original action. Nevertheless, your job is not to generate whole path but to do it step-by-step, and the information on whether a specific action is valid or not provided in each single step. Remember that the given action based the obstacles, the available action will not change if the agent chooses to stay the same location. You only need to give single-step action for each agent to follow; do not give more steps until tell you to. First, give your solution in the moving in a direction that is not towards its goal. (This is not the actual scenario, but an example of the desired output format. You will be provided with the actual scenario later):
format follows, with some explanation if the agent not moving
Step 1:
Agent
Current: (1,0)
Goal: (1,0)
Move: Stay, as it has already reached its goal.
Agent 2:
Current: (5,4)
Goal: (5.6)
Move: Up to (5,5)
Agent 3:
Current: (0,7)
Goal: (6,4)
Move: Right to (1,7)
Then, validate your solution by listing the coordinates of the agents after move and check there is any pair of agents that have the same coordinates. If there is collision by mistake, regenerate another solution immediately and validate again by listing the coordinates all the agents until you get a collision-free solution. Finally, end your output with your validated solution in new paragraph with the format of sequence of [[Agent id]]: [[Coordinate]].
Figure An example of the system prompt to specify the MAPF system and the objective. The text highlight in blue will be replaced by map description. For example, in room-32-32-4, the prompt will be 'rkom-like map with size 32*32:
In Fig. 6, we give our system prompt. Between different maps, the only thing that changed is the text highlighted in blue, and all other parts the same. We provide the user prompts in Fig. 7 and Fig. 8.
15

---

Published in Transactions on Machine Learning Research (06/2025)
Agent 1 is currently in (0.2), and wants to go to (3.1). Agent 2 currently (1,3), and wants to go to (2,0).
The map is follows, where "@' denotes cell with obstacle that agent cannot pass, and 7 denotes
empty cell that an agent can pass.
The bottom-left cell is (0,0) and the bottom-right cell is (31,0):
A...
In the next step:
Agent 1 can move ['stay at (0, 2);, 'right (1, 2), 'up to (0, 3)', 'down to (0, 1)]. Agent 2 can move ['stay at (1, 3)', 'left to (0, 3y,, 'right to (2, 3)', 'down to (1, 2)}.
Figure An example of the user prompt for describing the scenario. Text in blue is a scenario-specific prompt, while text orange is a map-specifie prompt. In the experiments on the emply map, only the first blue paragraph will be provided, and all text starting from the black paragraph removed because there no obstacles. The text in purple is the single-step observation (SSO) information.
[Success]]
Good job. Keep moving, In the next step:
Agent 1 can move ['stay at (0, 2),, 'right to (1, 2),, 'up to (0, 3),, 'down to (0, 1)']. Agent 2 can move ('stay at (1, 3)', 'left: (0, 3y, 'right to (2, 3)' 'down to (1, 2y] [[aalure]]]
You wrong. Agents (1,2), and (4,5) are colliding with each other. Please correct the current step, You are wrong. Agent 2,4 is colliding with obstacles. Please correct the current step.
Figure An example the user prompt starting from the second step. While here we demonstrate few options, only one of them, i.e, text in one color, will be provided to the LLM in one iteration.
B Token Length Grows
In Fig. 9, we show the average prompt length per agent per step, which includes both the input and the output. We found that with the growing number of agents, this average also growing, which means that the output length is growing faster than linear. This contributes to the fact that the more agents, the more complex the enviromment, and thus, the longer the explanation and the more iterations until correct plan is found. We also observe that in failing scenarios where the agents go back and forth, the token length is generally shorter, given that they did not run into the itcrative deconflict process, which takes a lot of tokens to solve.
C Comparison Between based Checker and LLM as Checker
In many domains, people are using LLM as the checker and provide feedback to another LLM, which serves as an actor. While we choose to use a rule-based checker because of its reliability and speed, here we provide some results on how bad the performance of an LLM- based checker could be. We randomly picked 50 different steps of information that need the chocker verify from our discussion history. And the succoss rate 76%, and the average time spent for each check seconds. This success rate is why we choose use the rule-based checker.
16

---

Published in Transactions on Machine Learning Research (06/2025)
002
803
Average Tokens per Agent Slep
803
202
102
Number Agents
Figure Average token length per agent step on success scenarios.
D
Complete Failing Example
While due to space limits, have only provided part of the example of the symmetry breaking examples in the main paper, here provide the full example in Fig. 10 on the corresponding step example of what will happen in one step of LLM response.
E
Case Study on GPT-ol-preview
In the main paper, we showed that the model of (GPT-)ol-previe) has a worse performance than the previous GPT-4-turbo. To study this anomaly, provide study here.
As shown in Fig. 11, compared to the previous version, GPT-ol-preview now learns to explicitly try to find an alternative route, and also, it now learns to use its previous history more strategically. After the model has found out that moving right is probably not helpful to him, it will not try to go right again. However, this making the result worse, given the current capability of the model is not strong enough. We observe that while at location (1, 17), agent could have moved up, GPT-ol-preview still chose to go back to the left. This fails meet the motivation of trying find an alternative path when meeting an obstacle. It is noteworthy that after a retry, it chooses move up and end up in successful final plan. Similar scenarios happens which leads to the improvement in Table. 11, which shows that GPT-ol-preview has the capability of at least matching the performance of the previous model, but the current result is coming from the randommess of LLMs. Also, this opens the potential for future research to study how to automatically integrate the regeneration process when provided with a more advanced checker. This checker would need go beyond merely assessing the final output, like the current checker, and instead evaluate the entire reasoning process. The checker should be able predict whether the current explanations are likely to lead to failure in future steps, rather than simply determining if the current step is correct. This aligns with evaluating the Q" value in Markov decision process, where π represents the generation policy of the large language model (LLM). Unlike V*, which evaluates the current state based on an optimal policy, Q" would allow the model lo assess whether the current action will result. in long-term success or failure in tasks such as MAPF. For instance, the checker should recognize that while the agent could theoretically chooses move left (0, 17) at step 6, the modcl's policy will not opt for this, indicating the need for regeneration at this step rather than later. It also noteworthy that even when large reasoning models (LRM) like GPT-ol-previee have success at some point, it will also introd much
move back to (1, 17) later,
17

---

Published in Transactions on Machine Learning Research (06/2025)
Step 1: Agent
Current: (0,2)
Goal: (3,1)
Move: Right to (1,2)
Agent 2:
Current: (1,3)
Goal: (2,0)
Move: Down to (1,2)
After the move, the coordinates of the agents are:
Agent 1: (1,2)
Agent 2: (1,2)
There is collision between Agent 1 and 2. will regenerate another solution immedialely.
Step 1 (Regenerated):
Agent
Current: (0,2)
Goal: (3,1)
Move: Down to (0,1)
Agent 2:
Current: (1,3)
Goal: (2,0)
Move: Left to (0,3)
After the move, the coordinates of the agents are:
Agent 1: (0,1)
Agent 2: (0,3)
There is no collision. Here is the validated solution:
Agent 1: (0,1)
Agent (0,3)
Figure 10: The output from GPT-4-turbo for the symmetry breaking example in Fig. 3b.
longer inference time and make it even harder to deploy in the real world. We also provide another example in Fig. 12, where GPT-ol--reviee has also shown its reasoning of trying one step, and going back. However, this example goes back directly becanse it sces no option to go to the goal location after the detour. This is one of the examples that LLM still fails even after we incorporate the human checker the middle because it still does not have strong capability in path planning.
18

---

Published in Transactions on Machine Learning Research (06/2025)
<Assistant>>
Step 5:
Agent 5:
Current: (0,17)
Goal: (0,23)
Move: Right to (1,17), aiming to find path upwards since moving up is blocked.
<User>
Keep moving. In the next step,
<Assistant>
Charling new routes...
Agent 5 is mapping out new poths lowards (0,23). Moving left from (1,17) could be viable, but obslacles might alter their course. Inderessen her own challenges and adjusting trajectory.
Step 6:
Agent 5:
Current: (1,17)
Goal: (0,23)
Move: Left to (0,17)
<User>
Keep moving. In the next step, <Assistant>>
Step 7:
Agent 5:
Current: (0,17)
Goal: (0,23)
Move: Stay at (0,17), as moving right doesn't help and moving up is blocked.
Figure 11: An example of part of the output from GPT-ol-preview model. The main difference compared to previous model in the reasoning is highlighted in red. Italics are the part shown as the thought of CPT-ol-preview in the web version.
19

---

Published in Transactions on Machine Learning Research (06/2025)
<Assistant>
Step 8:
Agent 3:
Current: (17,5)
Goal: (17,1)
Move: Up to (17,6)
Explanation: Moving up find path that allows decreasing the y-coordinate towards the goal.
<User>
Keep moving. In the next step, Assistant>
Step 9:
Agent 3:
Current: (17,6)
Goal: (17,1)
Available moves: [ssaay at (17,6)', 'right to (18,6), 'up to (17,7)', 'down to (17,5))
Move: Down to (17,5)
<User>
Keep moving. In the next step,
<Assistant>>
Step 10:
Agent 3:
Current: (17,5)
Goal: (17,1)
Available moves: [ssaay at (17,5)', 'left to (16,5), 'right to (18,5), 'up to (17,6))
Move: Stay at (17,5)
Explanation: No available moves bring Agent closer to its goal without moving away.
Figure 12: Another example of part of the output from GPT-ol-preview model.
20


Reviews:
[{"review_id": "gnWSxgy9G1", "reviewer": "Reviewer_Fbb4", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The authors discuss three key reasons why LLMs have not succeeded in solving MAPF problems:\n\nCapability to understand the scenario: The authors find that LLMs cannot fully comprehend the MAPF scenario, especially the information about the obstacles in the environment. Providing the map information through text-only descriptions, either listing the obstacle coordinates or describing the map using symbols, does not help the LLMs understand the problem.\n\nContext length limit: MAPF problems can involve a large number of agents, leading to long input sequences that exceed the context length limit of current LLMs. The authors observe that the number of tokens used grows non-linearly with the number of agents, and they have to restart the LLM frequently, causing it to forget previous information.\n\nReasoning capability: The authors identify that LLMs lack the necessary reasoning capability to effectively coordinate the movement of multiple agents and avoid collisions. While LLMs can follow simple instructions to move in a certain direction, they struggle with the complex reasoning required to deconflict the paths of all agents.\n\nThe authors discuss potential research directions to address these limitations, such as improving the capability of LLMs to handle long contexts, enhancing their reasoning abilities, and leveraging multimodal inputs that combine language and image information to better understand the MAPF scenario.\n\nAdditionally, the authors highlight other challenges in using LLMs for MAPF in real-world applications, such as the need for solution quality guarantees and the high latency associated with LLM-based approaches. They suggest that researchers from different backgrounds, including classic planning methods and reinforcement learning, could contribute to advancing the use of LLMs for MAPF.\n\nIn conclusion, the paper presents a comprehensive investigation into the limitations of using LLMs to solve MAPF problems and provides a detailed breakdown of the key challenges that need to be addressed. The authors hope their work can serve as a building block for future research in applying foundation models to the domain of multi-agent planning.\n\nWeaknesses\nTo strengthen this section, I suggest further elaboration on this point by acknowledging that while the evaluation focuses on simple prompts, exploring the impact of more advanced prompts could provide valuable insights into the system’s scalability and performance potential.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The study examines large language models (LLMs) in addressing multi-agent path finding (MAPF) challenges. LLMs show success in solving MAPF on empty maps but struggle with obstacles. Directly using LLMs for MAPF lacks success due to understanding limitations, context length, and reasoning challenges. Addressing these limitations and other real-world challenges is crucial for advancing LLMs in MAPF applications. The paper aims to guide future research in this area.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "In Section 2.3.2 Results and Section 3 Causes of Failures, certain phrases such as \"unclear\" and \"not stated\" could be rephrased to adopt a more constructive and research-oriented tone. Instead of stating that aspects are unclear, they could be described as requiring further clarification, open to interpretation, or presenting an opportunity for deeper analysis. Similarly, rather than indicating that something is not stated, it could be framed as yet to be explicitly defined, providing room for discussion or presenting an opportunity for future research.\n\nThese adjustments would enhance the readability of the paper and encourage further exploration rather than simply highlighting gaps. Adopting this approach would provide a more positive and forward-looking perspective for the reader.\n\nAdditionally, incorporating a comparison with existing MAPF plans could be considered for further analysis, though this is merely a suggestion rather than a recommendation.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "nfKzmi7I07", "reviewer": "Reviewer_xdjV", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper is reporting a negative result. One possible positive outcome of a negative result is a surprise: within a class of problems where a method has usually worked, there is an unexpected instance where it does not. I’m not personally surprised an LLM is not directly capable of solving a maze, nor does the article clearly make that claim.\n\nAnother way a negative result can be useful is preventing other researchers from needlessly repeating the same experimental idea. This utility is proportional to how well the obvious ideas are covered, and how much interest there is in the problem. The authors do try a range of things, drawing from existing literature.\n\nAs the authors also point out, the lack of success could also be considered a motivation for researchers to consider this a challenging problem that may spur development.\n\nHowever, those two benefits are in conflict with each other. If people are already (potentially) looking at this so that it’s worth presenting the results and preventing duplication, then it’s not clear people need to be motivated to look at the problem. But if this is a challenging problem that not enough people are looking at, then showing the obvious things don’t work is not as useful on its own. As things are written, the article does seem to be presenting both of these, and I think it would be stronger to argue for only one (and easier to justify those claims).\n\nAdditionally, while the authors did try a number of different variations, it’s not clear to me that it’s reasonable to consider the space of obvious solutions to be covered well, when LLMs are currently an extraordinarily active topic of research for a broad range of problems. This applies both to methods of using LLMs, through the discovery of more generally effective prompting schemes, as well as LLMs themselves, where drastic improvements in context length could solve some of the pathfinding failures the authors note might be (partially) caused by lack of history.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This article examines the ability of current LLMs to directly produce plans for single-agent and multi-agent pathfinding problems. It uses a set of publicly available four-connected grid-based pathfinding problems, and uses a number of different LLM arrangements to navigate to the goal location through the use of prompts and answers. The authors give experimental results showing an LLM setup can solve simple pathfinding problems, but the success rate for a variety of setups decreases to total failure as the pathfinding difficulty increases.. The authors give some analysis looking at different types of problem difficulty, prompts, multimodal input, different LLMs, and the effects and constraints of context length.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Section 1\n“MAPF is a unique problem in multi-agent coordination, so it is challenging …”\nAuthors should expand on what is unique. For example, what is a notable difference from cooperative multiplayer games?\nAlso, challenging doesn’t follow from uniqueness. This sentence needs some care and re-wording.\n\n“On the other hand, path planning is one of the easiest parts of planning”\neasiest in what context and in what sense? what are the other parts?\n\nSection 2.2\n“Instead, it breaks down the whole planning task into smaller singler-step tasks”\nThe authors do also explore a setup more like chain-or-thoughts (rhe one-shot setup). Rather than saying SBS is different, this paragraph would be a good spot to note the authors look at both. OS should be introduced here regardless, as it shows up soon after in the Table 1 results. The paragraph in 2.3 “It has been shown that a step-by-step generation is better in many reasoning-related tasks …” should probably be moved here, as part of the discussion of the general experimental setup.\n\nSection 2.3\nThe results in Table 1 and Table 2 present the binary success criteria. This is reasonable for simplicity. However, less-processed results should also be included: what do the results look like in terms of solution length and single-step failures (replanning events)?\n\nFigure 3: explain what the authors mean by symmetry breaking here: there are no other mentions of symmetry in the paper.\nCollisions at (2,1) and (1,2)?  For agent 1/agent 2 the paths [R/D] and [D/R, R/D, R/D] both lead to collision, and at different locations. This is possibly related to the question of symmetry above, but as noted right above, there is no discussion of specific handling of rotations/flips.\n\n“We observe that for smaller-scale problems that have fewer agents, GPT-4 can successfully generate valid solutions. However, GPT-4 fails to generate valid solutions”\nElsewhere, the authors have a distinction between valid and successfully generating a solution with few enough steps. So in these cases here, do the author mean valid, or successful within the 3*optimal condition?\n\nSection 3.1\n“ in scenarios that are successfully solved, this average is 1.5”.\nWhat is the ratio in the problems where the LLM agent is not successful?\n\n“LLMs can mostly succeed in scenarios that do not need a lot of waiting, and in most steps, they only need to go in the two directions aligned with the goal’s direction”\nThe clause about direction is separate from and does not follow from the ratio argument. It should separately justified with data.\n\n“This lack of reasoning capabilities is usually solved with tool use in other domains, but MAPF itself is hard because MAPF requires the capability of path finding in a complex map and avoiding collisions between all pairs of agents strategically and efficiently.  …”\nThis paragraph is in my opinion making an unjustifiably broad claim, and I would suggest weakening it. The most obvious way to apply a tool doesn't work, but that doesn't necessarily mean that the hardness is a fundamental feature of the problem. For example, having a complete plan, in a similar way to SBS,  seems like it would allow for a non-solving collision-checking tool.\n\nTable 3. Link GO and GO+SSO to the previous discussions. GO+SSO is what was used for Table 1 and 2?  If so, possibly consider renaming GO+SSO to be OS to match past experiments, and maybe GO to be OS-SSO?\n\nSimilar for Figure 5. How do TOM and TOO relate to previous experiments? IIt seems like they must be TOM: the correct answer should be obvious in the caption and text\n\n— smaller issues —\n\nSection 2.3.2 “Based on our results on single-agent path planning, we believe there is a possibility of generating a plan, regardless of optimality, for MAPF.”\nI am unsure what the authors are trying to convey to the reader here: suggest either dropping it, or rephrasing it if the authors believe it is conveying something important.\n\nSection 2.3.3 “While it is unclear how well LLMs can solve MAPF problems”\nWhy is it unclear at this point in the paper? One possibility is that this statement is obvious (and unnecessary) readers haven't done the experiments and the paper hasn't given results. Another possibility is that the authors believe the readers should be unsure at this point: if so, that wasn't clear to me, and the authors need to make that expected reason clear.\n\nSection 3.1 “More specifically, LLMs are guaranteed to tell whether”\nnot guaranteed?\n\n“We also observe that the GPT-4-8k model takes more iterations than the latest GPT-4-turbo\nmodel. This could either contribute to forgetting earlier information or to the improved capacity of the new model.”\nWhat is contributing to forgetting? Please rephrase the second sentence.\n\nSection 4\n“LLMs can solve small problems simply through prompting and discussing what is stopping them from solving larger scenarios”\nSuggest re-phrasing this is a weaker statement, e.g. “... and discussing some difficulties LLM have when solving larger scenarios”.\n\n“While we are unclear on how such things … will be a very challenging but meaningful direction… we want to remind them to keep looking …”\nSuggest softening some of the wording here, using could instead of should, and phrasing in terms of the authos believing something to be a promising direction. There is something slightly awkward about saying \"we are unclear on how\", and then directing researchers in very specific directions. Or, as an alternative, just drop text from \"Furthermore ...\" onwards: there's no need to reach so hard for future work, it is mostly speculative.", "broader_impact_concerns": "n/a", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "k2qq2jJzzu", "reviewer": "Reviewer_TpMx", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "In general I found the paper to be well written (minor fixes on wording and such are listed below), but fundamentally, the paper explores what I feel to be a fairly inappropriate line of exploration. It should be obvious that LLMs cannot do the long-sequence reasoning required for complicated MAPF problems, and unless this is surprisingly not the case, I fail to see the merit in running evaluations to confirm this hypothesis. To put it analogously, I don’t think LLMs are capable of computing the mean of a large set of floating-point numbers. It would be surprising and worth exploring if this were not the case, but I don’t believe a paper is warranted just to establish that LLMs failing at large-scale computation of the mean.\n\nThe title of the paper is provocative: ``_Why_ Solving MAPF with LLMs has not Succeeded Yet’’. Such a bold statement requires similarly bold evidence, but I found the three reasons provided (cf. Section 3) to be largely surface level and kind of obvious. LLMs are doing token prediction and not reasoning, and it’s obvious that tasks dedicated to complicated reasoning would be something that they struggle to handle. This all seems to step from a position of “hoping LLMs work” for this setting (cf last sentence on pages 2 and 4), but the very premise doesn’t make sense. If we are in such a structured environment where collisions are trivially detectable, then why would we ever turn to a large set of weights to only maybe compute the right answer part of the time? “Current heuristic-based algorithms like CBS can solve all the scenarios tested in the paper in less than 0.1 second” <— this should be a clear indication that turning to LLMs for solutions is a losing prospect.\n\nThe authors have clearly explored a wide variety of angles to try and have LLMs auto-complete their way to a MAPF solution. It’s definitely a positive sign that multiple things were attempted (e.g., range of maze types/size and the different input forms found in Figure 5). And as far as I can tell, the evaluations across these options are done correctly. The details included in the appendix are also nicely thorough.\n\nHowever, I ultimately feel that the motivation of the work is on shaky ground, and it’s not something the readership of TMLR would be compelled to know about.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors focus on the task of solving traditional MAPF problems with LLMs through various prompting techniques, and reporting on the results that they find. The authors found that state-of-the-art LLMs are capable of producing solutions for the easiest of MAPF tasks (e.g., single agent in rooms without obstacles), but fail to generalize to anything of reasonable size.\n\nThere are three issues raised by the authors as potential sources for the poor performance: (1) lack of LLM understanding; (2) limits on the context length; and (3) lack of reasoning capability.\n\nFinally, the evaluations to demonstrate the behaviour cover a range of LLM models, prompt styles, and benchmarks.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "No", "audience_explanation": "", "requested_changes": "I have a hard time knowing what to suggest, as my core criticism with the work isn’t just something a revision can fix. I suppose that one thing I might recommend to the authors is to take the insight and expertise they clearly have in the MAPF field, and apply it to novel / meaningful settings that include LLMs. Can they find suboptimal parts of solutions? Can they explain existing MAPF plans? Can they be used to synthesize programs for searching or heuristics? Etc. These are avenues in the same ballpark that don’t rely on winning the horse race against well-established and efficient methods.\n\nAside from that major suggestion, these are the minor things I noticed while reading the paper (as mentioned previously, it was otherwise extremely well written).\n\n## Minor fixes\n\n- There are some references that need fixing. The ones I’ve noticed include…\n  - First sentence of 2.3.2\n  - Question mark at the bottom of pg 9\n\n- Start of the intro needs to be updated — it’s been more than a year since ChatGPT has come out.\n\n- Not sure what you meant by “overcooked” on the first page\n\n- At the end of 2.2, you should explain what is meant by “getting a rate limit error”. I think I know what you mean (being restricted by the API call limits on the LLM service you use), but this should be elaborated on.\n\n- The use of “Besides, …” to start a sentence (twice in a row on pg 9) is too informal.\n\n- Not sure what “stably” means in the second sentence of the Conclusion section.", "broader_impact_concerns": "I don’t feel that there are any broader impacts or ethical concerns that the authors need to address with this line of work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "iUnG71pq9O", "reviewer": "Reviewer_FMAf", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n1. The proposed benchmark is novel and will inspire future works to evaluate LLMs' planning capabilities, especially in a multi-agent scenario.\n\n2. The provided causes might be helpful for other planning and spatial reasoning benchmarks.\n\n**Weaknesses**\n\n1. Only simple prompts are evaluated; it is unclear whether advanced prompts can drastically improve performance. (Please refer to requested changes 1-4)\n\n2. The three causes have been discussed for general planning problems in the literature. It seems that there are no unique insights specific to multi-agent or path planning problems. The unique insights beyond these general points should be discussed. For example, the requested changes. I hope the authors can discuss other unique insights. (Please refer to requested changes 50)\n\n3. (Multi-agent) pathfinding belongs to the category of spatial reasoning in LLM literature. More relevant literature should be discussed.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "1. This paper proposes using an LLM to directly solve MAPF, providing a new benchmark to evaluate LLMs' planning and spatial reasoning capabilities.\n   \n2. Three causes of failure are presented and analyzed.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. In the single-agent scenario, only a simple prompt is used. It is unclear whether an advanced prompt (e.g., verbal RL [Ref A]) would improve performance.\n\n2. In the multi-agent scenario, the prompt may become long and reach the context limit. Is it possible to model each agent with one LLM and enable communication among LLMs (e.g., [Ref B])? Will this alleviate the issue?\n\n3. It is unclear if an advanced spatial reasoning prompt (e.g., [Ref C]) will help in this task. Could it improve the understanding of obstacles?\n\n4. Multi-agent pathfinding can be solved by CBS, and GPT is familiar with this algorithm. How will GPT behave if we prompt it to solve the problem using CBS?\n\nI strongly encourage the authors to include the methods mentioned above and conduct ablation studies.\n\n5. Compared with traditional spatial reasoning, the multi-agent setting is novel. The paper could benefit from a discussion on the difficulties GPT faces in understanding multi-agent scenarios compared with single-agent scenarios. When the number of agents increases, what challenges arise beyond the context length limit?\n\n[Ref A] Reflexion: Language Agents with Verbal Reinforcement Learning\n\n[Ref B] CAMEL: Communicative Agents for \"Mind\" Exploration of Large Language Model Society\n\n[Ref C] Mind’s Eye of LLMs: Visualization-of-Thought Elicit Spatial Reasoning in Large Language Mode", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The submission elicited a clear split among reviewers. Reviewers FMAf and Fbb4 praised the paper’s comprehensive experimental regimen and its systematic identification of why off-the-shelf LLM prompting fails on multi-agent pathfinding (MAPF). They welcomed the work’s potential to seed a new planning benchmark and felt their constructive feedback—on tone and minor analyses—was satisfactorily addressed. In contrast, Reviewers xdjV and TpMx found the negative results largely unsurprising given known LLM limitations and argued that the manuscript oscillates between diagnosing solver failures and proposing MAPF as a benchmark without sufficiently developing the latter narrative.

Despite these divergent views, the empirical methodology is solid, and the failure-mode breakdown will benefit the LLM evaluation community. At the same time, the benchmark proposition needs sharper articulation and balance. Accordingly, we recommend Accept with Minor Revision, with the following concrete edits to unify the paper’s framing and amplify its community impact:
- Sharpen Benchmark Framing
    - In the Abstract, Introduction, and Conclusion, explicitly state that the primary contribution is to establish MAPF as a standardized LLM evaluation domain—analogous to BlocksWorld and PlanBench—rather than to propose new solver algorithms.
    - Clarify in the title or subtitle that this is a “benchmark proposal with failure-mode analysis.”
-Reorganize Narrative Balance
    - Streamline the detailed failure-mode sections (Sections 2–3) by condensing repetitive solver-failure anecdotes and relocating some examples to an appendix.
    - Elevate a dedicated “Benchmark Protocol” subsection that outlines problem instances, evaluation metrics, and minimal dataset splits for community adoption.
- Consistency of Motivation and Claims
    - Ensure the motivation statements consistently emphasize benchmark goals rather than only empirical “why LLMs fail.”
    - Reconcile any instances where the manuscript vacillates between “discovering failure causes” and “proposing future benchmarks.”
- Minor Tone and Wording Tweaks
    - Adopt more constructive phrasing (e.g., “presents an opportunity for deeper analysis” vs. “unclear”).
    - Soften absolute claims and incorporate the suggested language edits from Reviewer Fbb4.
Decision: Accept (poster)