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

• URL: http://arxiv.org/abs/2407.02511v1
• Date: Thu, 20 Jun 2024 01:24:30 GMT
• Title: LLM-A*: Large Language Model Enhanced Incremental Heuristic Search on Path Planning
• Authors: Silin Meng, Yiwei Wang, Cheng-Fu Yang, Nanyun Peng, Kai-Wei Chang,
• Abstract summary: Path planning is a fundamental scientific problem in robotics and autonomous navigation. 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. We propose a 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.
• Score: 91.95362946266577
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Sample and Oracle Efficient Reinforcement Learning for MDPs with Linearly-Realizable Value Functions [10.225358400539719]
  We present an efficient reinforcement algorithm for Decision (MDPs) where a linear-action-action generalizes in a feature map. Specifically, we introduce a new algorithm that efficiently finds a near-optimal policy in this setting.
  arXiv  Detail & Related papers  (2024-09-07T14:38:05Z)
• Pluto and Charon: A Time and Memory Efficient Collaborative Edge AI Framework for Personal LLMs Fine-Tuning [13.26886445965894]
  Pluto and Charon (PAC) is a time and memory efficient collaborative edge AI framework for personal LLMs fine-tuning. PAC implements a personal LLMs fine-tuning technique that is efficient in terms of parameters, time, and memory. Extensive evaluation based on prototype implementation demonstrates that PAC remarkably outperforms state-of-the-art approaches.
  arXiv  Detail & Related papers  (2024-08-20T11:30:12Z)
• Directed Exploration in Reinforcement Learning from Linear Temporal Logic [59.707408697394534]
  Linear temporal logic (LTL) is a powerful language for task specification in reinforcement learning. We show that the synthesized reward signal remains fundamentally sparse, making exploration challenging. We show how better exploration can be achieved by further leveraging the specification and casting its corresponding Limit Deterministic B"uchi Automaton (LDBA) as a Markov reward process.
  arXiv  Detail & Related papers  (2024-08-18T14:25:44Z)
• How Can LLM Guide RL? A Value-Based Approach [68.55316627400683]
  Reinforcement learning (RL) has become the de facto standard practice for sequential decision-making problems by improving future acting policies with feedback. Recent developments in large language models (LLMs) have showcased impressive capabilities in language understanding and generation, yet they fall short in exploration and self-improvement capabilities. We develop an algorithm named LINVIT that incorporates LLM guidance as a regularization factor in value-based RL, leading to significant reductions in the amount of data needed for learning.
  arXiv  Detail & Related papers  (2024-02-25T20:07:13Z)
• LLM A*: Human in the Loop Large Language Models Enabled A* Search for Robotics [3.567107449359775]
  This research focuses on how Large Language Models (LLMs) can help with (path) planning for mobile embodied agents such as robots. A novel framework named LLM A*, aims to leverage the commonsense of LLMs, and the utility-optimal A* is proposed to facilitate few-shot near-optimal path planning. This approach takes human feedback on board and renders the entire planning process transparent (akin to a white box') to humans.
  arXiv  Detail & Related papers  (2023-12-04T10:37:58Z)
• LanguageMPC: Large Language Models as Decision Makers for Autonomous Driving [87.1164964709168]
  This work employs Large Language Models (LLMs) as a decision-making component for complex autonomous driving scenarios. Extensive experiments demonstrate that our proposed method not only consistently surpasses baseline approaches in single-vehicle tasks, but also helps handle complex driving behaviors even multi-vehicle coordination.
  arXiv  Detail & Related papers  (2023-10-04T17:59:49Z)
• Overcoming Exploration: Deep Reinforcement Learning in Complex Environments from Temporal Logic Specifications [2.8904578737516764]
  We present a Deep Reinforcement Learning (DRL) algorithm for a task-guided robot with unknown continuous-time dynamics deployed in a large-scale complex environment. Our framework is shown to significantly improve performance (effectiveness, efficiency) and exploration of robots tasked with complex missions in large-scale complex environments.
  arXiv  Detail & Related papers  (2022-01-28T16:39:08Z)
• Deep Learning Aided Packet Routing in Aeronautical Ad-Hoc Networks Relying on Real Flight Data: From Single-Objective to Near-Pareto Multi-Objective Optimization [79.96177511319713]
  We invoke deep learning (DL) to assist routing in aeronautical ad-hoc networks (AANETs) A deep neural network (DNN) is conceived for mapping the local geographic information observed by the forwarding node into the information required for determining the optimal next hop. We extend the DL-aided routing algorithm to a multi-objective scenario, where we aim for simultaneously minimizing the delay, maximizing the path capacity, and maximizing the path lifetime.
  arXiv  Detail & Related papers  (2021-10-28T14:18:22Z)
• Learning Space Partitions for Path Planning [54.475949279050596]
  PlaLaM outperforms existing path planning methods in 2D navigation tasks, especially in the presence of difficult-to-escape local optima. These gains transfer to highly multimodal real-world tasks, where we outperform strong baselines in compiler phase ordering by up to 245% and in molecular design by up to 0.4 on properties on a 0-1 scale.
  arXiv  Detail & Related papers  (2021-06-19T18:06:11Z)
• Integrated Decision and Control: Towards Interpretable and Efficient Driving Intelligence [13.589285628074542]
  We present an interpretable and efficient decision and control framework for automated vehicles. It decomposes the driving task into multi-path planning and optimal tracking that are structured hierarchically. Results show that our method has better online computing efficiency and driving performance including traffic efficiency and safety.
  arXiv  Detail & Related papers  (2021-03-18T14:43:31Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.