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.}

翻译：栅格地图中的路径规划问题源于多种应用场景，已引起广泛关注。现有方法如A*、Dijkstra及其变体在小规模地图中表现良好，但由于搜索时间和内存消耗过高，难以应对大规模地图。近年来，大语言模型（LLMs）在路径规划中展现出卓越性能，但仍存在空间幻觉和规划效果不佳的问题。在现有研究中，LLM-A* \\cite{meng2024llm} 利用LLM生成一系列航点，然后使用A*算法规划相邻航点间的路径，从而构建完整路径。然而，LLM-A* 在大规模地图中仍面临计算时间过长的问题。为填补这一空白，我们深入研究了LLM-A* 并发现其性能瓶颈。据此，我们设计了一种创新的大语言模型增强算法，简称为 iLLM-A*。该算法包含三项精心设计的机制：A*算法的优化、用于生成高质量航点的LLM增量学习方法，以及为A*路径规划选择合适的航点。最终，在不同栅格地图上的综合评估表明，与LLM-A*相比，iLLM-A* \\textbf{1) 平均实现超过$1000\\times$的加速，极端情况下最高可达$2349.5\\times$加速；2) 节省高达$58.6\\%$的内存开销；3) 同时获得明显更短的路径长度和更低的路径长度标准差。}