A $1000\times$ Faster LLM-enhanced Algorithm For Path Planning in Large-scale Grid Maps

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* $\mathbf{\text{1)}}\mathbf{\text{achieves}}\mathbf{\text{more}}\mathbf{\text{than}}1000\times \mathbf{\text{speedup}}\mathbf{\text{on}}\mathbf{\text{average,}}\mathbf{\text{and}}\mathbf{\text{up}}\mathbf{\text{to}}2349.5\times \mathbf{\text{speedup}}\mathbf{\text{in}}\mathbf{\text{the}}\mathbf{\text{extreme}}\mathbf{\text{case,}}\mathbf{\text{2)}}\mathbf{\text{saves}}\mathbf{\text{up}}\mathbf{\text{to}}58.6\mathrm{\%}\mathbf{\text{of}}\mathbf{\text{the}}\mathbf{\text{memory}}\mathbf{\text{cost,}}\mathbf{\text{3)}}\mathbf{\text{achieves}}\mathbf{\text{both}}\mathbf{\text{obviously}}\mathbf{\text{shorter}}\mathbf{\text{path}}\mathbf{\text{length}}\mathbf{\text{and}}\mathbf{\text{lower}}\mathbf{\text{path}}\mathbf{\text{length}}\mathbf{\text{standard}}\mathbf{\text{deviation.}}$