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

2024-01-08 · Weizhe Chen, Sven Koenig, Bistra Dilkina

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.

📄 PDF Abstract BibTeX arXiv:2401.03630

Code (0)

등록된 구현이 없습니다.

Tasks

Language ModelingLanguage ModellingLarge Language ModelMulti-Agent Path Finding

Methods 이 논문이 사용한 방법론

Multi-Head Attention 설명 없음

Attention 설명 없음

Linear Layer A Linear Layer is a projection $\mathbf{XW + b}$.

Softmax The Softmax output function transforms a previous layer's output into a vector of probabilities. It is commonly used for multiclass classification. Given an input vector $x$…

Adam 설명 없음

Layer Normalization Unlike batch normalization, Layer Normalization directly estimates the normalization statistics from the summed inputs…

Residual Connection 설명 없음

Absolute Position Encodings Absolute Position Encodings are a type of position embeddings for [Transformer-based models] where positional encodings are…

Flexible and Explainable Solutions for Multi-Agent Path Finding Problems

2021-09-17 · Aysu Bogatarkan

The multi-agent path finding (MAPF) problem is a combinatorial search problem that aims at finding paths for multiple agents (e.g., robots) in an environment (e.g., an autonomous warehouse) such that no two agents collid…

Multi-Agent Path Finding

Optimal and Bounded Suboptimal Any-Angle Multi-agent Pathfinding

2024-04-25 · Konstantin Yakovlev, Anton Andreychuk, Roni Stern

Multi-agent pathfinding (MAPF) is the problem of finding a set of conflict-free paths for a set of agents. Typically, the agents' moves are limited to a pre-defined graph of possible locations and allowed transitions bet…

Resolving Head-On Conflicts for Multi-Agent Path Finding with Conflict-Based Search

2020-07-07 · Lun Yang

Conflict-Based Search (CBS) is a popular framework for solving the Multi-Agent Path Finding problem. Some of the conflicts incur a foreseeable conflict in one or both of the children nodes when splitting on them. This pa…

Multi-Agent Path Finding

Solving Multi-Agent Multi-Goal Path Finding Problems in Polynomial Time

2025-12-17 · Stefan Edelkamp arxiv

In this paper, we plan missions for a fleet of agents in undirected graphs, such as grids, with multiple goals. In contrast to regular multi-agent path-finding, the solver finds and updates the assignment of goals to the…

Multi-Goal Multi-Agent Path Finding via Decoupled and Integrated Goal Vertex Ordering

2020-09-10 · Pavel Surynek

We introduce multi-goal multi agent path finding (MAPF$^{MG}$) which generalizes the standard discrete multi-agent path finding (MAPF) problem. While the task in MAPF is to navigate agents in an undirected graph from the…

Heuristic Search Multi-Agent Path Finding Navigate