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

Abstract: Path planning is a fundamental scientific problem in robotics and autonomous navigation, requiring the derivation of efficient routes from starting to destination points while avoiding obstacles. Traditional algorithms like A* and its variants are capable of ensuring path validity but suffer from significant computational and memory inefficiencies as the state space grows. Conversely, large language models (LLMs) excel in broader environmental analysis through contextual understanding, providing global insights into environments. However, they fall short in detailed spatial and temporal reasoning, often leading to invalid or inefficient routes. In this work, we propose LLM-A*, an new LLM based route planning method that synergistically combines the precise pathfinding capabilities of A* with the global reasoning capability of LLMs. This hybrid approach aims to enhance pathfinding efficiency in terms of time and space complexity while maintaining the integrity of path validity, especially in large-scale scenarios. By integrating the strengths of both methodologies, LLM-A* addresses the computational and memory limitations of conventional algorithms without compromising on the validity required for effective pathfinding.

## introduction path planning is the computational process of determining a path from an initial point to a destination point that adheres to specific criteria, such as avoiding obstacles, minimizing travel distance or time, and satisfying other constraints @xcite @xcite . this problem is crucial across several fields, such as robotics, autonomous vehicle navigation, industrial automation, and virtual environment navigation due to its direct impact on the efficiency, safety, and feasibility of operational systems @xcite frazzoli, { "operation": 859, "storage": 802, "path length": 53.46 } {"operation": 140, "storage": 235, "path length": 53.46} start state a* llm-a* goal state target state (llm-waypoint) barriers visited state 2011; @xcite . existing path planning algorithms are capable of effectively completing planning tasks and ensuring the validity of their paths. however, as the environment and map scale up, algorithms like a* and its variants @xcite @xcite encounter an exponential increase in computational and memory demands. this occurs because the pathfinding process can become suboptimal (see figure 1 and 2), where the algorithm might spend unnecessary effort exploring less relevant areas, leading to exponential increases in time complexity as the map size enlarges. meanwhile, large language models (llms) have achieved notable milestones in various planning tasks @xcite @xcite @xcite . these models demonstrate capabilities in processing and reasoning over long-context input to provide valuable global insights that reflect their understanding of the environment, such as identifying the relative positions of barriers, agents, and goals. however, they struggle with complex, long-term planning and complex spatial reasoning tasks such as grid-based path planning. llms often generate paths that are either invalid or ungrounded, resulting in incomplete or colliding paths, indicating a gap in their capability to handle detailed spatial intricacies @xcite . in this work, we propose llm-a*, a new llm based route planning method that synergizes the traditional a* algorithm with the global insights from large language models. as illustrated in fig. 1 and 2, this hybrid approach leverages llm-generated waypoints to guide the path searching process, significantly reducing computational and memory costs. in addition, by integrating the standard l2 distance-based heuristic of a* with new heuristic values derived from these waypoints, llm-a* addresses the granularity issues in llm-generated solutions, ensuring the validity of the output paths. we conducted extensive experiments across various environment to compare the performance of a* and llm-a* (integrating llama3 with few-shot prompting). as illustrated in figure 3 , a* exhibits exponential growth in both computational operations and storage requirements with linearly increasing environment scale. in contrast, llm-a* shows a nearly linear growth pattern, indicating superior scalability. this suggests that llm-a* is significantly more efficient in terms of both computation and memory, making it better suited for larger environments. furthermore, our primary experimental results, summarized in extensions of a* have aimed to enhance its efficiency and adaptability. korf's iterative deepening a* (ida*), from 1985, combines depth-first search with a*'s heuristic to create a memoryefficient approach @xcite . korf also introduced learning real-time a* (lrta*) in 1990, incorporating real-time learning to dynamically update heuristic values, improving performance in changing environments @xcite ). russell's simplified memory bounded a* (sma*), from 1992, addresses memory constraints by selectively forgetting less promising paths, making it suitable for resource-limited applications @xcite . further enhancements include stentz's dynamic a* (d*) from 1994, which recalculates paths as the environment changes, proving effective for navigation in unknown or evolving terrains @xcite . @xcite s lifelong planning a* (lpa*), introduced in 2004, incrementally updates paths in dynamic and large-scale environments @xcite . @xcite , proposed in 2011, optimizes a* for only grid-based maps by identifying key "jump points", reducing the number of expanded nodes @xcite . nash et al.'s theta*, from 2007, allows line-of-sight checks between nodes, resulting in more direct paths @xcite . hierarchical approaches, such as holte et al.'s hierarchical a* (ha*) from 1996, decompose large pathfinding problems into smaller subproblems through a hierarchy of abstractions, reducing computational complexity @xcite . botea et al.'s hierarchical path-finding a* (hpa*), introduced in 2004, improves transitions between abstraction levels for efficient large-map pathfinding @xcite . specialized methods also contribute significantly. demyen and buro's triangulation-based pathfinding (tra*), proposed in 2006, navigates polygonal environments using triangulation, suited for non-grid-based settings @xcite ). koch's grid-specific hierarchical path-finding (ghpa*), introduced in 2011, optimizes grid maps pathfinding by integrating hierarchical and grid-specific optimizations @xcite . large language models in path planning. large language models (llms) have recently achieved remarkable success in natural language processing tasks and other domains @xcite . studies such as @xcite @xcite explore llms in high-level planning, highlighting challenges in long-term planning and spatial reasoning @xcite . our research shifts focus to continuous environments, offering a more realistic setting compared to grid-based maps. continuous spaces align better with real-world conditions, providing a more natural interface for human interaction and allowing higher precision in spatial reasoning. llms show varying proficiency in spatial reasoning @xcite @xcite @xcite ), yet face limitations in spatial reasoning and planning @xcite @xcite . we introduce a benchmark for path planning in continuous environments, integrating spatial and temporal reasoning. prior benchmarks @xcite @xcite often neglect temporal planning aspects. our study further evaluates llms in robot motion and path planning contexts, addressing limitations in end-to-end planning @xcite @xcite . recent work, such as the llm3 framework @xcite leverages pre-trained llms to integrate symbolic task planning with continuous motion generation through motion failure reasoning, where llm3 iteratively refines both symbolic actions and continuous parameters, significantly improving planning efficiency in dynamic environments, which aligns with our focus on llms' adaptability in correcting low-level planning errors and enhancing resilience in dynamic conditions. understanding the interplay between high-level and low-level planning is crucial @xcite @xcite . high-level planning involves strategic goals, while low-level focuses on detailed task execution. our research explores llms' adaptability in correcting low-level planning errors, ensuring resilience in dynamic conditions. if s @xmath0: add s n to o open 22: return failure 3 methodology ## conclusion in this work, we propose a novel path planning algorithm, llm-a*, which outperforms traditional algorithms like a* in terms of both computational and memory efficiency, as well as llm-only approach in path robustness and optimality. llm-a* integrates heuristic values derived from llmgenerated waypoints (serves as global insight), with the deterministic guarantees in the a* algorithm. this hybrid approach addresses the shortcomings of both llm-only approach and the a* algorithm by combining their respective strengths. furthermore, the methodology of llm-a* retains the general applicability of a*, making it suitable for pathfinding tasks in a wide range of environments. thus, llm-a* serves as an effective alternative to a* algorithm for path planning, especially in large-scale scenarios.