To the Globe ( TTG ): Towards Language-Driven Guaranteed Travel Planning (2024)

Abstract: Travel planning is a challenging and time-consuming task that aims to find an itinerary which satisfies multiple, interdependent constraints regarding flights, accommodations, attractions, and other travel arrangements. In this paper, we propose To the Globe (TTG), a real-time demo system that takes natural language requests from users, translates it to symbolic form via a fine-tuned Large Language Model, and produces optimal travel itineraries with Mixed Integer Linear Programming solvers. The overall system takes ~5seconds to reply to the user request with guaranteed itineraries. To train TTG, we develop a synthetic data pipeline that generates userrequests, flight and hotel information in symbolic form without human annotations, based on the statistics of real-world datasets, and fine-tune an LLM to translate NL user requests to their symbolic form, which is sent to the symbolic solver to compute optimal itineraries. Our NL-symbolic translation achieves ~91% exact match in a backtranslation metric (i.e., whether the estimated symbolic form of generated natural language matches the groundtruth), and its returned itineraries have a ratio of 0.979 compared to the optimal cost of the ground truth user request. When evaluated by users, TTG achieves consistently high Net Promoter Scores (NPS) of 35-40% on generated itinerary.

## introduction travel planning is a routine activity that typically requires a significant amount of human time and effort to find an optimal itinerary satisfying many implicit and explicit constraints which interact and change over time. ideally, a human would only need to provide natural language instructions (e.g., "i want to go to hawaii for three days with a budget of $1,000.") and an ai agent provides solutions which are optimal with respect to certain objectives (e.g., total expense) and feasible (i.e., satisfy all constraints). moreover, the quality of the agent's decision should be reliable enough such that humans can fully delegate the task, or approve with a glimpse of check. designing such an ai system remains non-trivial. first, it involves complex planning with potentially vague natural language instructions, sophisticated objectives and constraints (e.g., hotels, flights, restaurants, attractions, budgets) and requiring multiple back-and-forth reasoning steps without a clear and predefined decision path. despite impressive performance achieved by large language models (llms), they are still weak at complex reasoning and planning @xcite @xcite , and may hallucinate @xcite or be inconsistent @xcite , in particular during complicated reasoning. this raises concerns on whether its decision can be trusted @xcite . second, travel planning is a time-dependent task that requires constantly re-planning due to ever-changing situations. even with exactly the same request, the optimal itinerary may be different given varying prices and availability. third, such a decision is highly personalized depending on the private constraints and preferences. users may speak a few brief words and expect the agent to give a solution that satisfies all of their implicit constraints, which can be quite subtle to capture from past conversations. in this paper, we propose ttg, a demo system that takes natural language instructions from users and outputs optimal travel itineraries in seconds. to achieve this, our system leverages the power of llms and existing symbolic solvers, e.g., mixed integer linear programming (milp). it first converts natural language instructions into a symbolic representation, which is solved by the symbolic solver, and then replies to the user with natural language outputs and a rich visualization. compared to pure llm-based systems (e.g., claudeatlas foot_0 , expedia romie foot_1 ), ttg provides an up-to-date, precise and executable itinerary with guarantees, in almost real time (∼ 5 seconds per request). ## overview of ttg fig. 1 shows the front-end interface of ttg. users can obtain travel itineraries in a few seconds by sending natural language requests in the semitransparent dialog box. users can also visualize candidate itineraries on the rendered map of the globe, and select based on their preferences. we use a hybrid design leveraging both llms and symbolic solvers that can deal with natural language input and still guarantee the feasibility and optimality of the output itineraries, if user requests are translated correctly by the fine-tuned llm. ## conclusion and future work in this work, we propose ttg, and end to end system which plans travel itineraries from user requests in natural language. ttg uses a hybrid architecture that combines an llm with combinatorial solvers, dynamically formulating travel requests into a well-defined milp problem, and translating the solution computed by the solver back to natural language. overall, the system responds almost in real-time (∼ 5 seconds), and outputs feasible and optimal guaranteed travel itineraries, given correctly understood user requests by the finetuned llm, which @xmath0. for this, a data generation pipeline is developed to provide synthetic symbolic and natural language pairs for model training. we recognize that achieving true optimality requires a system that enables robust personalization, and human-driven filtering and selection. as a result, we anticipate the need for a human benchmark task that enables respondents to stipulate a travel goal in real time and compare between a few near-optimal results, both to measure system performance and to collect signal for improvement. future developments will therefore explore multiround dialog and personalization to further improve user experience, and end-to-end trainable pipelines to make the system more adaptive.