用大模型加速路径规划，速度提升千倍以上。
A $1000\times$ Faster LLM-enhanced Algorithm For Path Planning in Large-scale Grid Maps
- 用大模型生成关键路径点，再用A*算法连接，大幅减少搜索范围。
- 在大规模地图上平均提速超1000倍，最多达2349.5倍，内存节省58.6%。
- 适合需要实时路径规划的自动驾驶、机器人导航等场景。
网格地图中的路径规划在诸多应用中备受关注。传统方法如A*、Dijkstra及其变体在小规模地图上表现良好，但在大规模地图上因搜索时间长、内存消耗大而失效。近期大语言模型（LLMs）在路径规划中展现出潜力，但仍存在空间错觉和规划性能差的问题。现有工作LLM-A*通过大模型生成一系列路点，再由A*算法连接相邻路点完成路径构建，但依然存在计算耗时高的问题。本文深入分析了LLM-A*的瓶颈，提出一种新型增强算法iLLM-A*，包含三项优化机制：改进A*算法、大模型增量学习以生成高质量路点、合理选择路点供A*使用。在多种网格地图上的综合评估表明，与LLM-A*相比，iLLM-A*平均提速超过1000倍，极端情况下最高达2349.5倍，内存消耗最多降低58.6%，同时路径长度更短且标准差更低。
原文摘要 · Abstract (English)
Path planning in grid maps, arising from various applications, has garnered significant attention. Existing methods, such as A*, Dijkstra, and their variants, work well for small-scale maps but fail to address large-scale ones due to high search time and memory consumption. Recently, Large Language Models (LLMs) have shown remarkable performance in path planning but still suffer from spatial illusion and poor planning performance. Among all the works, LLM-A* \cite{meng2024llm} leverages LLM to generate a series of waypoints and then uses A* to plan the paths between the neighboring waypoints. In this way, the complete path is constructed. However, LLM-A* still suffers from high computational time for large-scale maps. To fill this gap, we conducted a deep investigation into LLM-A* and found its bottleneck, resulting in limited performance. Accordingly, we design an innovative LLM-enhanced algorithm, abbr. as iLLM-A*. iLLM-A* includes 3 carefully designed mechanisms, including the optimization of A*, an incremental learning method for LLM to generate high-quality waypoints, and the selection of the appropriate waypoints for A* for path planning. Finally, a comprehensive evaluation on various grid maps shows that, compared with LLM-A*, iLLM-A* \textbf{1) achieves more than $1000\times$ speedup on average, and up to $2349.5\times$ speedup in the extreme case, 2) saves up to $58.6\%$ of the memory cost, 3) achieves both obviously shorter path length and lower path length standard deviation.}
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。