UCLA

Path planning is a fundamental problem in robotics and autonomous systems, requiring the computation of efficient routes from a start to a goal while avoiding obstacles. Traditional pathfinding algorithms like A* guarantee valid paths but face scalability issues in large environments, incurring high computational and memory costs as the state space grows. Large language models (LLMs), on the other hand, have emerged as powerful AI tools capable of understanding context at a global level and providing high-level environmental insights. However, an LLM alone lacks precise spatial reasoning, often producing impractical or invalid routes in detailed path planning.

This thesis proposes a novel hybrid algorithm, dubbed LLM-A*, that integrates an LLM with the A* algorithm to combine their complementary strengths. The LLM component offers global guidance to narrow the search space and provide heuristic hints, while the A* component ensures local optimality and path validity. By leveraging the LLM’s broad environmental awareness to inform the A* search, this approach significantly improves pathfinding efficiency and reduces memory usage without sacrificing the quality of the path. Results indicate that this LLM-assisted strategy can plan routes more efficiently in complex, large-scale maps, enhancing scalability.