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 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.
问 Lune
几分钟读透这篇 Paper,不用再花一下午。
Lune 能读完全文,也能读引用它的顶会 Paper,讲清它的结论、证据和局限,每一点都注明出自哪篇 Paper。不用硬啃,也不靠猜。
已有 8 篇顶会 Paper 引用了它。别等审稿人问起,先弄清它们发现了什么。
脉络
- RethinkMCTS: Refining Erroneous Thoughts in Monte Carlo Tree Search for Code Generation 引用了 Reflexion: language agents with verbal reinforcement learning
- Reflexion: language agents with verbal reinforcement learning 引用了 ALFWorld: Aligning Text and Embodied Environments for Interactive Learning
- Reflexion: language agents with verbal reinforcement learning 引用了 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 引用了 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 引用了 Chain-of-Thought Prompting Elicits Reasoning in Large Language Models
- NavGPT: Explicit Reasoning in Vision-and-Language Navigation with Large Language Models 引用了 Chain-of-Thought Prompting Elicits Reasoning in Large Language Models
引用它的顶会 Paper8
- One Demo Is All It Takes: Planning Domain Derivation with LLMs from A Single DemonstrationJinbang Huang, Yixin Xiao, Zhanguang Zhang, Mark Coates 等ICLR 2026 · 9 次引用
- PathMind: A Retrieve-Prioritize-Reason Framework for Knowledge Graph Reasoning with Large Language ModelsYu Liu, Xixun Lin, Yanmin Shang, Yangxi Li 等AAAI 2026 · 3 次引用
- Self-CriTeach: LLM Self-Teaching and Self-Critiquing for Improving Robotic Planning via Automated Domain GenerationJinbang Huang, Zhiyuan Li, Yuanzhao Hu, Zhanguang Zhang 等ICML 2026 · 3 次引用
- Learning Admissible Heuristics for A*: Theory and PracticeEhsan Futuhi, Nathan R. SturtevantICLR 2026 · 3 次引用
- RethinkMCTS: Refining Erroneous Thoughts in Monte Carlo Tree Search for Code GenerationQingyao Li, Wei Xia, Xinyi Dai, Kounianhua Du 等EMNLP 2025 · 2 次引用
它引用的 Paper12
- Chain-of-Thought Prompting Elicits Reasoning in Large Language ModelsJason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma 等NeurIPS 2022 · 22,562 次引用
- Reflexion: language agents with verbal reinforcement learningNoah Shinn, Federico Cassano, Ashwin Gopinath, Karthik Narasimhan 等NeurIPS 2023 · 5,828 次引用
- ALFWorld: Aligning Text and Embodied Environments for Interactive LearningMohit Shridhar, Xingdi Yuan, Marc-Alexandre Côté, Yonatan Bisk 等ICLR 2021 · 819 次引用
- LLM-Planner: Few-Shot Grounded Planning for Embodied Agents with Large Language ModelsChan Hee Song, Brian M. Sadler, Jiaman Wu, Wei-Lun Chao 等ICCV 2023 · 685 次引用
- NavGPT: Explicit Reasoning in Vision-and-Language Navigation with Large Language ModelsGengze Zhou, Yicong Hong, Qi WuAAAI 2024 · 361 次引用
相关 Paper
- Thought of Search: Planning with Language Models Through The Lens of EfficiencyMichael Katz, Harsha Kokel, Kavitha Srinivas, Shirin SohrabiNeurIPS 2024 · 50 次引用
- Can LLMs Fix Issues with Reasoning Models? Towards More Likely Models for AI PlanningTurgay Caglar, Sirine Belhaj, Tathagata Chakraborti, Michael Katz 等AAAI 2024 · 11 次引用
- GraphMind: LLMs as Dynamic Knowledge Builders for Sequential Decision-MakingSunguk Shin, Hayeong Lee, JunHo Seo, Jinho Lee 等ACL Findings 2026
- Instruction-Augmented Long-Horizon Planning: Embedding Grounding Mechanisms in Embodied Mobile ManipulationFangyuan Wang, Shipeng Lyu, Peng Zhou, Anqing Duan 等AAAI 2025 · 9 次引用
- LLMAP: LLM-Assisted Multi-Objective Route Planning with User PreferencesLiangqi Yuan, Dong-Jun Han, Christopher G. Brinton, Sabine BrunswickerEMNLP Findings 2025 · 5 次引用
