EMNLP Findings2024
LLM-A*: Large Language Model Enhanced Incremental Heuristic Search on Path Planning
Silin Meng, Yiwei Wang, Cheng-Fu Yang, Nanyun Peng, Kai-Wei Chang
Abstract
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.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
8 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- RethinkMCTS: Refining Erroneous Thoughts in Monte Carlo Tree Search for Code Generation cites Reflexion: language agents with verbal reinforcement learning
- Reflexion: language agents with verbal reinforcement learning cites ALFWorld: Aligning Text and Embodied Environments for Interactive Learning
- Reflexion: language agents with verbal reinforcement learning cites Chain-of-Thought Prompting Elicits Reasoning in Large Language Models
- Self-CriTeach: LLM Self-Teaching and Self-Critiquing for Improving Robotic Planning via Automated Domain Generation cites One Demo Is All It Takes: Planning Domain Derivation with LLMs from A Single Demonstration
- Self-CriTeach: LLM Self-Teaching and Self-Critiquing for Improving Robotic Planning via Automated Domain Generation cites Chain-of-Thought Prompting Elicits Reasoning in Large Language Models
- NavGPT: Explicit Reasoning in Vision-and-Language Navigation with Large Language Models cites Chain-of-Thought Prompting Elicits Reasoning in Large Language Models
Cited by top-tier papers8
- One Demo Is All It Takes: Planning Domain Derivation with LLMs from A Single DemonstrationJinbang Huang, Yixin Xiao, Zhanguang Zhang, Mark Coates et al.ICLR 2026 · 9 citations
- PathMind: A Retrieve-Prioritize-Reason Framework for Knowledge Graph Reasoning with Large Language ModelsYu Liu, Xixun Lin, Yanmin Shang, Yangxi Li et al.AAAI 2026 · 3 citations
- Self-CriTeach: LLM Self-Teaching and Self-Critiquing for Improving Robotic Planning via Automated Domain GenerationJinbang Huang, Zhiyuan Li, Yuanzhao Hu, Zhanguang Zhang et al.ICML 2026 · 3 citations
- Learning Admissible Heuristics for A*: Theory and PracticeEhsan Futuhi, Nathan R. SturtevantICLR 2026 · 3 citations
- RethinkMCTS: Refining Erroneous Thoughts in Monte Carlo Tree Search for Code GenerationQingyao Li, Wei Xia, Xinyi Dai, Kounianhua Du et al.EMNLP 2025 · 2 citations
Builds on12
- Chain-of-Thought Prompting Elicits Reasoning in Large Language ModelsJason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma et al.NeurIPS 2022 · 22,562 citations
- Reflexion: language agents with verbal reinforcement learningNoah Shinn, Federico Cassano, Ashwin Gopinath, Karthik Narasimhan et al.NeurIPS 2023 · 5,828 citations
- ALFWorld: Aligning Text and Embodied Environments for Interactive LearningMohit Shridhar, Xingdi Yuan, Marc-Alexandre Côté, Yonatan Bisk et al.ICLR 2021 · 819 citations
- LLM-Planner: Few-Shot Grounded Planning for Embodied Agents with Large Language ModelsChan Hee Song, Brian M. Sadler, Jiaman Wu, Wei-Lun Chao et al.ICCV 2023 · 685 citations
- NavGPT: Explicit Reasoning in Vision-and-Language Navigation with Large Language ModelsGengze Zhou, Yicong Hong, Qi WuAAAI 2024 · 361 citations
Related papers
- Thought of Search: Planning with Language Models Through The Lens of EfficiencyMichael Katz, Harsha Kokel, Kavitha Srinivas, Shirin SohrabiNeurIPS 2024 · 50 citations
- Can LLMs Fix Issues with Reasoning Models? Towards More Likely Models for AI PlanningTurgay Caglar, Sirine Belhaj, Tathagata Chakraborti, Michael Katz et al.AAAI 2024 · 11 citations
- GraphMind: LLMs as Dynamic Knowledge Builders for Sequential Decision-MakingSunguk Shin, Hayeong Lee, JunHo Seo, Jinho Lee et al.ACL Findings 2026
- Instruction-Augmented Long-Horizon Planning: Embedding Grounding Mechanisms in Embodied Mobile ManipulationFangyuan Wang, Shipeng Lyu, Peng Zhou, Anqing Duan et al.AAAI 2025 · 9 citations
- LLMAP: LLM-Assisted Multi-Objective Route Planning with User PreferencesLiangqi Yuan, Dong-Jun Han, Christopher G. Brinton, Sabine BrunswickerEMNLP Findings 2025 · 5 citations
