Inroads to personalized AI trip planning
The dream of a truly personalized, effortlessly planned trip might soon be a reality, thanks to groundbreaking research from MIT and the MIT-IBM Watson AI Lab. While large language models (LLMs) have revolutionized many fields, their application in complex logistical tasks like travel planning has historically fallen short, often yielding viable solutions less than 4 percent of the time.
This challenge stems from LLMs’ struggles with intricate mathematical reasoning and multi-constraint problems. Recognizing this limitation, a research team led by Chuchu Fan, an associate professor at MIT’s Department of Aeronautics and Astronautics (AeroAstro) and the Laboratory for Information and Decision Systems (LIDS), approached the issue from a new angle. Fan, also a researcher at the MIT-IBM Watson AI Lab, believes that many planning problems are inherently ‘combinatorial optimization problems’ requiring certifiable constraint satisfaction.
The team’s innovative solution combines the natural language processing power of LLMs with the rigorous verification capabilities of algorithms and a complete satisfiability solver. This hybrid framework acts as an ‘AI travel broker,’ designed to produce realistic, logical, and comprehensive travel plans without requiring users to have programming knowledge or extensive research into options. Crucially, if a user’s specific constraints cannot be met, the system identifies the precise conflict and suggests actionable alternatives, allowing the user to refine their preferences until a valid plan emerges.
“Our idea is not to ask LLMs to propose a travel plan. Instead, an LLM here is acting as a translator to translate this natural language description of the problem into a problem that a solver can handle,” explains Fan. This elegant division of labor leverages LLMs (such as GPT-4, Claude-3, or Mistral-Large) for their human-like interaction and the solver, specifically a satisfiability modulo theories (SMT) solver, for its robust logical reasoning.
The ‘AI travel agent’ operates through a four-step iterative process: First, the LLM parses the user’s natural language travel prompt, extracting preferences like budget, accommodations, transportation, destinations, and trip duration. Second, these parsed preferences are converted into executable Python code, annotated with natural language descriptions of constraints, which then calls various APIs (e.g., CitySearch, FlightSearch) to gather necessary data. Third, the SMT solver processes these constraints to determine if a sound and complete solution exists. Finally, if a plan is found, the solver outputs the result to the LLM, which then crafts a coherent, user-friendly itinerary.
The results are remarkably impressive. Tested against baselines like GPT-4 alone or GPT-4 with simple tools, the new technique achieved over a 90 percent pass rate for delivering viable travel plans that satisfied all constraints, significantly outperforming baselines which typically yielded 10 percent or lower. The system also demonstrated strong adaptability to unseen constraints and paraphrased queries, proving its robustness and generalizability.
Beyond personalized travel, this powerful framework has proven its versatility by successfully tackling other complex planning challenges across diverse domains, including block picking, task allocation, the traveling salesman problem, and warehouse optimization. This demonstrates the broad applicability of combining intuitive LLM interaction with rigorous formal verification tools.
“I think this is a very strong and innovative framework that can save a lot of time for humans, and also, it’s a very novel combination of the LLM and the solver,” adds Yilun Hao, an AeroAstro graduate student and co-author of the paper presented at the Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics.
