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

## Abstract

Abstract With the explosive influence caused by the success of large language models (LLM) like ChatGPT and GPT-4, there has been an extensive amount of recent work showing that foundation models can be used to solve a large variety of tasks. However, there is very limited work that shares insights on multi-agent planning. Multi-agent planning is different from other domains by combining the difficulty of multi-agent coordination and planning, and making it hard to leverage external tools to facilitate the reasoning needed. In this paper, we focus on the problem of multi-agent path finding (MAPF), which is also known as multi-robot route planning, and study the performance of solving MAPF with LLMs. We first show the motivating success on 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.

## 1 Introduction

In the past year 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 combining LLMs with different ways of prompting can help solve problems that have some aspects of reasoning, including examples from logical problems (Yao et al., ; Liu et al., ) to controlling a robot dog without finetuning (Wang et al., ).

Motivated by the success of LLMs, some recent works studied the performance of LLMs on multi-agent problems and showed LLM can also help multi-agent coordination (Chen et al., ; Agashe et al., ). However, they barely cover multi-agent planning. 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 a group of agents from their respective start locations to their goal locations without collisions. MAPF can be used directly to formulate real-world applications like warehouse management (Sharon et al., ; Han & Yu, ), swarm control (Li et al., ), among others. In a typical warehouse scenario, around a thousand warehouse robots (agents) could be running simultaneously in one warehouse room (scenario), and each agent needs to plan its path, which could be as long as a hundred timesteps. Previous methods for MAPF can be classified into 1) classic methods like heuristic search and SAT (Sharon et al., ; Han & Yu, ), and 2) learning-based approaches that mostly use reinforcement learning (Sartoretti et al., ). MAPF is a unique problem in multi-agent coordination in that coordination is required within the planning, so it is highly challenging to facilitate the reasoning of coordination by using LLMs to generate useful high-level guidance combined with a low-level path planner to ensure the solution is valid, an approach that will be parallel to this taken in the setting of overcooked (Agashe et al., ). On the other hand, path planning is one of the easiest parts of planning, and constraints only concern obstacles and moving continuity. Because of these unique challenges in the MAPF problem, it is unclear how good LLMs will be at solving MAPF.

Figure: Figure 1: An illustration of our workflow.
Refer to caption: extracted/5400803/figs/llm_workflow.png

In this paper, we propose to use an LLM directly to solve MAPF without any additional heuristic guidance from solvers or any additional training. We give 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 and provide error message to the LLM when violations occur, and iterate with the LLM until a valid solution is generated. We evaluate the performance of LLMs on the empty map, the room map, and the maze map, which are classic maps from the standard MAPF benchmark (Stern et al., ). 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 researchers 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.

## 2 LLMs for Multi-agent Path Finding

### 2.1 Preliminary

The multi-agent path finding (MAPF) problem is the problem of finding a set of conflict-free paths for a set of agents in a known environment while minimizing their travel times. Specifically, in this paper, we consider the same problem as (Stern et al., ; Li et al., ), which is a four-connected grid map, where each agent is given a start cell and a goal cell. A scenario is defined as the combination of the description of the map, which is the size of the map, indication of 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 conflict 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, i.e., minimize the time when the last agent arrives at its goal location.

Large language models (LLMs) like ChatGPT, Claude, and Gemini have at least tens of billions of parameters and are trained with extremely large amounts of data collected on the internet. With the number of parameters exponentially larger than the degree of freedom in small problems, LLMs have the potential to solve some easy problems in reasoning with certain prompts (Wei et al., ), and break down harder problems into smaller ones to get suboptimal solutions (Yang et al., ). When applying to MAPF, we hope LLMs can be an alternative model to the current MAPF reinforcement learning-based models without the need for any training. Unlike previous work with LLMs that solves the path-planning problem at the low level with existing heuristic solvers (Agashe et al., ), MAPF is unique because it is extremely hard to decouple the high-level coordination from the path-planning process. The coordination needed is the deconflict that happens in each step and each step only, which forbids the use of a single-agent planner that cannot take coordination into account. And without the decoupling, we cannot leverage a path planner like previous work has done to reduce the difficulty in the reasoning.

### 2.2 Methods

Figure: Figure 2: An example of the user prompt for describing the scenario. Text in blue is a scenario-specific prompt, while text in orange is a map-specific prompt. In the experiments on the empty map, only the first blue paragraph will be provided, and all text starting from the black paragraph is removed because there are no obstacles. The text in purple is the single-step observation (SSO) information.

Figure: Figure 3: An example of the user prompt starting from the second step. While here we demonstrate a few options, only one of them, i.e., text in one color, will be provided to the LLM in one iteration.

In this paper, we focus on using LLMs to solve the MAPF problem directly.
However, it is quite obvious that current ML models cannot be perfect solvers in their first trial, and we introduce a high-level conflict checker to ensure the plan generated by the LLM is valid. We inform the LLM about the mistake in the solution, if any. Unlike some previous works (Yao et al., ; Yang et al., ), our checker is not another LLM both because it is extremely easy 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. In this checker, we not only check for agent-to-agent collisions but also correct the LLM for any collision with the fixed obstacles. We do not provide any additional guidance on how the LLM should deconflict the solution but just describe the conflicts.

Following the common practice of LLMs, we build our workflow shown in Fig. 1. As existing learning-based approaches (Damani et al., ), we give LLMs stepwise local information and let the LLM choose the actions of agents step-by-step. This step-by-step (SBS) generation is different from the popular chain-of-thoughts idea (Wei et al., ) 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, so the LLM does not need to be fully correct before we can use some results from it. We start by giving the LLM the system prompt of becoming a solver for the MAPF problem. This part is fixed within each map, and different 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, so we provide a single-step observation (SSO) in the prompt by default. See Figure 2 for an example of the scenario description prompt. 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. See Figure 3 for an example of the iteration-wise user prompts. 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, i.e., treat the current agent locations as their starting point, whenever we got a rate limit error.

### 2.3 Experiment Results on MAPF Benchmark

Figure: Figure 4: 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 positions on the vertical axis indicate greater values.
Refer to caption: extracted/5400803/figs/flip_room.png

#### 2.3.1 General Experiment Settings

While we have introduced the high-level conflict detector, we define a solution generation to be successful if it does not fail because of any of the following:

- 1.
Fails to generate a plan whose number of steps is at most 3 times longer than 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.

Note that we do not consider any token limit error because allowing no more than 5 times in a single step guarantees that the message length in one step is within the token limit, and we already consider restarting at each step if the token limit is too long in our method.

By default, we are using the GPT-4-1106-preview model, also known as the GPT-4-turbo model, which is the state-of-the-art LLM that is publicly available. We set the temperature as $1.0$ and the seed as 42 (^1^11Note that we are testing using the API, where the behavior could be slightly different from the web version of GPT-4.). We show an example of our user prompt in Fig. 2 and Fig. 3, and an example of the complete system prompt in the appendix. We will describe how each variant will change from this default prompt.

Each setting in the experiment is tested on 5 different scenarios in the standard MAPF benchmark, each different in terms of the start and goal location combinations of the agents on a given map.

#### 2.3.2 Results

While it is unclear how well LLMs can solve MAPF problems, 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., ), which has no obstacles at all and only requires the agents to not collide with each other. The results are shown in Table. 1. We observe that for smaller-scale problems that has fewer agents, GPT-4 can successfully generate valid solutions. However, GPT-4 fails to generate valid solutions when there are more agents on the same map.

It has been shown that a step-by-step generation is better in many reasoning-related tasks, since it can guide the generated plan to create the chain of thoughts as a human rather than guessing a solution and then checking whether they are correct (Wei et al., ). However, it is not well-studied whether a step-by-step generation is also helpful in the planning since a complete plan will also require to be given in a step-by-step (SBS) way, and the LLM models need to decide every single step anyway. Therefore, we study a variant that generates the whole plan in one shot (OS) with the help of chain-of-thought prompts and show the comparison in Table. 1. We observe that one-shot (OS) generation fails to generate solutions even 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 room-32-32-1 map and the maze-32-32-2 map, which is shown in Fig. 4. The results are shown in Table. 1. In this case, we found that LLMs fail to generate solutions when the number of agents is already quite small, and that LLMs completely fail on the maze-32-32- map even with only 2 agents.

**Table 1: The success rate of solving MAPF with LLM on empty-8-8, room-32-32-4 and maze maps with varying numbers of agents (n).**
| Map | n | Success Rate (%) |  |
| --- | --- | --- | --- |
| OS | SBS |  |  |
|  | 2 | 10 | 100 |
| Empty | 4 | 0 | 100 |
|  | 8 | 0 | 100 |
|  | 16 | 0 | 60 |
|  | 2 | 10 | 100 |
| Room | 4 | 0 | 80 |
|  | 8 | 0 | 20 |
| Maze | 2 | 0 | 0 |

## 3 Cause of Failures

Because LLMs are evolving rapidly, it is unclear how long LLMs will still fail. Although our methods do not combine any external tools like low-level planning or external memory (Agashe et al., ), which could make LLMs much stronger, it is important for us to break down the failures and identify the cause of the failures so we can strategically choose the correct tools to overcome them in the future. We found that the cause of failing in MAPF 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., ). 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”. We observe that LLMs fail only once with 16 agents in the empty map because of consecutive failures in a single step, and all other times they fail because they use many more steps than they should. More specifically, we discovered that 77% of the failures occurred because the LLM agents began to oscillate in a specific area of the map, while the remaining failures were due to excessively long detours.

Based on our observations, we break down the reasons into three deeper parts from the perspective of natural language models: limitation from the model, understanding, and reasoning. For simplicity, we first discuss the lack of reasoning capability, which is common in many tasks.

### 3.1 Reasoning Capability

Figure: (a)
Refer to caption: extracted/5400803/figs/sym_breaking_1.png

Figure: Figure 6: The output from GPT-4-turbo for the symmetry breaking example in Fig. 4(b).

**Table 2: 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).**
| Model | n | Success Rate | Avg. Iterations |  |  |
| --- | --- | --- | --- | --- | --- |
| GO | GO+SSO | GO | GO+SSO |  |  |
|  | 2 | 80 | 100 | 2.7 | 1.6 |
| GPT-4-8K | 4 | 20 | 60 | 3.0 | 2.3 |
|  | 8 | 0 | 0 | N/A | N/A |
|  | 2 | 100 | 100 | 2.1 | 1.2 |
| GPT-4-128K | 4 | 60 | 80 | 2.7 | 1.4 |
|  | 8 | 0 | 20 | N/A | 2.4 |

In this paper, we focus on 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 a valid lower bound on the optimal MAPF solution), and in scenarios that are successfully solved, 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 directions aligned with the goal’s direction. LLM fails in other scenarios because they need path finding in complex environments. A simple example of the failure of path finding is shown in Fig. 5, where we have the classic symmetry-breaking example. We provide the input of the scenario information and the output of the first step in Fig. 3 and Fig. 6. We observe that while waiting for one 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 a total makespan of 6. This example shows that LLM does not understand what makespan is and how a solution is optimized for makespan.

On the other hand, when we look at the average number of iterations for prompts with both global obstacle observation in the first user prompt and single-step obstacle observations(GO+SSO) in Table. 2, it is still not very close to $1$ which means no iterations at all. This is because even if we have explicitly let the LLM deconflict the agents by listing all the coordinates of agents, it does not have the capability to check the answers itself without the use of external tools. More specifically, LLM cannot tell whether a list of tuples of numbers has any duplicates. This is similar to the fact that LLM cannot sort a list of numbers without step-by-step instructions, which we do not allow the LLMs to do because we still do not want the LLM to use too many tokens in a single step. We also observe that the GPT-4-8k model takes more iterations than the latest GPT-4-turbo model. This could either contribute to forgetting earlier information or to the improved capacity of the new model.

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. The coordination between agents is required in each step, and each step only. If we let the tool, in this case, a single-agent planner like A*, include the de-conflicting, the problem is already solved, while LLM did no help. On the other hand, the tools must know what kind of deconflict they need to do to add those constraints into the heuristic search algorithm. This paradox is making LLM with tool use in MAPF very hard.

To potentially increase the reasoning capability, we have also tried a list of tricks. These kinds of tricks include breaking the big paragraph into bullet-point style instruction, removing some ’useless’ instruction, adding a whole example for in-context learning, and using the theory of mind to guess other agent’s intuitions (Li et al., ). These tricks did not show any help in any scenarios, and even greatly harmed the performance of the GPT-4-8k model.

### 3.2 Context Length Limit

Because the underlying architecture of popular LLMs is transformers, which further rely on self-attention, a longer context in the input will significantly increase the computing complexity in the process. Therefore, in their training process, they set a maximum limit of tokens on the input and trained specifically on them. Current large language models released will also provide a context length limit, which is as long as 200K 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. However, recent studies have shown that long models like GPT4-turbo-128K are not a model whose capacity in 8K length also works when given a 128K-tokens input (^2^22https://github.com/gkamradt/LLMTest_NeedleInAHaystack). 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 thousand agents will require a total context length of $250(tokens/agent\ step)*50(steps)*1000(agents)=5M$ tokens, which is much bigger than the current limit. 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 number of tokens used grows non-linearly with regard to the number of agents due to the increasing number of iterations, and we have put the numbers in the appendix.

In table. 2, we show our results on the room map, and test with different GPT-4 models with different context lengths. 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.

### 3.3 Understanding Obstacle Locations

**Table 3: The success rate of different ways of inputting the map information to LLM on Room-32-32-4 map with different number of agents (n).**
| n\Success Rate | MM | TOO | TOM |
| --- | --- | --- | --- |
| 2 | 100 | 100 | 100 |
| 4 | 20 | 60 | 80 |
| 8 | 0 | 0 | 20 |

Figure: Figure 7: An illustration of the difference between multimodal input (MM), text that describes the whole map (TOM), and text that describes the obstacles (TOO).
Refer to caption: extracted/5400803/figs/MM_TOO_TOM.png

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 easy, understanding the map information is hard. Trained with publicly available text, LLM learns what a specific 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 to 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 to a lack of training data with related context about the information in the pictures or in a symbol-based input.

Because of this lack of information, our main prompt included guidance on what action could be taken in the current step to increase the success rate a little bit. In Table. 2, we provided the results of global observation (GO) only and the version with single-step observation (SSO) together. We discover that while global observation can also provide a good win rate with the help of our high-level checkers, it increases the average iterations in each step, and also fails in cases that could be successful with the help of SSO, which is killed by using much more total number of steps than it should. 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 of 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. 7, 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:

- 1.
A multimodal-based method MM where we use an image to give the picture of the map, and text to describe the problem and the scenario.
- 2.
A text-only method that describes the map by listing all the coordinates of the obstacles, named TOO.
- 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. 3. We found that with an image-based input, the results are even worse. For example, large models can only have a high-level idea that there is a wall in the middle area, rather than knowing there is a 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 path planning. Overall, in complex environments such as mazes and real-world city maps, LLMs 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.

## 4 Discussion

As we have shown in the previous section, there are three aspects that mainly limit the current capability of solving MAPF with LLMs. While there have been many works in the NLP that could solve one of them, e.g., extending the context length limit to up to 4M tokens or using a decentralized control, those methods will harm the reasoning capability and, therefore, are not preferable in our case.

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 discussing what is stopping them from solving larger ones.

Moving on, we believe the three reasons for failures can each independently relate to different research directions. Improving capability in a long context is already a popular direction in NLP, and there are also many papers 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 be potentially helpful for the reasoning in MAPF. Image generation models like stable diffusion (Rombach et al., ) have shown to be a strong tool in single agent planning(Janner et al., ). 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 the understanding of the obstacles, we believe more annotated data are needed to help foundation models connect the abstract description to concrete coordinate-level knowledge of where obstacles are. 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 such data online. Hopefully, such data could help foundation models able to know position encodings are specifically more important in problems related to planning. However, a challenge for fine-tuning a customized model is that popular open-source models have smaller context length, like 4K in LLAMA-2, and 32K for Mixtral 8*7b, which will limit their performance on MAPF.

Besides, although the success rate is one of the most important factors in measuring the performance of a solver, there are also other obstacles that need to be solved before using LLMs in real-world scenarios. First of all, success does not indicate anything about the solution quality. 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. And when the planning is getting harder, the success rate is 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. While we are unclear on how such things should be included, this will be a very challenging but meaningful direction. For potential researchers going in this direction, 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 a 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 state-of-the-art system-wise optimization like vLLM (Kwon et al., ) for LLAMA-2 (Touvron et al., ). 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 a list of factors like network connection and server availability. In our 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

### 5.1 LLM for Reasoning

Since the release of GPT-3, researchers have studied the effect of how they are performing on diverse sets of problems. Starting with failure in general tasks(Valmeekam et al., ), ideas like chain of thought (Wei et al., ), in context learning (Ye et al., ) have been shown to significantly improve the performance of LLMs in different tasks related to reasoning(Fu et al., ; Shum et al., ). A recent line of work has been introduced to use natural language as 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 (Shinn et al., ; Chen et al., ; Olausson et al., ), reasoning (Yao et al., ; Yang et al., ; Shinn et al., ), and reducing harmful information in LLMs (Ganguli et al., ). There is also a very popular line of work augmenting LLMs with external memory, belief, and tools. For example, Liu et al. () proposed to use LLMs to generate a PDDL description of the problem in classic planning benchmark domains like blocksworld and thermes. Mao et al. () used external memory to match the previous experience and shows that the underlying knowledge in LLMs can make a novel tool that is more powerful than before in autonomous driving. In this paper, we use our high-level checker as the only tool in the process, and we hope the reasons for failure could later help researchers choose external tools.

### 5.2 LLM for Multi-agent Systems

While there is extensive research on using LLMs for many different problems, there is little work that addresses the problem of LLM for multi-agent systems in the beginning. This is typically due to the context length limit that generally applies when the total number of agents is not too small. 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., ; Li et al., ), create dialogue-based games with LLM (Schlangen, ). Recent work has shown that dialogue between multiple agents can help accuracy and remove factual errors (Du et al., ; Wang et al., ). When it comes to solving problems related to multi-agent system, there are a few works that are more in the multi-robot system. Zhang et al. () and Mandi et al. () are two works that first extend LLMs to the domain, but they are limited to the scale of two to three agents. Chen et al. () studied whether using a more decentralized controller can help to solve the context length limit problem when the number of agents is higher. Agashe et al. () evaluate the overall multi-agent coordination capability in three different domains and show that with proper tools, LLMs can even outperform MARL algorithms. While they succeed in their domains, in this paper, we specifically look at the problem of MAPF, and we are showing the cause of failure in the MAPF problem because of its unique challenges in MAPF.

### 5.3 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 like autonomous warehouses. It has previously been solved with more classic methods like heuristic search algorithms (Sharon et al., ), rule-based algorithms (Han & Yu, ), and reduction-based algorithms (Surynek et al., ). While learning-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., ) 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., ) to follow guidance from classic methods in each step (Skrynnik et al., ). In this paper, we focus on using LLM, which is a neural-network-based approach but is not specifically fine-tuned for MAPF problems.

## 6 Conclusion

In this paper, we investigate the use of LLMs for solving the MAPF problem. We first show that LLMs could work in easy scenarios like a small number of agents in the empty map, while being unable to stably generate valid solutions when the problem gets harder. To make our work applicable to future models, we elaborate on the failures and show that they can be broken down into the problem of the context length limit of the model, the capability to understand and remember where obstacles are, and the capability of planning. We used extensive experiments to support our breakdown, and provided discussions on how the difficulties could be addressed by people with different backgrounds.

## 7 Impact Statement

This paper presents work whose goal is to express our position on how to advance the field of Machine Learning and Multi-agent Path Finding. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.

## Appendix A Complete System Prompt

Figure: Figure 8: 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 ’room-like map with size 32*32’.

In Fig. 8, we give our system prompt. Between different map, the only thing changed is the text highlighted in blue, and all others part are the same.

## Appendix B Token Length Grows

Figure: Figure 9: Average token length per agent step on success scenarios.
Refer to caption: extracted/5400803/figs/avg_token.png

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 is 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 environment, and thus, the longer explanation and more iterations until a correct plan is needed. We also observe that on failing scenarios where the agents are going back and forth, the token length is generally shorter, given that they did not run into the iterative deconflict process, which takes a lot of tokens to solve.

## Peer Reviews

confidence: 4
contribution: 1
initial_rating: 3
presentation: 3
questions: The authors can consider including baseline methods like heuristic search or SAT-based MAPF algorithms for comparison. Such comparisons would clarify whether LLMs bring any unique advantage to MAPF. Besides, they can evaluate the generated paths for metrics like makespan, and path length. Including these metrics could highlight the quality of LLM-generated solutions relative to optimal or near-optimal paths.
soundness: 2
strengths: Firstly, the paper is well-structured, and it clearly explains why LLMs may be suitable candidates for MAPF due to their reasoning capabilities and large contextual understanding. It conducts experiments on various MAPF benchmark maps, evaluating LLMs’ performance in different scenarios and identifying specific failure points. The paper’s breakdown of LLM limitations, such as reasoning and spatial understanding, provides useful insights for future improvements in LLM-based MAPF solutions. Different prompt styles and input representations (e.g., text-only, multimodal) are compared, contributing valuable insights into how prompt structure affects LLM performance.
summary: The paper investigates the use of LLMs for solving multi-agent path-finding problems(MAPF), focusing on moving multiple agents from start to goal locations without collisions. The study explores whether LLMs, without additional training or heuristic guidance, can effectively generate valid paths for agents in different MAPF scenarios, including simple and complex environments. 
Experiments reveal that while LLMs can solve straightforward MAPF cases with limited obstacles, they struggle with more challenging environments, often failing to generate collision-free solutions. The paper identifies three primary reasons for LLMs’ limitations in MAPF: lack of advanced reasoning, context length limitations, and difficulty understanding spatial map information. Based on these findings, the authors suggest directions for future work to address these limitations and improve LLMs' MAPF performance.
weaknesses: The paper does not compare the LLM-based approach with traditional MAPF algorithms (e.g., heuristic search, SAT, or reinforcement learning). Including baseline comparisons would provide a better understanding of how LLMs perform relative to established methods.
It also lacks visualizations of agent paths and collision instances, which would improve clarity and provide a more intuitive understanding of LLM performance. Success metrics focus on whether a solution is collision-free, with limited emphasis on solution quality (e.g., path optimality or efficiency). Detailed metrics would offer a clearer picture of LLMs’ efficacy in generating high-quality paths.

---

confidence: 4
contribution: 1
initial_rating: 1
presentation: 2
questions: 1. How do you justify that the proposed prompt method is the best approach and that its failure indicates no other prompting method can address the MAPF problem? How do you ensure the conclusions are generalizable beyond this specific scenario and prompt?
2. Given that the insights are common LLM limitations, not specific to MAPF, what is the unique benefit of this research? Are there distinct challenges in MAPF that differ from general LLM challenges, making any of the observations particularly relevant?
3. Why use LLMs for MAPF or even SAPF? The necessity is unclear, as these problems can be well-addressed using traditional analytical methods.
soundness: 1
strengths: - This paper addresses a unique application of LLMs to multi-agent coordination, specifically MAPF.
- The paper identifies general limitations of LLMs in multi-agent coordination tasks, with some illustrative failure cases.
- The discussion outlines the general challenges of using LLMs in MAPF and suggests broad areas for improvement.
summary: The paper explores the feasibility of using large language models (LLMs) for solving the Multi-Agent Path Finding (MAPF) problem. While LLMs have demonstrated success in various fields, this study examines their limitations in handling MAPF due to issues with reasoning capabilities, context length limits, and obstacle comprehension. Experiments on standard MAPF benchmarks show that LLMs perform well on simple scenarios but struggle as problem complexity increases. The authors conclude that current LLMs are insufficient for MAPF without additional improvements or hybrid systems integrating traditional path-planning methods.
weaknesses: - Given that these problems are well-addressed by analytical methods, could the authors elaborate on the concrete advantages of using LLMs for MAPF compared to existing analytical methods?
- As the findings primarily reiterate known LLM challenges (e.g., context limitations and reasoning issues) without introducing MAPF-specific insights or innovations. The relevance to MAPF needs to be clarified. The authors are suggested to highlight any MAPF-specific challenges or insights they discovered.
- The experiments are restricted to simple cases that may not generalize to real-world MAPF tasks, which undermines the strength of the study’s conclusions.
- The chosen prompt design lacks justification as the best approach for MAPF. Without alternative prompting methods or tuning strategies, it is unclear if the observed limitations are universal or specific to this setup.

---

confidence: 5
contribution: 2
initial_rating: 3
presentation: 2
questions: There are some serious concerns that I have pointed out in the previous section

## Limitations:

The methods used to obtain plans with LLMs are quite simple. It would have been better to have some more sophisticated methods (used in prior literature) to compare and show their failure modes. Just using LLMs for planning might not be a reasonable approach and probably that’s why many of the recent papers come up with more sophisticated methods (different roles with LLMs, decentralization, etc.)
soundness: 2
strengths: - This paper effectively highlights the current limitations of LLMs in multi-agent pathfinding (MAPF) domains through experiments conducted across environments of varying complexity.
- The authors provide an analysis of potential reasons behind LLMs’ challenges in effective planning.
- This work could serve as a valuable reference for future research directions in MAPF with LLMs.
summary: This paper addresses the challenge of multi-agent pathfinding using large language models (LLMs). The authors demonstrate that while LLMs have proven effective for single-agent planning and, to a certain extent, for multi-agent pathfinding in relatively simple environments, current LLM capabilities are inadequate for planning in more complex settings.
weaknesses: - The paper only addresses the limitations of LLMs in centralized planning paradigms. The authors claim to use the history of the agents as input in the prompts. Due to this, the context window limit is reached quite quickly when the number of agents is high. But since the environment is Markov, shouldn’t it be able to decide actions for the agents just based on their current states?
- The methods used to demonstrate the limitations of LLMs are relatively straightforward. Including comparisons to more advanced modular architectures, such as those incorporating memory modules and decentralized planners (e.g., [1, 2, 3]), would have strengthened the analysis—even though surpassing state-of-the-art classical planners is not the primary objective of the paper.
- Overall, the paper feels more akin to a research proposal than a definitive study; it identifies key challenges and proposes future research directions but lacks extensive experimental results demonstrating effective solutions.
- The authors suggest three possible reasons for LLMs' shortcomings in MAPF: reasoning limitations, context length constraints, and difficulty understanding obstacle locations. However, these challenges should also arise in single-agent scenarios, where the agent must similarly reason and interpret obstacles, yet LLMs perform well in those cases. Could the authors provide further insights by comparing single-agent and multi-agent tasks?

 References:

[1]: Building Cooperative Embodied Agents Modularly with Large Language Models. Hongxin Zhang and Weihua Du and Jiaming Shan and Qinhong Zhou and Yilun Du and Joshua B. Tenenbaum and Tianmin Shu and Chuang Gan. https://arxiv.org/abs/2307.02485

[2]: Nayak, S., Orozco, A. M., Have, M. T., Thirumalai, V., Zhang, J., Chen, D., ... & Balakrishnan, H. (2024). Long-Horizon Planning for Multi-Agent Robots in Partially Observable Environments. *arXiv preprint arXiv:2407.10031*.

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

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 2
questions: 1.  Would comparing to a wider range of baseline methods (other than just 0S and SBS) help substantiate the claim that LLMs are not good for MAPF problems?     
2.  Under Methods: “Following common practices of LLMs” what exactly are these?
3.  The authors mention giving the LLM “stepwise local information” what exactly does this mean?  (I assume it is related to the context window size issue?)
4.  The authors only give the LLM information to solve the “next step” and keep re-prompting until the LLM provides a solution with no conflicts.  How does this affect the global optimality of the solution?
5.  Is there any additional reasoning/evidence for why the SBS method is advantageous (other than the context window length)?  Are there any downsides to the SBS method?  
6.  What is meant by "validated solution" in Figure 4?  The agents do not reach the goals specified in the figure.
soundness: 2
strengths: LLMs are indeed experiencing a surge of popularity in a huge spectrum of applications.  Any work that contributes to understanding their limitations is important.
summary: This is a paper that attempts to show that LLMs are not yet a viable option for solving multi-agent path finding (MAPF).  The authors describe a method for prompting an LLM for a solution, checking the output for collisions, and iteratively re-prompting the LLM until a solution is found or until a max number of iterations is reached.  They show that LLMs can solve MAPF problems when the planning problem is simple (such as single agent problems in an empty room with no obstacles) and that the capabilities of LLMs as MAPF solvers break down as the problem becomes more complex (multiple agents and more complex obstacle scenarios). They then discuss three possible causes of the poor performance (LLM’s reasoning capabilities, context length limits, and map “understanding”).
weaknesses: 1.	While it’s true that their method didn’t work well, the authors do not present enough evidence to justify saying “LLMs do not yet work for MAPF” (which is the main claim of the paper).  
2.	Experimental results are given in Tables 1-4 without sufficient explanation of the methods.  Would recommend a more concise problem statement in the paper (not appendix) that gives specifics of the scenarios, prompts, LLM outputs, and the collision checker.
3.	The justification for why the SBS method the authors describe in the paragraph starting on line 207 is not clear.  Other than providing a method to keep the context length shorter, it’s not apparent why this is a good approach.
4.	Many claims are made with little to substantiate them:
a.	Line 041: previous work “barely covers multi-agent planning” (Chen2023b and Agashe 2023)
b.	Line 047-049: Disagree on the list of previous methods.  It should also include LLMs (Chen et al 2023b)
c.	Broad claims about LLMs are made in the section on Understanding Obstacle Locations that do not seem supported by the single example presented.
d.	The authors claim (line 428) that the current workflow does not include any tool use, but they use an external collision checker (with little or no description of the checker).
e.	The claim made on line 363 “people barely provide any such information online since people have common knowledge of what to do with a map” seems unfounded and there is nothing to support it.
5.	There are significant grammar issues throughout.  Some examples:
a.	(Line 323) “However, recent studies have shown that long models like GPT4- turbo-128K are not a model whose capacity in 8K length also works when given a 128K-tokens input.”
b.	And (line 371) “which is killed by using much more total number of steps than it should”
6.	In lines 102-103 the authors say “we hope LLMs can be an alternative model to the current MAPF RL based models without additional training”.  However, they have previously stated that in their formulation, this didn’t work.  At this point, it’s better to say what you observed than what you had hoped for.
7.	The authors state on line 201 “It is unclear how well LLMs can solve MAPF problems,” but the main claim of the paper is that they aren’t good at it.
8.	In Figure 4, the goal of Agent 1 is (3,1) and the goal of Agent 2 is (2,0), however, Agent 1 ends up at (0,1) and Agent 2 ends up at (0,3). These are not at the goals, and in fact, Agent 2 has moved further away from the goal, so it’s not clear why this is a “validated solution”, except for the fact that they did not collide.  
9.	It seems intuitive and not scientifically interesting that success rate drops as the size of the problem grows (Lines 424-426).  
10.	The formatting of references seems non-standard.

Meta-review: The paper explores the use of large language models (LLMs) for multi-agent path-finding (MAPF) problems. The study investigates whether LLMs are able to generate valid paths for agents in different MAPF scenarios without heuristic guidance or additional training. Experiments show that while LLMs can effectively solve simple MAPF problems with a small number of obstacles, they face significant challenges in complex environments, frequently failing to produce collision-free solutions. The paper highlights three contributing factors: insufficient advanced reasoning capabilities, restrictions due to context length, and challenges in comprehending spatial information. Drawing from these insights, the authors propose future research directions to overcome these challenges and enhance LLMs’ performance in MAPF tasks.

The paper was reviewed by three referees who agree on the papers' key strengths and weaknesses. All three reviewers appreciate the identification of the limitations of using LLMs for multi-agent planning, which provides valuable insight for future work in LLM-based MAPF. However, the reviewers emphasize the need to compare to other MAPF algorithms including traditional methods as well as more advanced algorithms. The reviewers recognize that the paper's objective is not to outperform classic planners, but these comparisons would help to strengthen the paper's analysis by highlighting where LLMs fall short and would help to motivate the use of LLMs for MAPF. Related, the paper would benefit from experiments on more complex scenarios with further analysis of the success and failure of LLMs.

Decision: Reject