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

Resumo Técnico: Planejamento de Caminho com Restrições via LLMs

1. O Problema

O planejamento de caminhos no mundo real (logística, entregas, turismo) raramente se resume à otimização simples de rotas (como o Problema do Caixeiro Viajador clássico - TSP). Esses cenários envolvem múltiplas restrições complexas e específicas do usuário, como:

• Número de rotas e locais de depósito (depots).
• Comprimento máximo de rota e janelas de tempo.
• Requisitos específicos de tarefas (ex: priorizar locais "emocionantes" em vez de "tranquilos").

Desafios Atuais:

• Falta de Escalabilidade: Abordagens tradicionais dependem de formulações matemáticas dedicadas e algoritmos especializados para cada variante de problema. A introdução de novas restrições exige reengenharia do modelo e ajuste fino extensivo.
• Barreira de Entrada: Usuários não especialistas precisam traduzir requisitos em linguagem natural para formulações matemáticas estruturadas, o que é difícil e propenso a erros.
• Rigidez: Algoritmos existentes não conseguem adaptar-se facilmente a solicitações conversacionais ou problemas não vistos anteriormente.

2. Metodologia Proposta

Os autores propõem um framework flexível que utiliza Modelos de Linguagem Grandes (LLMs) para interpretar instruções em linguagem natural e resolver problemas de planejamento de caminho com restrições, sem a necessidade de formulação matemática manual prévia. O sistema opera através de dois caminhos integrados:

A. Arquitetura de Dois Caminhos:

1. Correspondência de Problemas (Pathway 1): Para tipos de problemas conhecidos (ex: TSP básico, VRP com janelas de tempo), o LLM compara a solicitação do usuário com uma biblioteca de "Casos de Planejamento de Caminho" pré-definidos. Se houver correspondência, o LLM extrai uma Formulação Estruturada do Problema (SPF) do banco de dados, que contém parâmetros, restrições matemáticas e formatos de saída padronizados.
2. Aprendizado em Contexto (Pathway 2): Para problemas novos ou não vistos, o LLM utiliza few-shot prompting (um exemplo de caso da biblioteca) para inferir autonomamente a representação do problema e gerar uma nova SPF estruturada a partir da descrição em linguagem natural.

B. Ciclo de Geração, Verificação e Refinamento Iterativo:

• Geração de Solução: O LLM usa a SPF para gerar uma rota candidata.
• Verificação de Restrições:
  • Se a SPF for conhecida, o sistema verifica matematicamente se as restrições (ex: visitar cada cidade uma vez, começar e terminar no depósito) foram violadas.
  • Se a SPF for gerada pelo LLM, o modelo realiza auto-verificação, analisando se a solução atende às restrições descritas na própria SPF gerada.
• Refinamento Iterativo (Estilo Algoritmo Genético):
  • Se violações forem detectadas, o LLM é instruído a corrigir a solução especificamente nas falhas identificadas.
  • Mesmo para soluções viáveis, o sistema executa múltiplas rodadas de geração. O LLM compara novas candidatas com as anteriores, buscando reduzir o custo total (distância) e selecionando a melhor solução viável.

3. Contribuições Principais

1. Pipeline Flexível de Linguagem Natural: Capacidade de resolver problemas de planejamento de caminho com restrições diretamente a partir de texto conversacional, eliminando a necessidade de formulação estruturada pelo usuário.
2. Sistema Híbrido de Adaptação: Combina correspondência com casos pré-existentes para eficiência e aprendizado em contexto para generalização em problemas inéditos.
3. Mecanismo de Auto-Verificação e Refinamento: Integração de um processo iterativo que garante a viabilidade das soluções (respeito às restrições) e melhora progressivamente a qualidade (otimização de custo), inspirado em algoritmos evolutivos.
4. Validação Empírica: Avaliação abrangente em diversos cenários de roteamento, demonstrando a escalabilidade e o potencial prático da abordagem.

4. Resultados Experimentais

Os experimentos foram conduzidos em quatro tipos de problemas (TSP básico, roteamento multi-dia com um depósito, multi-dia com depósitos diferentes, e casos mistos) usando LLMs de ponta (GPT-4-Turbo, Llama 3.3 70b).

• Viabilidade e Verificação:
  • Com o módulo de verificação, 95,38% das soluções foram válidas.
  • Sem o módulo de verificação, a taxa de soluções válidas caiu para 85,63%.
  • Isso confirma que a SPF e a verificação são cruciais para garantir que o LLM siga as restrições.
• Otimização de Custo (Refinamento Iterativo):
  • A iteração reduziu o custo total de viagem em 64% dos casos testados.
  • Tabela de Redução de Custo (Média):
    • Tipo 1: Redução de 5,28% (287.87 -> 272.66).
    • Tipo 2: Redução de 8,81% (589.45 -> 537.52).
    • Tipo 3: Redução de 8,78% (328.13 -> 299.31).
    • Tipo 4: Redução de 6,95% (460.21 -> 428.23).
• Formato de Saída: O uso de SPFs garantiu uma saída estruturada e consistente, facilitando a análise, enquanto prompts genéricos resultaram em textos descritivos difíceis de avaliar em escala.

5. Limitações e Futuro

• Garantia Teórica: Não há garantia de otimalidade global (os problemas são NP-difíceis). O LLM não pode provar que a solução é a melhor possível dentro de um fator de aproximação.
• Escalabilidade: O desempenho degrada significativamente com mais de 15-20 cidades. O LLM tende a cometer erros como omitir cidades, visitar locais repetidamente ou alucinar formatos de saída.
• Direção Futura: Os autores propõem uma abordagem híbrida onde o LLM converte a SPF em um modelo de Programação Linear Inteira (ILP), delegando a otimização final para um solver ILP tradicional, combinando a flexibilidade da linguagem natural com a precisão matemática.

6. Significado e Impacto

Este trabalho representa um avanço significativo na interação humano-máquina para sistemas autônomos. Ao permitir que usuários especifiquem tarefas complexas de roteamento em linguagem natural, o framework reduz a barreira de entrada para aplicações de logística e planejamento. A capacidade de generalizar para novos tipos de problemas sem reengenharia de algoritmos torna a tecnologia mais adaptável a cenários do mundo real dinâmicos e imprevisíveis. A integração de verificação iterativa resolve um dos maiores pontos fracos do uso de LLMs em tarefas críticas: a falta de confiabilidade e consistência nas restrições.