9 Feb 2024 | Weizhe Chen, Sven Koenig, Bistra Dilkina
This paper explores the challenges of using large language models (LLMs) to solve multi-agent path finding (MAPF) problems, a task that combines the difficulties of multi-agent coordination and planning. Despite the success of LLMs in various domains, their application to MAPF has not yet yielded satisfactory results. The authors focus on the performance of LLMs in solving MAPF, particularly in scenarios with obstacles, and find that while LLMs can solve simple problems, they fail in more complex scenarios due to limitations in understanding the context, reasoning capabilities, and context length limits.
The paper outlines three main reasons for the failures:
1. **Context Length Limit**: LLMs have a strict token limit, which becomes a significant issue in complex environments with many agents.
2. **Understanding Obstacle Locations**: LLMs struggle to understand the spatial relationships between obstacles and agent paths, leading to incorrect planning.
3. **Reasoning Capability**: LLMs lack the ability to reason about long-term planning and coordination, often resulting in oscillations or inefficient detours.
To address these issues, the authors propose a step-by-step generation approach and a high-level conflict checker to ensure the validity of the solutions. They also experiment with different input formats, such as text-only and image-based inputs, to improve performance. The results show that while LLMs can solve small, easy MAPF problems, they fail in more complex scenarios due to the limitations mentioned above.
The paper concludes by discussing potential future research directions, including improving LLMs' reasoning capabilities, extending context lengths, and enhancing understanding of obstacle locations. The authors hope that their work will serve as a foundation for future research in using LLMs for MAPF.This paper explores the challenges of using large language models (LLMs) to solve multi-agent path finding (MAPF) problems, a task that combines the difficulties of multi-agent coordination and planning. Despite the success of LLMs in various domains, their application to MAPF has not yet yielded satisfactory results. The authors focus on the performance of LLMs in solving MAPF, particularly in scenarios with obstacles, and find that while LLMs can solve simple problems, they fail in more complex scenarios due to limitations in understanding the context, reasoning capabilities, and context length limits.
The paper outlines three main reasons for the failures:
1. **Context Length Limit**: LLMs have a strict token limit, which becomes a significant issue in complex environments with many agents.
2. **Understanding Obstacle Locations**: LLMs struggle to understand the spatial relationships between obstacles and agent paths, leading to incorrect planning.
3. **Reasoning Capability**: LLMs lack the ability to reason about long-term planning and coordination, often resulting in oscillations or inefficient detours.
To address these issues, the authors propose a step-by-step generation approach and a high-level conflict checker to ensure the validity of the solutions. They also experiment with different input formats, such as text-only and image-based inputs, to improve performance. The results show that while LLMs can solve small, easy MAPF problems, they fail in more complex scenarios due to the limitations mentioned above.
The paper concludes by discussing potential future research directions, including improving LLMs' reasoning capabilities, extending context lengths, and enhancing understanding of obstacle locations. The authors hope that their work will serve as a foundation for future research in using LLMs for MAPF.