LLM-A*: Large Language Model Enhanced Incremental Heuristic Search on Path Planning

LLM-A*: Large Language Model Enhanced Incremental Heuristic Search on Path Planning

20 Jun 2024 | Silin Meng, Yiwei Wang, Cheng-Fu Yang, Nanyun Peng, Kai-Wei Chang
LLM-A* is a hybrid path planning algorithm that combines the precision of the A* algorithm with the global reasoning capabilities of large language models (LLMs). It leverages LLM-generated waypoints to guide the search process, significantly reducing the number of visited states and improving computational and memory efficiency. The algorithm integrates the standard L2 distance-based heuristic of A* with new heuristic values derived from these waypoints, ensuring the validity of the output paths. LLM-A* outperforms traditional A* in terms of scalability and efficiency, showing nearly linear growth in computational and memory requirements compared to the exponential growth of A* in larger environments. The algorithm is tested across various environments and demonstrates superior performance in terms of operation and storage efficiency, path length, and validity. LLM-A* also addresses the limitations of LLM-only approaches by incorporating the deterministic guarantees of A* to ensure path validity. The methodology of LLM-A* retains the general applicability of A*, making it suitable for a wide range of pathfinding tasks. The algorithm's performance is evaluated using quantitative metrics, including operation and storage ratios, relative path length, valid path ratio, and growth factors. The results show that LLM-A* achieves a significantly lower operation and storage ratio compared to A*, with a high valid path ratio and minimal increase in path length. The algorithm's effectiveness is further validated through qualitative analysis, demonstrating its ability to find optimal paths with fewer operations and storage usage. LLM-A* is a robust alternative to A* for path planning, especially in large-scale scenarios. However, it does not guarantee optimal paths and may sometimes generate suboptimal paths. Future improvements could focus on enhancing the optimality of the generated paths to ensure more consistent performance.LLM-A* is a hybrid path planning algorithm that combines the precision of the A* algorithm with the global reasoning capabilities of large language models (LLMs). It leverages LLM-generated waypoints to guide the search process, significantly reducing the number of visited states and improving computational and memory efficiency. The algorithm integrates the standard L2 distance-based heuristic of A* with new heuristic values derived from these waypoints, ensuring the validity of the output paths. LLM-A* outperforms traditional A* in terms of scalability and efficiency, showing nearly linear growth in computational and memory requirements compared to the exponential growth of A* in larger environments. The algorithm is tested across various environments and demonstrates superior performance in terms of operation and storage efficiency, path length, and validity. LLM-A* also addresses the limitations of LLM-only approaches by incorporating the deterministic guarantees of A* to ensure path validity. The methodology of LLM-A* retains the general applicability of A*, making it suitable for a wide range of pathfinding tasks. The algorithm's performance is evaluated using quantitative metrics, including operation and storage ratios, relative path length, valid path ratio, and growth factors. The results show that LLM-A* achieves a significantly lower operation and storage ratio compared to A*, with a high valid path ratio and minimal increase in path length. The algorithm's effectiveness is further validated through qualitative analysis, demonstrating its ability to find optimal paths with fewer operations and storage usage. LLM-A* is a robust alternative to A* for path planning, especially in large-scale scenarios. However, it does not guarantee optimal paths and may sometimes generate suboptimal paths. Future improvements could focus on enhancing the optimality of the generated paths to ensure more consistent performance.
Reach us at info@study.space
Understanding LLM-A*%3A Large Language Model Enhanced Incremental Heuristic Search on Path Planning