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

arXiv: https://arxiv.org/abs/2407.02511 · HTML: https://mlsanity.com/paper/2407.02511/

## Key facts

- Cited by 45 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 51 references that are in the map.
- First posted on arXiv 20 Jun 2024.

## Builds on (most cited first, 21 of 21)

- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Sparks of Artificial General Intelligence: Early experiments with GPT-4](https://mlsanity.com/paper/2303.12712/) (2023)
- [ALFWorld: Aligning Text and Embodied Environments for Interactive Learning](https://mlsanity.com/paper/2010.03768/) (2020)
- [ALFRED: A Benchmark for Interpreting Grounded Instructions for Everyday Tasks](https://mlsanity.com/paper/1912.01734/) (2019)
- [LLM+P: Empowering Large Language Models with Optimal Planning Proficiency](https://mlsanity.com/paper/2304.11477/) (2023)
- [TextWorld: A Learning Environment for Text-based Games](https://mlsanity.com/paper/1806.11532/) (2018)
- [FireAct: Toward Language Agent Fine-tuning](https://mlsanity.com/paper/2310.05915/) (2023)
- [Reasoning or Reciting? Exploring the Capabilities and Limitations of Language Models Through Counterfactual Tasks](https://mlsanity.com/paper/2307.02477/) (2023)
- [Take a Step Back: Evoking Reasoning via Abstraction in Large Language Models](https://mlsanity.com/paper/2310.06117/) (2023)
- [Can Language Models Encode Perceptual Structure Without Grounding? A Case Study in Color](https://mlsanity.com/paper/2109.06129/) (2021)
- [AutoTAMP: Autoregressive Task and Motion Planning with LLMs as Translators and Checkers](https://mlsanity.com/paper/2306.06531/) (2023)
- [A Benchmark for Systematic Generalization in Grounded Language Understanding](https://mlsanity.com/paper/2003.05161/) (2020)
- [LLM3:Large Language Model-based Task and Motion Planning with Motion Failure Reasoning](https://mlsanity.com/paper/2403.11552/) (2024)
- [Can Large Language Models be Good Path Planners? A Benchmark and Investigation on Spatial-temporal Reasoning](https://mlsanity.com/paper/2310.03249/) (2023)
- [A Theoretical Analysis of the Number of Shots in Few-Shot Learning](https://mlsanity.com/paper/1909.11722/) (2019)
- [Theta*: Any-Angle Path Planning on Grids](https://mlsanity.com/paper/1401.3843/) (2014)
- [ReaSCAN: Compositional Reasoning in Language Grounding](https://mlsanity.com/paper/2109.08994/) (2021)
- [Planning as In-Painting: A Diffusion-Based Embodied Task Planning Framework for Environments under Uncertainty](https://mlsanity.com/paper/2312.01097/) (2023)
- [MANGO: A Benchmark for Evaluating Mapping and Navigation Abilities of Large Language Models](https://mlsanity.com/paper/2403.19913/) (2024)
- [LACMA: Language-Aligning Contrastive Learning with Meta-Actions for Embodied Instruction Following](https://mlsanity.com/paper/2310.12344/) (2023)
- [Are LLMs the Master of All Trades? : Exploring Domain-Agnostic Reasoning Skills of LLMs](https://mlsanity.com/paper/2303.12810/) (2023)

## Built on by (most cited first, 30 of 45)

- [A Survey of Agentic Reasoning for Large Language Models: Towards Recursively Self-Improving and Collective Agents](https://mlsanity.com/paper/2601.12538/) (2026)
- [A Survey of Test-Time Compute: From Intuitive Inference to Deliberate Reasoning](https://mlsanity.com/paper/2501.02497/) (2025)
- [Large Language Models for Planning: A Comprehensive and Systematic Survey](https://mlsanity.com/paper/2505.19683/) (2025)
- [Benchmarking Agentic Workflow Generation](https://mlsanity.com/paper/2410.07869/) (2024)
- [RethinkMCTS: Refining Erroneous Thoughts in Monte Carlo Tree Search for Code Generation](https://mlsanity.com/paper/2409.09584/) (2024)
- [A Survey on LLM Test-Time Compute via Search: Tasks, LLM Profiling, Search Algorithms, and Relevant Frameworks](https://mlsanity.com/paper/2501.10069/) (2025)
- [Is Your LLM-Based Multi-Agent a Reliable Real-World Planner? Exploring Fraud Detection in Travel Planning](https://mlsanity.com/paper/2505.16557/) (2025)
- [R2D2: Remembering, Replaying and Dynamic Decision Making with a Reflective Agentic Memory](https://mlsanity.com/paper/2501.12485/) (2025)
- [Neural Chain-of-Thought Search: Searching the Optimal Reasoning Path to Enhance Large Language Models](https://mlsanity.com/paper/2601.11340/) (2026)
- [Evaluating Vision-Language Models as Evaluators in Path Planning](https://mlsanity.com/paper/2411.18711/) (2024)
- [TraveLLM: Could you plan my new public transit route in face of a network disruption?](https://mlsanity.com/paper/2407.14926/) (2024)
- [VLM-RRT: Vision Language Model Guided RRT Search for Autonomous UAV Navigation](https://mlsanity.com/paper/2505.23267/) (2025)
- [LLMAP: LLM-Assisted Multi-Objective Route Planning with User Preferences](https://mlsanity.com/paper/2509.12273/) (2025)
- [StyleBench: Evaluating thinking styles in Large Language Models](https://mlsanity.com/paper/2509.20868/) (2025)
- [Offline Learning and Forgetting for Reasoning with Large Language Models](https://mlsanity.com/paper/2504.11364/) (2025)
- [GridRoute: A Benchmark for LLM-Based Route Planning with Cardinal Movement in Grid Environments](https://mlsanity.com/paper/2505.24306/) (2025)
- [Assessing the Value of Visual Input: A Benchmark of Multimodal Large Language Models for Robotic Path Planning](https://mlsanity.com/paper/2507.12391/) (2025)
- [Discovering Heuristics with Large Language Models (LLMs) for Mixed-Integer Programs: Single-Machine Scheduling](https://mlsanity.com/paper/2510.24013/) (2025)
- [Can LLMs plan paths with extra hints from solvers?](https://mlsanity.com/paper/2410.05045/) (2024)
- [Gricean Norms as a Basis for Effective Collaboration](https://mlsanity.com/paper/2503.14484/) (2025)
- [Generative AI for Autonomous Driving: A Review](https://mlsanity.com/paper/2505.15863/) (2025)
- [Constraint-Aware Route Recommendation from Natural Language via Hierarchical LLM Agents](https://mlsanity.com/paper/2510.06078/) (2025)
- [Can LLMs plan paths in the real world?](https://mlsanity.com/paper/2411.17912/) (2024)
- [From Reasoning to Generalization: Knowledge-Augmented LLMs for ARC Benchmark](https://mlsanity.com/paper/2505.17482/) (2025)
- [LLM-ODDR: A Large Language Model Framework for Joint Order Dispatching and Driver Repositioning](https://mlsanity.com/paper/2505.22695/) (2025)
- [Learning Admissible Heuristics for A*: Theory and Practice](https://mlsanity.com/paper/2509.22626/) (2025)
- [Augmented Runtime Collaboration for Self-Organizing Multi-Agent Systems: A Hybrid Bi-Criteria Routing Approach](https://mlsanity.com/paper/2512.00740/) (2025)
- [LLM-Advisor: An LLM Advisor for Cost-efficient Path Planning across Multiple Terrains](https://mlsanity.com/paper/2503.01236/) (2025)
- [Semantic Intelligence: Integrating GPT-4 with A Planning in Low-Cost Robotics](https://mlsanity.com/paper/2505.01931/) (2025)
- [A 1000× Faster LLM-enhanced Algorithm For Path Planning in Large-scale Grid Maps](https://mlsanity.com/paper/2510.02716/) (2025)

## Abstract (arXiv)

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.