AI-Powered Trip Planning: MIT and IBM Watson AI Lab Revolutionize Personalized Travel
Navigating the complexities of travel planning often involves juggling numerous logistics, from transportation and accommodations to meals and attractions. While large language models (LLMs) hold promise as tools for this task, their ability to handle complex logistical and mathematical reasoning, as well as problems with multiple constraints, has been limited. Recent studies have shown that state-of-the-art LLMs provide viable trip planning solutions only 4% of the time, even with additional tools and APIs.
To address this challenge, a research team from MIT and the MIT-IBM Watson AI Lab has developed a novel framework that combines LLMs with algorithms and a complete satisfiability solver, significantly improving the success rate of LLM solutions for complex problems like trip planning. This innovative approach aims to create a user-friendly AI travel broker capable of developing realistic, logical, and complete travel plans.
Chuchu Fan, associate professor in the MIT Department of Aeronautics and Astronautics (AeroAstro) and the Laboratory for Information and Decision Systems (LIDS), explains that many planning problems are inherently combinatorial optimization problems, requiring the satisfaction of several constraints in a certifiable way. The team’s work leverages machine learning, control theory, and formal methods to develop safe and verifiable control systems for robotics, autonomous systems, controllers, and human-machine interactions.
The framework utilizes LLMs to translate natural language descriptions of travel plans into problems that a solver can handle. Solvers, mathematical tools that rigorously check if criteria can be met, require complex computer programming for use. By combining LLMs with solvers, the researchers have created a system that allows users to plan trips in a timely manner, without the need for programming knowledge or extensive research into travel options.
If a user’s constraint cannot be met, the new technique identifies and articulates the issue, proposing alternative measures. The user can then choose to accept, reject, or modify these suggestions until a valid plan is formulated, if one exists.
The “travel agent” operates in four steps: parsing the user’s requested travel plan prompt, converting the steps into executable Python code with natural language annotations, calling APIs to collect data, and using the SMT solver to execute the steps laid out in the constraint satisfaction problem. If a solution is found, the solver outputs the result to the LLM, which then provides a coherent itinerary to the user. If constraints cannot be met, the framework identifies the conflicting constraints and provides potential remedies to the user.
The researchers tested their method using GPT-4, Claude-3, or Mistral-Large as the method’s LLM, achieving over a 90 percent pass rate, compared to 10 percent or lower for the baselines. The team also explored the addition of a JSON representation within the query step, which further made it easier for the method to provide solutions with 84.4-98.9 percent pass rates.
The MIT-IBM team also applied their framework to other domains with tasks like block picking, task allocation, the traveling salesman problem, and warehouse optimization. This demonstrates the generalizability and robustness of their planning solution.
Co-authors of the paper on this work include Yang Zhang, Yilun Hao, and Yongchao Chen. The research was recently presented at the Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics.
