Advances in customized artificial intelligence travel scheduling

Advances in customized artificial intelligence travel scheduling

Feeling Stuck with Travel Plans? AI Travel Brokers to the Rescue!

Traveling can be a hassle, especially when planning logistics like transportation, accommodations, meals, and lodging. For those curious about leveraging large language models (LLMs) to manage these tasks, it seems like an attractive solution due to their natural language capability, commonsense reasoning, and ability to gather information. However, researchers have found that state-of-the-art LLMs struggle with complex logistical reasoning and problems involving multiple constraints, making them impractical for tasks like trip planning more often than not.

The MIT and MIT-IBM Watson AI Lab team recognized this issue and decided to refocus the problem as a combinatorial optimization challenge involving multiple constraints. "These planning problems are naturally combinatorial optimization problems," said Chuchu Fan, an associate professor in MIT's Department of Aeronautics and Astronautics and the Laboratory for Information and Decision Systems. With their expertise in machine learning, control theory, and formal methods, they aimed to develop a user-friendly AI travel broker capable of creating logical, realistic, and complete travel plans, even in complex situations.

The researchers combined LLMs with algorithms and a complete satisfiability solver to create this AI travel broker. Solvers are powerful mathematical tools that rigorously check if certain criteria can be met and how, but they require complex programming and are time-consuming to use. By teaming them with LLMs, the researchers hoped to provide a quick, user-friendly solution for trip planning. If a user's constraints cannot be met, the new technique identifies the issues and suggests alternatives to the user, allowing for flexible solutions and easy adjustments until a valid plan is developed.

"Our idea is not to ask LLMs to propose a travel plan," said Fan. "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 [and then provide that to the user]." This approach ensures that travel plans are not only creative but also feasible and practical.

Co-authoring a paper on the work with Fan were Yang Zhang of MIT-IBM Watson AI Lab, AeroAstro graduate student Yilun Hao, and graduate student Yongchao Chen of MIT LIDS and Harvard University. This work was recently presented at the Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics.

Breaking down the Solver

Math tends to be domain-specific. For example, in natural language processing, LLMs use regression to predict the next token or "word" in a series to analyze or create a document—a process effective for generalizing diverse human inputs. However, LLMs are not ideal for formal verification applications, like in aerospace or cybersecurity, where problem completeness and proven solutions are crucial to avoid safety issues. Here, solvers excel but require fixed formatting inputs and struggle with unsatisfiable queries—a weakness that the hybrid technique addresses, providing solutions for complex problems like trip planning that are intuitive for everyday people.

"The solver is really the key here, because when we develop these algorithms, we know exactly how the problem is being solved as an optimization problem," said Fan. Specifically, the research group used a solver called satisfiability modulo theories (SMT), which determines whether a formula can be satisfied. "With this particular solver, it's not just doing optimization. It's doing reasoning over a lot of different algorithms there to understand whether the planning problem is possible or not to solve. That's a pretty significant thing in travel planning. It's not a very traditional mathematical optimization problem because people come up with all these limitations, constraints, restrictions," notes Fan.

Translation in Action

The "travel agent" works in four steps:

1. The LLM takes a user's travel plan prompt and parses it into planning steps, considering preferences for budget, hotels, transportation, destinations, attractions, restaurants, and trip duration.
2. These steps are converted into executable Python code annotated for each constraint, which calls APIs like CitySearch, FlightSearch, etc., to gather data, and the SMT solver to begin executing the steps laid out in the constraint satisfaction problem.
3. If a sound and complete solution can be found, the solver outputs it to the LLM, which then provides a coherent itinerary to the user.
4. If one or more constraints cannot be met, the framework offers alternative solutions to the user, enabling them to decide on the best course of action until a solution (or the maximum number of iterations) is reached.

Generalizable and Robust Planning

The researchers tested their method using GPT-4, Claude-3, or Mistral-Large as the LLM against other baselines, such as GPT-4 alone, OpenAI o1-preview alone, GPT-4 with a tool to collect information, and a search algorithm that optimizes for total cost. Using the TravelPlanner dataset, they looked at multiple performance metrics and found that the new technique achieved over a 90% pass rate, compared to 10% or lower for the baselines. With the addition of a JSON representation for the query, the method could deliver solutions with 84.4-98.9% pass rates. The MIT-IBM team also explored the performance of their framework in additional scenarios, such as handling new, unseen constraints and paraphrased query-step and step-code prompts—results that showed excellent performance, especially with an 86.7% pass rate for the paraphrasing trial.

"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," said Hao.

This work was funded, in part, by the Office of Naval Research and the MIT-IBM Watson AI Lab.

1. With the development of an AI travel broker, researchers aim to simplify trip planning by combining large language models (LLMs) with algorithms and a complete satisfiability solver.
2. The AI travel broker, designed by the MIT and MIT-IBM Watson AI Lab team, is capable of creating logical, realistic, and complete travel plans even in complex situations.
3. In the process of creating travel plans, the LLM acts as a translator, converting the natural language description of the problem into a problem that a solver can handle, ensuring both creativity and feasibility.
4. The solver used in this process, specifically satisfiability modulo theories (SMT), determines whether a formula can be satisfied, allowing for the execution of complex travel plans with multiple constraints.
5. The AI travel broker's performance was tested against several baselines, demonstrating over a 90% pass rate, showcasing its effectiveness and potential for significant time savings in travel planning.

Read also: