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

1. Problem Statement

Real-world path planning tasks (e.g., logistics, delivery, travel) often involve complex, user-defined constraints beyond simple route optimization. These include:

• Variable Constraints: Number of routes, maximum route length, specific depot locations, time windows, and scheduling requirements.
• Scalability Issues: Traditional approaches rely on dedicated mathematical formulations and specialized algorithms (e.g., for TSP, VRP, Capacitated VRP) for each specific problem variant. This requires expert knowledge and extensive tuning, making it difficult to scale to diverse or novel scenarios.
• The Gap: There is a need for a system that can accept natural language (NL) instructions, interpret complex constraints without manual formulation, and generate feasible, optimized routes without requiring the user to define a structured mathematical model.

2. Methodology

The authors propose a flexible framework that leverages Large Language Models (LLMs) to solve constrained path planning problems directly from natural language input. The system operates via a two-pathway architecture combined with an iterative verification and refinement loop.

A. Two-Pathway System

The system determines how to process an input based on whether the problem matches known patterns:

1. Pathway 1: Problem Matching (Known Types)
   • The LLM analyzes the NL input and searches a pre-defined Case Library of structured problem formulations (SPFs).
   • If a match is found (e.g., a standard Traveling Salesperson Problem or a specific Vehicle Routing Problem variant), the LLM retrieves the corresponding SPF.
   • The SPF includes the objective, constraints (expressed as mathematical inequalities), and strict output format requirements.
2. Pathway 2: In-Context Learning (Novel Types)
   • If the input describes a novel or unseen problem type, the LLM cannot find a match.
   • Using single-shot prompting (providing one example of an NL-to-SPF conversion), the LLM autonomously infers the problem structure.
   • It generates a custom SPF and an initial solution without relying on pre-existing templates.

B. Iterative Solution Generation and Verification

Once a solution is generated (via either pathway), the system employs a Genetic Algorithm-inspired refinement process:

• Constraint Verification: The system checks if the candidate solution satisfies all constraints (e.g., visiting all cities exactly once, starting/ending at the correct depot).
  • With SPF: The system uses explicit mathematical inequalities to verify feasibility.
  • Without SPF: The LLM performs self-verification by checking its own output against the constraints it generated.
• Self-Correction: If violations are detected, the LLM is prompted to revise the solution, explicitly addressing the failed constraints.
• Iterative Optimization: The LLM generates multiple candidate solutions, compares them based on travel cost (objective function), and selects the best one. This cycle repeats until a feasible solution is found or a maximum iteration count is reached.

3. Key Contributions

1. Natural Language Interface for Routing: Developed a pipeline allowing users to specify complex routing tasks conversationally, eliminating the need for formal mathematical problem formulation.
2. Hybrid Problem Solving: Designed a dual-pathway system that handles both pre-studied problem types (via library matching) and novel specifications (via in-context learning), ensuring generalizability.
3. Iterative Verification Framework: Integrated a self-correction loop that ensures solutions are feasible (constraint-compliant) and progressively optimizes solution quality (minimizing cost).
4. Direct NL Output: Unlike previous works that required LLMs to generate executable code (Python/C++) to solve optimization problems, this framework enables the LLM to output structured natural language solutions directly.

4. Experimental Results

The framework was evaluated using state-of-the-art LLMs (GPT-4-Turbo, Llama3.3 70b) across four problem types:

1. Basic TSP (Single depot, single route).
2. Multi-day TSP (Single depot, multiple routes).
3. Multi-day TSP with changing depots (Different depot per day).
4. Mixed/Novel constraints (Self-generated SPF).

Key Findings:

• Feasibility: With the self-verification module, 95.38% of generated solutions were valid. Without verification, validity dropped to 85.63%.
• Optimality: Iterative refinement reduced total travel costs in 64% of cases.
  • Example: For Problem Type 2, average cost dropped from 589.45 (no iteration) to 537.52 (with iteration), an 8.81% reduction.
• Format Consistency: Structured Prompts (SPF) were crucial. Without them, LLMs struggled to produce parseable outputs, often violating constraints or failing to follow format.
• Scalability Limit: The system performed well on problems with up to 10–15 cities. Performance degraded significantly with >15–20 cities, leading to hallucinations (missing cities, repeated visits) and format errors.

5. Significance and Limitations

Significance:

• Democratization of Optimization: Makes complex routing optimization accessible to non-experts who can describe problems in plain English.
• Flexibility: Capable of adapting to new constraint combinations without re-engineering algorithms.
• Scalable Framework: Provides a generalizable approach for real-world routing where requirements change dynamically.

Limitations:

• No Theoretical Guarantees: As the underlying problems are NP-hard, the LLM cannot provide mathematical proofs of optimality or approximation bounds (unlike traditional approximation algorithms).
• Scalability: Current LLMs struggle with large-scale instances (>20 nodes), often producing invalid outputs that the verification module can detect but the LLM cannot reliably self-correct.

Future Work:
The authors propose a hybrid approach where the LLM converts the natural language constraints into an Integer Linear Programming (ILP) formulation, delegating the final optimization step to a conventional ILP solver to overcome scalability and optimality guarantees.