Agentes de viagens ajudam a fornecer logística completa — como transporte, acomodações, refeições e hospedagem — para empresários, turistas e todos os demais. Para aqueles que buscam fazer seus próprios arranjos, os modelos de linguagem de grande porte (LLMs) parecem ser uma ferramenta poderosa para essa tarefa, devido à sua capacidade de interagir iterativamente usando linguagem natural, fornecer algum raciocínio sensato, coletar informações e utilizar outras ferramentas para auxiliar na tarefa em questão. No entanto, trabalhos recentes constataram que os LLMs de última geração enfrentam dificuldades com raciocínios logísticos e matemáticos complexos, bem como com problemas com múltiplas restrições, como planejamento de viagens, onde se constatou que fornecem soluções viáveis em 4% ou menos das vezes, mesmo com ferramentas e interfaces de programação de aplicativos (APIs) adicionais.

Posteriormente, uma equipe de pesquisa do MIT e do Laboratório de IA Watson do MIT-IBM reformulou a questão para verificar se seria possível aumentar a taxa de sucesso de soluções de LLM para problemas complexos. "Acreditamos que muitos desses problemas de planejamento são naturalmente um problema de otimização combinatória", em que é necessário satisfazer diversas restrições de forma certificável, afirma Chuchu Fan, professora associada do Departamento de Aeronáutica e Astronáutica (AeroAstro) do MIT e do Laboratório de Sistemas de Informação e Decisão (LIDS). Ela também é pesquisadora do Laboratório de IA Watson do MIT-IBM. Sua equipe aplica aprendizado de máquina, teoria de controle e métodos formais para desenvolver sistemas de controle seguros e verificáveis para robótica, sistemas autônomos, controladores e interações homem-máquina.

Observando a natureza transferível de seu trabalho para o planejamento de viagens, o grupo buscou criar uma estrutura amigável que pudesse atuar como um corretor de viagens de IA para ajudar a desenvolver planos de viagem realistas, lógicos e completos. Para isso, os pesquisadores combinaram LLMs comuns com algoritmos e um solucionador de satisfatibilidade completo. Solvers são ferramentas matemáticas que verificam rigorosamente se os critérios podem ser atendidos e como, mas exigem programação de computador complexa para uso. Isso os torna companheiros naturais dos LLMs para problemas como esses, em que os usuários desejam ajuda para planejar em tempo hábil, sem a necessidade de conhecimento de programação ou pesquisa sobre opções de viagem. Além disso, se a restrição de um usuário não puder ser atendida, a nova técnica pode identificar e articular onde está o problema e propor medidas alternativas ao usuário, que pode então optar por aceitá-las, rejeitá-las ou modificá-las até que um plano válido seja formulado, se houver.

“Todos terão que lidar com as diferentes complexidades do planejamento de viagens em algum momento. Há diferentes necessidades, requisitos, restrições e informações do mundo real que você pode coletar”, diz Fan. “Nossa ideia não é pedir aos LLMs que proponham um plano de viagem. Em vez disso, um LLM atua como um tradutor para traduzir essa descrição em linguagem natural do problema para um problema que um solucionador possa lidar [e então fornecê-lo ao usuário]”, diz Fan.

Yang Zhang, do Laboratório de IA Watson do MIT-IBM, o aluno de pós-graduação da AeroAstro, Yilun Hao, e o aluno de pós-graduação Yongchao Chen, do MIT LIDS e da Universidade Harvard, são coautores de um artigo sobre o trabalho com Fan. Este trabalho foi apresentado recentemente na Conferência das Nações das Américas, Capítulo da Associação de Linguística Computacional.

A matemática tende a ser específica de um domínio. Por exemplo, no processamento de linguagem natural, os LLMs realizam regressões para prever o próximo token, também conhecido como "palavra", em uma série para analisar ou criar um documento. Isso funciona bem para generalizar diversas entradas humanas. Os LLMs sozinhos, no entanto, não funcionariam para aplicações formais de verificação, como na indústria aeroespacial ou de segurança cibernética, onde conexões de circuitos e tarefas de restrição precisam ser completas e comprovadas, caso contrário, brechas e vulnerabilidades podem passar despercebidas e causar problemas críticos de segurança. Nesse caso, os solucionadores se destacam, mas precisam de entradas com formatação fixa e lutam com consultas insatisfatórias. Uma técnica híbrida, no entanto, oferece a oportunidade de desenvolver soluções para problemas complexos, como planejamento de viagens, de uma forma intuitiva para pessoas comuns.

“O solucionador é realmente a chave aqui, porque quando desenvolvemos esses algoritmos, sabemos exatamente como o problema está sendo resolvido como um problema de otimização”, diz Fan. Especificamente, o grupo de pesquisa utilizou um solucionador chamado teorias do módulo de satisfatibilidade (SMT), que determina se uma fórmula pode ser satisfeita. “Com este solucionador em particular, não se trata apenas de otimização. Trata-se de raciocinar sobre vários algoritmos diferentes para entender se o problema de planejamento é ou não solucionável. Isso é algo bastante significativo no planejamento de viagens. Não é um problema de otimização matemática muito tradicional, porque as pessoas criam todas essas limitações, restrições e restrições”, observa Fan.

O "agente de viagens" funciona em quatro etapas que podem ser repetidas conforme necessário. Os pesquisadores usaram GPT-4, Claude-3 ou Mistral-Large como LLM do método. Primeiro, o LLM analisa o prompt de plano de viagem solicitado pelo usuário em etapas de planejamento, observando as preferências de orçamento, hotéis, transporte, destinos, atrações, restaurantes e duração da viagem em dias, bem como quaisquer outras prescrições do usuário. Essas etapas são então convertidas em código Python executável (com uma anotação em linguagem natural para cada uma das restrições), que chama APIs como CitySearch, FlightSearch, etc. para coletar dados e o solucionador SMT para começar a executar as etapas definidas no problema de satisfação das restrições. Se uma solução sólida e completa for encontrada, o solucionador envia o resultado para o LLM, que então fornece um itinerário coerente para o usuário.

Se uma ou mais restrições não puderem ser atendidas, o framework começa a procurar uma alternativa. O solucionador gera um código que identifica as restrições conflitantes (com sua anotação correspondente), que o LLM então fornece ao usuário com uma possível solução. O usuário pode então decidir como prosseguir até que uma solução (ou o número máximo de iterações) seja alcançado.

Os pesquisadores testaram seu método usando os LLMs mencionados acima em relação a outras linhas de base: GPT-4 sozinho, OpenAI o1-preview sozinho, GPT-4 com uma ferramenta para coletar informações e um algoritmo de busca que otimiza o custo total. Usando o conjunto de dados TravelPlanner, que inclui dados para planos viáveis, a equipe analisou várias métricas de desempenho: com que frequência um método poderia entregar uma solução, se a solução atendia a critérios de senso comum como não visitar duas cidades em um dia, a capacidade do método de atender a uma ou mais restrições e uma taxa de aprovação final indicando que ele poderia atender a todas as restrições. A nova técnica geralmente alcançou uma taxa de aprovação de mais de 90%, em comparação com 10% ou menos para as linhas de base. A equipe também explorou a adição de uma representação JSON dentro da etapa de consulta, o que tornou ainda mais fácil para o método fornecer soluções com taxas de aprovação de 84,4-98,9%.

A equipe MIT-IBM impôs desafios adicionais ao seu método. Eles analisaram a importância de cada componente da solução — como a remoção do feedback humano ou do solucionador — e como isso afetava os ajustes do plano para consultas insatisfatórias em 10 ou 20 iterações, usando um novo conjunto de dados criado por eles, chamado UnsatChristmas, que inclui restrições não vistas e uma versão modificada do TravelPlanner. Em média, a estrutura do grupo MIT-IBM obteve 78,6% e 85% de sucesso, que sobem para 81,6% e 91,7% com rodadas adicionais de modificação do plano. Os pesquisadores analisaram o quão bem ela lidou com restrições novas e não vistas e com prompts parafraseados de etapas de consulta e código de etapas. Em ambos os casos, o desempenho foi muito bom, especialmente com uma taxa de aprovação de 86,7% no teste de paráfrase.

Por fim, os pesquisadores do MIT-IBM aplicaram sua estrutura a outros domínios, com tarefas como seleção de blocos, alocação de tarefas, o problema do caixeiro-viajante e depósito. Nesse caso, o método deve selecionar blocos numerados e coloridos e maximizar sua pontuação; otimizar a atribuição de tarefas do robô para diferentes cenários; planejar viagens minimizando a distância percorrida; e concluir e otimizar tarefas do robô.

“Acho que esta é uma estrutura muito forte e inovadora que pode economizar muito tempo para os humanos e, além disso, é uma combinação muito inovadora do LLM e do solucionador”, diz Hao.

Este trabalho foi financiado, em parte, pelo Escritório de Pesquisa Naval e pelo Laboratório de IA Watson do MIT-IBM.