# Constraint-aware Path Planning from Natural Language Instructions Using Large Language Models

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 34 references that are in the map.
- First posted on arXiv 26 Feb 2026.

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

- [ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution](https://mlsanity.com/paper/2402.01145/) (2024)
- [Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model](https://mlsanity.com/paper/2401.02051/) (2024)
- [The Learnability of In-Context Learning](https://mlsanity.com/paper/2303.07895/) (2023)
- [Using Large Language Models for Hyperparameter Optimization](https://mlsanity.com/paper/2312.04528/) (2023)
- [LLM4AD: A Platform for Algorithm Design with Large Language Model](https://mlsanity.com/paper/2412.17287/) (2024)
- [Visual Reasoning and Multi-Agent Approach in Multimodal Large Language Models (MLLMs): Solving TSP and mTSP Combinatorial Challenges](https://mlsanity.com/paper/2407.00092/) (2024)
- [Planning of Heuristics: Strategic Planning on Large Language Models with Monte Carlo Tree Search for Automating Heuristic Optimization](https://mlsanity.com/paper/2502.11422/) (2025)
- [LLM-Driven Instance-Specific Heuristic Generation and Selection](https://mlsanity.com/paper/2506.00490/) (2025)
- [ARS: Automatic Routing Solver with Large Language Models](https://mlsanity.com/paper/2502.15359/) (2025)
- [Multilingual Performance Biases of Large Language Models in Education](https://mlsanity.com/paper/2504.17720/) (2025)
- [Towards a HIPAA Compliant Agentic AI System in Healthcare](https://mlsanity.com/paper/2504.17669/) (2025)
- [Combinatorial Optimization for All: Using LLMs to Aid Non-Experts in Improving Optimization Algorithms](https://mlsanity.com/paper/2503.10968/) (2025)
- [Assessing the Capability of Large Language Models for Domain-Specific Ontology Generation](https://mlsanity.com/paper/2504.17402/) (2025)
- [Can Large Language Models Solve Robot Routing?](https://mlsanity.com/paper/2403.10795/) (2024)
- [Leveraging Large Language Models to Develop Heuristics for Emerging Optimization Problems](https://mlsanity.com/paper/2503.03350/) (2025)
- [Large Language Models for the Automated Analysis of Optimization Algorithms](https://mlsanity.com/paper/2402.08472/) (2024)
- [Coverage of an Environment Using Energy-Constrained Unmanned Aerial Vehicles](https://mlsanity.com/paper/2007.03501/) (2020)
- [DynamicRouteGPT: A Real-Time Multi-Vehicle Dynamic Navigation Framework Based on Large Language Models](https://mlsanity.com/paper/2408.14185/) (2024)
- [INSIGHT: Bridging the Student-Teacher Gap in Times of Large Language Models](https://mlsanity.com/paper/2504.17677/) (2025)
- [Conversational Assistants to support Heart Failure Patients: comparing a Neurosymbolic Architecture with ChatGPT](https://mlsanity.com/paper/2504.17753/) (2025)

## Abstract (arXiv)

Real-world path planning tasks typically involve multiple constraints beyond simple route optimization, such as the number of routes, maximum route length, depot locations, and task-specific requirements. Traditional approaches rely on dedicated formulations and algorithms for each problem variant, making them difficult to scale across diverse scenarios. In this work, we propose a flexible framework that leverages large language models (LLMs) to solve constrained path planning problems directly from natural language input. The core idea is to allow users to describe routing tasks conversationally, while enabling the LLM to interpret and solve the problem through solution verification and iterative refinement. The proposed method consists of two integrated components. For problem types that have been previously formulated and studied, the LLM first matches the input request to a known problem formulation in a library of pre-defined templates. For novel or unseen problem instances, the LLM autonomously infers a problem representation from the natural language description and constructs a suitable formulation in an in-context learning manner. In both cases, an iterative solution generation and verification process guides the LLM toward producing feasible and increasingly optimal solutions. Candidate solutions are compared and refined through multiple rounds of self-correction, inspired by genetic-algorithm-style refinement. We present the design, implementation, and evaluation of this LLM-based framework, demonstrating its capability to handle a variety of constrained path planning problems. This method provides a scalable and generalizable approach for solving real-world routing tasks with minimal human intervention, while enabling flexible problem specification through natural language.