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

📄 arXiv: 2401.03630v2 📥 PDF

作者: Weizhe Chen, Sven Koenig, Bistra Dilkina

分类: cs.MA, cs.AI, cs.CL

发布日期: 2024-01-08 (更新: 2024-02-09)

💡 一句话要点

探讨大型语言模型在多智能体路径规划中的局限性

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 多智能体路径规划 大型语言模型 机器人导航 自动驾驶 智能交通系统

📋 核心要点

  1. 当前多智能体路径规划（MAPF）面临的主要挑战是多智能体协调与规划的复杂性，使得现有的LLM方法难以有效应用。
  2. 论文提出通过分析LLM在不同复杂度地图上的表现，探讨其在多智能体路径规划中的局限性，旨在为未来研究提供方向。
  3. 实验结果表明，LLM在简单环境中表现良好，但在复杂环境中失败，强调了多智能体规划的独特挑战和研究需求。

📝 摘要（中文）

随着大型语言模型（LLM）如ChatGPT和GPT-4的成功，相关研究迅速增加，但在多智能体规划领域的探索仍然有限。本文聚焦于多智能体路径规划（MAPF），研究LLM在此问题上的表现。我们首先展示了在无障碍空房间地图上的成功案例，随后分析了在更复杂的房间地图和迷宫地图上的失败。我们提出了直接使用LLM解决MAPF未成功的原因，并通过多项实验支持我们的假设，探讨不同背景的研究者如何从不同角度解决这一问题。

🔬 方法详解

问题定义：本文解决的是多智能体路径规划（MAPF）问题，现有方法在复杂环境下的表现不佳，难以有效利用LLM进行规划。

核心思路：我们通过对比LLM在不同环境下的表现，分析其在复杂路径规划中的局限性，提出需要更深入的多智能体协调机制。

技术框架：研究首先在无障碍的空房间地图上测试LLM的表现，随后在标准MAPF基准的复杂房间和迷宫地图上进行实验，比较其成功率和效率。

关键创新：论文的创新在于系统性地分析了LLM在多智能体路径规划中的失败原因，强调了多智能体协调的复杂性与LLM的局限性。

关键设计：实验中使用了不同的地图设置，评估了LLM在路径规划中的表现，特别关注了环境复杂度对结果的影响。具体参数设置和实验设计细节在论文中进行了详细描述。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果显示，LLM在空房间地图上成功率高达90%，但在复杂房间和迷宫地图上的成功率降至20%以下，强调了环境复杂性对多智能体路径规划的重大影响。这一发现为未来研究提供了重要的方向。

🎯 应用场景

该研究为多智能体系统中的路径规划提供了重要的理论基础，尤其是在机器人导航、自动驾驶和智能交通系统等领域具有潜在应用价值。通过深入理解LLM的局限性，未来的研究可以更有效地结合多智能体协调机制与先进的语言模型，从而提升路径规划的效率与准确性。

📄 摘要（原文）

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.