TravelPlanner: A Benchmark for Real-World Planning with Language Agents

Jian Xie, Kai Zhang, Jiangjie Chen, Tinghui Zhu, Renze Lou, Yuandong Tian, Yanghua Xiao, Yu Su

TL;DR

The paper introduces TravelPlanner, a challenging new benchmark designed to evaluate large language model (LLM) agents on multi-constraint, long-horizon planning tasks using a real-world travel scenario. The evaluation reveals a stark reality check for current AI: even state-of-the-art models like GPT-4 achieve a mere 0.6% success rate when required to search for information and plan simultaneously. This benchmark highlights a massive gap between current language agents and human-level planning capabilities.

What Problem Does This Paper Address?

While LLMs have shown impressive performance in tool use and isolated reasoning tasks, evaluating their ability to plan in complex, unconstrained real-world environments remains difficult. Existing benchmarks often focus on single-objective optimization with fixed ground truths (like Blocksworld) or simple web navigation.

Real-world planning, such as organizing a multi-day vacation, is inherently more difficult. It requires an agent to:

  1. Manage long horizons: Make dozens of interdependent decisions regarding flights, hotels, restaurants, and attractions.
  2. Handle multiple constraints: Simultaneously satisfy explicit user preferences (e.g., budget, room type) and implicit commonsense constraints (e.g., not booking a lunch in a city you haven't arrived in yet).
  3. Proactively collect information: Search through massive, partially observable environments using tools.

To bridge this gap, the authors created TravelPlanner to see if today's language agents can truly operate as robust real-world planners.

Figure 1. Overview of TravelPlanner. Given a query, language agents are tasked with employing various search tools to gather information. Based on the collected information, language agents are expected to deliver a plan that not only satisfies the user’s needs specified in the query but also adheres to commonsense constraints.

Methods

The authors evaluate language agents using two distinct settings:

  • Two-Stage Mode (Tool-Use + Planning): The agent is given a natural language query and must proactively use six environment tools to gather information, save relevant data to a digital "Notebook" (simulating working memory), and then compile a final itinerary using a Planner tool.
  • Sole-Planning Mode: To isolate planning skills from information retrieval errors, this simplified mode provides the agent with all necessary, pre-filtered information (such as available flights and restaurants) directly in the context window.

The evaluation framework automatically parses the generated itineraries and grades them on three constraint tiers: environment constraints, commonsense constraints (e.g., no repeating attractions, reasonable city routes), and hard constraints (user-specified preferences like budget or cuisine).

Datasets

The paper introduces the TravelPlanner benchmark, which consists of:

  • A Sandbox Environment: A static database containing nearly 4 million data records crawled from the internet, including flight statuses, distance matrices, restaurant options, attractions, and accommodations.
  • 1,225 Curated Queries: Divided into training (45), validation (180), and test sets (1,000). The queries span three difficulty levels (Easy, Medium, Hard) and three travel durations (3, 5, or 7 days), which dictate the number of cities visited and constraints imposed.
  • Human-Annotated Reference Plans: Created by 20 graduate students to ensure that every query has at least one valid, feasible solution.

Key Insights and Ideas

  • The "Multitasking Tax" on Cognitive Capacity: LLMs suffer a severe performance drop when forced to collect information and plan at the same time. GPT-4's success rate drops from 4.4% in sole-planning mode to 0.6% in the two-stage mode, suggesting that language agents have a limited "cognitive capacity" when multitasking.
  • Micro-Success vs. Macro-Failure: Agents often achieve high micro pass rates (satisfying individual constraints like finding the right cuisine), but fail miserably at macro pass rates (satisfying all constraints holistically). They struggle to maintain a global view of the plan.
  • Stubborn Dead Loops: When agents receive negative feedback from the environment (e.g., "No flights found"), they frequently fail to dynamically adjust their strategy. Instead, they get trapped in repetitive loops, executing the exact same invalid action multiple times.
Figure 2. Tool-use error distribution on the test set. An early stop will be triggered if the agent either makes three consecutive failed attempts or repetitive actions, indicating a dead loop.

Key Results

The quantitative results paint a sobering picture for autonomous agents:

  • Two-Stage Performance: GPT-4-Turbo (using the ReAct framework) was the only model capable of completing any tasks, achieving a 0.6% final pass rate on the test set. Other prominent models, including Gemini Pro, GPT-3.5-Turbo, and Mixtral-8x7B, scored 0%.
  • Sole-Planning Performance: Even when handed all the correct data on a silver platter, GPT-4 only managed a 4.4% success rate, proving that multi-constraint satisfaction itself is a major bottleneck.
  • Traditional Baselines: A standard rule-based Greedy Search baseline also scored 0%, as it optimized purely for cost and could not navigate the complex web of user and commonsense constraints.

The authors note that agents frequently fail due to argument errors in tool usage, date confusion (e.g., searching for 2023 flights in a 2022 database), and hallucinating fictitious details when they fail to find data.

Figure 3. Case studies of failures. Agents fail to finalize plans due to repeated errors like incorrect dates, confusion with information details leading to hallucinatory answers, and disconnects between reasoning and actions. All cases are gained from GPT-4-Turbo based agents. For details of GPT-4-Turbo with the Reflexion strategy, please refer to Appendix B.2. We provide more cases in Appendix C.2.

Limitations and Future Work

The authors acknowledge a few key limitations:

  • Static Sandbox: The environment is static to ensure reproducible and unbiased evaluation, meaning it doesn't capture the real-time volatility of live web data.
  • Subjective Commonsense: The definition of "commonsense" constraints is based on author consensus, which may vary across different cultures and contexts.

Future Directions: The dismal success rates indicate that standard prompting strategies (like ReAct or Reflexion) are insufficient for complex planning. The authors suggest that future research must focus on developing more sophisticated strategies, such as explicit backtracking mechanisms to recover from dead ends, better working memory management, and training agents via reinforcement learning from environment feedback.

Summary updated

Abstract

Planning has been part of the core pursuit for artificial intelligence since its conception, but earlier AI agents mostly focused on constrained settings because many of the cognitive substrates necessary for human-level planning have been lacking. Recently, language agents powered by large language models (LLMs) have shown interesting capabilities such as tool use and reasoning. Are these language agents capable of planning in more complex settings that are out of the reach of prior AI agents? To advance this investigation, we propose TravelPlanner, a new planning benchmark that focuses on travel planning, a common real-world planning scenario. It provides a rich sandbox environment, various tools for accessing nearly four million data records, and 1,225 meticulously curated planning intents and reference plans. Comprehensive evaluations show that the current language agents are not yet capable of handling such complex planning tasks-even GPT-4 only achieves a success rate of 0.6%. Language agents struggle to stay on task, use the right tools to collect information, or keep track of multiple constraints. However, we note that the mere possibility for language agents to tackle such a complex problem is in itself non-trivial progress. TravelPlanner provides a challenging yet meaningful testbed for future language agents.
BibTeX
@inproceedings{xie2024travelplanner,
  author = {Jian Xie and Kai Zhang and Jiangjie Chen and Tinghui Zhu and Renze Lou and Yuandong Tian and Yanghua Xiao and Yu Su},
  title = {{TravelPlanner: A Benchmark for Real-World Planning with Language Agents}},
  booktitle = {International Conference on Machine Learning},
  year = {2024},
  url = {https://openreview.net/forum?id=l5XQzNkAOe},
}
Figure