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

📄 arXiv: 2410.16456v1 📥 PDF

作者: Da JU, Song Jiang, Andrew Cohen, Aaron Foss, Sasha Mitts, Arman Zharmagambetov, Brandon Amos, Xian Li, Justine T Kao, Maryam Fazel-Zarandi, Yuandong Tian

分类: cs.CL

发布日期: 2024-10-21

期刊: EMNLP 2024 Demo Track

💡 一句话要点

TTG：提出一种语言驱动的保证性旅行规划系统，解决复杂旅行安排问题。

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 旅行规划 自然语言处理 混合整数线性规划 大型语言模型 符号求解 合成数据 优化算法

📋 核心要点

  1. 旅行规划涉及航班、住宿和景点等多重约束，现有方法难以高效满足这些复杂且相互依赖的需求。
  2. TTG系统通过将自然语言请求转换为符号形式，并利用混合整数线性规划求解器，实现最优旅行行程的快速生成。
  3. 实验表明，TTG在自然语言到符号的翻译上达到91%的准确率，行程成本接近最优，用户净推荐值达到35-40%。

📝 摘要（中文）

本文提出了To the Globe (TTG)，一个实时的演示系统，它接受用户的自然语言请求，通过微调的大型语言模型将其翻译成符号形式，并使用混合整数线性规划求解器生成最优的旅行行程。整个系统大约需要5秒钟来回复用户的请求，并提供保证的行程。为了训练TTG，我们开发了一个合成数据管道，该管道基于真实世界数据集的统计数据，生成用户请求、航班和酒店信息的符号形式，无需人工标注。我们微调一个LLM，将NL用户请求翻译成符号形式，然后将其发送到符号求解器以计算最优行程。我们的NL-符号翻译在反向翻译指标中实现了约91%的精确匹配（即，生成的自然语言的估计符号形式是否与groundtruth匹配），并且其返回的行程与ground truth用户请求的最优成本相比，比率为0.979。在用户评估中，TTG在生成的行程上实现了持续较高的净推荐值（NPS），达到35-40%。

🔬 方法详解

问题定义：旅行规划是一个复杂且耗时的任务，需要满足多个相互依赖的约束条件，包括航班、住宿、景点和其他旅行安排。现有的旅行规划方法通常难以在合理的时间内找到满足所有约束条件的最优行程，尤其是在用户需求复杂多样的情况下。

核心思路：TTG的核心思路是将用户的自然语言请求转化为符号形式，然后利用符号求解器（如混合整数线性规划求解器）来寻找最优的旅行行程。这种方法结合了自然语言处理的灵活性和符号求解器的精确性，能够在保证行程质量的同时，提高规划效率。

技术框架：TTG系统主要包含三个模块：1) 自然语言理解模块：使用微调的大型语言模型（LLM）将用户的自然语言请求翻译成符号形式。2) 符号求解模块：使用混合整数线性规划（MILP）求解器，根据符号化的用户请求和旅行数据（如航班、酒店信息）生成最优的旅行行程。3) 合成数据生成模块：用于生成训练LLM所需的合成数据，包括用户请求、航班和酒店信息等。

关键创新：TTG的关键创新在于将自然语言处理和符号求解相结合，实现了一种高效且保证质量的旅行规划方法。此外，该系统还提出了一种合成数据生成管道，可以自动生成训练数据，无需人工标注，降低了开发成本。

关键设计：TTG使用微调的LLM进行自然语言到符号的翻译，通过合成数据进行训练，保证了翻译的准确性。混合整数线性规划求解器用于寻找满足所有约束条件的最优行程。合成数据生成管道基于真实世界数据集的统计数据，保证了生成数据的真实性和多样性。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

TTG系统在自然语言到符号的翻译上实现了约91%的精确匹配。生成的行程成本与ground truth用户请求的最优成本相比，比率为0.979，表明生成的行程非常接近最优解。用户评估显示，TTG在生成的行程上实现了持续较高的净推荐值（NPS），达到35-40%。

🎯 应用场景

TTG系统可应用于在线旅行社、旅游规划App等领域，为用户提供个性化、高效的旅行规划服务。该系统能够处理复杂的旅行约束，并保证行程的最优性，从而提高用户满意度，并可能扩展到其他需要复杂约束优化的领域，例如物流、调度等。

📄 摘要（原文）

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 ~5 seconds to reply to the user request with guaranteed itineraries. To train TTG, we develop a synthetic data pipeline that generates user requests, 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.