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

Introduction

• Travel planning is long-horizon and interdependent, combines explicit user and budget needs with commonsense constraints, and requires proactive information gathering in a partially observable environment.The benchmark targets a complexity the paper says is out of reach for prior AI agents.Source: §1 · p. 2
• TravelPlanner offers around four million Internet-crawled data entries through six tools and 1,225 diverse user queries with reference plans.Each query imposes a different combination of constraints.Source: §1 · p. 2
• GPT-4 satisfies all task constraints on 0.6% of tasks, while all other evaluated LLMs fail to complete any tasks.The paper evaluates five LLMs and four planning strategies for producing complete plans and following constraints.Source: §1 · p. 2
• ReAct and Reflexion are insufficient for TravelPlanner’s multi-constraint tasks, where agents struggle to turn reasoning into correct actions and track global constraints; common failures include tool-argument errors, dead loops, and hallucinations.The authors argue that more sophisticated planning strategies are needed to approach human-level planning.Source: §1 · p. 2
• Human annotators take an average of 12 minutes to annotate a plan, compared with 1–2 minutes for a language agent to produce one automatically.The authors frame this speed as a possible route toward automating tedious planning tasks, despite agents’ low constraint-satisfaction success.Source: §1 · p. 2

2.1. Large Language Model based Agents

• LLM-powered agents use memory, tool use, and planning modules; examples include AutoGPT, BabyAGI, and HuggingGPT (Shen et al., 2023).Memory approaches include summarization (Chen et al., 2023; Zhou et al., 2023; Liang et al., 2023) and retrieval (Andreas, 2022; Park et al., 2023; Zhong et al., 2023), while external-tool interaction has been validated (Nakano et al., 2021; Lu et al., 2023; Ge et al., 2023; Xie et al., 2023).Source: §2.1 · p. 3

2.2. Planning

• Prior planning methods use task decomposition and step-by-step reasoning, search structures such as trees and graphs, and environmental feedback, but their effectiveness under multiple constraints remains uncertain.Relevant work includes Wei et al. (2022), Yuan et al. (2023), Zheng et al. (2024), Yao et al. (2023), Besta et al. (2023), Yao et al. (2022), and Shinn et al. (2023).Source: §2.2 · p. 3

2.3. Evaluation of Language Agents

• TravelPlanner addresses evaluations that may miss real-world complexity by testing whether agents can generate feasible solutions across varied objectives, or constraints.Earlier evaluations focus on single objectives and fixed ground truths.Source: §2.3 · p. 3
• Prior agent evaluations commonly focus on arithmetic reasoning, tool use, or web navigation, assessing correct answers, tool proficiency, or locating specific websites.Examples include Roy & Roth (2015), Cobbe et al. (2021), Patel et al. (2021); Li et al. (2023), Xu et al. (2023), Zhuang et al. (2023); and Deng et al. (2023), Zhou et al. (2024), Liu et al. (2024).Source: §2.3 · p. 3

3.1. Overview

• TravelPlanner contains 1,225 queries across nine groups, split into 45 training, 180 validation, and 1,000 test queries.The groups vary by travel duration and number of hard constraints; training queries have human-annotated plans.Source: §3.1 · p. 3

3.2. Constraint Introduction

• Plans are tested against environment, commonsense, and hard constraints, covering adaptation to unavailable options, sensible choices, and personalized user needs.Hard constraints assess generalization to user needs; environment constraints test whether agents adjust plans when travel options are unavailable.Source: §3.2 · pp. 3–4

3.3. Benchmark Construction Pipeline

• Queries vary across 3-, 5-, and 7-day trips and increasing user constraints; 20 graduate students annotated feasible plans, which authors reviewed and used to recalibrate budgets.Three-, five-, and seven-day plans cover one, two, and three cities, respectively; query difficulty adds budget, cuisine, room, and transportation constraints.Source: §3.3 · pp. 4–5

3.4. Evaluation

• Evaluation measures delivery within 30 steps, final feasibility, and commonsense and hard-constraint pass rates, with micro and macro rates distinguishing individual constraints from holistic compliance.Micro rates count passed constraints over applicable constraints; macro rates count plans that pass all constraints of the relevant type.Source: §3.4 · p. 5

3.5. Sole-Planning Setting

• Sole-planning mode isolates planning skill by supplying human-annotated destination cities and necessary information, eliminating the need for agents to gather information through tools.The benchmark’s two-stage mode assesses agents’ overall tool-use and planning abilities.Source: §3.5 · pp. 5–6

4. Experiments

• Zero-shot experiments compare LLMs using ReAct for two-stage information collection with LLMs using different strategies in sole-planning mode.The tested models have context windows exceeding 8K; the lineup includes GPT-3.5-Turbo, GPT-4-Turbo, Gemini Pro, Mistral-7B-32K, and Mixtral-8x7B-MoE.Source: §4 · p. 6, §4.1 · p. 6

4.1. Baselines

• Baselines include cost-optimizing greedy search and Direct, ZS-CoT (Wei et al., 2022), ReAct (Yao et al., 2022), and Reflexion (Shinn et al., 2023).ToT (Yao et al., 2023) and GoT (Besta et al., 2023) are excluded because extensive search is prohibitively costly for TravelPlanner’s complexity.Source: §4.1 · p. 6

4.2. Main Results

• 0.6% final pass rate is achieved by GPT-4-Turbo with ReAct in two-stage mode, while none of the other LLMs passes any task.Even with all necessary information in sole-planning mode, ReAct and Reflexion struggle, and the best agent still falls short of greedy search on hard constraints.Source: §4.2 · pp. 6–7
• Across all metrics, two-stage scores are lower than sole-planning scores for every model, with the largest gap exceeding 30%.The comparison indicates difficulty handling information collection and planning at the same time.Source: §4.2 · p. 7
• Some agents achieve high micro scores but low macro scores, indicating that they satisfy some constraints while overlooking others.The pattern reflects difficulty considering multiple constraints holistically, a critical requirement for TravelPlanner tasks.Source: §4.2 · p. 7

5.2. Planning Error Analysis

• Agents’ constraint pass rates stay below 10% at every difficulty level and worsen as more constraints are added.Sole-planning mode improves performance over two-stage mode, but agents use tools less effectively than reference plans, often leaving information collection incomplete; the mismatch grows with trip duration.Source: Table 4 · p. 7, §5.2 · pp. 7–8, Table 5 · p. 7

5.1. Tool-Use Error Analysis

• Invalid actions account for 37.3% of GPT-4-Turbo errors and repetitive action loops for 6.0%, while other models also make tool-argument errors.Agents persist with invalid or null-result actions despite feedback, indicating difficulty adjusting plans to environmental feedback; information-collection mistakes also occur with GPT-4-Turbo and are more severe for Gemini Pro and Mixtral.Source: §5.1 · p. 7

5.2. Planning Error Analysis

• “Minimum Nights Stay” and “Budget” require global planning, but autoregressive agents struggle to anticipate outcomes across future branches.The paper identifies backtracking and heuristic forward-looking planning as strategies that could address this limitation.Source: §5.2 · p. 8

5.3. Case Studies

• Incorrect dates can yield null results and repeated failures, causing agents to stop planning without correcting their initial assumptions.This occurs even after preceding tool-use steps are executed correctly; the sandbox data is based on 2022.Source: §5.3 · p. 8, Figure 3 · p. 8
• Agents confuse information and hallucinate details, such as using the same flight number for departure and return flights (Liu et al., 2023b).The authors suggest this may reflect “Lost in the Middle” when agents face mass information.Source: §5.3 · p. 8, Figure 3 · p. 8
• Agents’ actions can diverge from their reasoning: despite recognizing the need to minimize costs, they may select more expensive items (Shinn et al., 2023).The authors identify this reasoning-action mismatch as impeding Reflexion’s delivery rate.Source: §5.3 · p. 8, Figure 3 · p. 8

• TravelPlanner assesses current language agents’ multi-constraint planning and tool-use abilities in real-world scenarios.Source: §6 · p. 8
• 0.6% is the final pass rate achieved by even the most advanced language agent frameworks, which struggle to account for all constraints and produce feasible plans.Source: §6 · p. 9
• The authors envision TravelPlanner as a catalyst for improving agents’ performance in increasingly complex scenarios and advancing AI capabilities.They identify its intricate logic and general applicability as important components in language-agent development.Source: §6 · p. 9

Impact Statements

• The authors aim for TravelPlanner to serve as an effective benchmark for complex-planning research.Some environment data comes from publicly available Internet sources and does not represent the authors’ viewpoints.Source: §7 · p. 9
• Because commonsense definitions differ, the authors base current evaluation criteria on consensus and invite discussion to improve coverage.Source: §7 · p. 9
• The authors will release evaluation scripts and encourage using evaluation feedback in training, including through reinforcement learning, to develop new methods.Source: §7 · p. 9
• The authors prohibit cheating on validation and test sets to preserve the fairness and reliability of benchmark evaluation.Source: §7 · p. 9

Appendices

• The supplementary material elaborates on these aspects.Source: Appendices · p. 12
• Appendix A covers benchmark details.Source: Appendices · p. 12
• Appendix B covers experiment details.Source: Appendices · p. 12
• Appendix C covers case presentation.Source: Appendices · p. 12

A.1. Dataset Distribution

• Table A.1 reports group distributions for the training, validation, and test sets.The supplied passages do not include the table’s group values.Source: §A.1 · p. 12, Table A.1 · p. 12

A.2. Tool Description

• Table A.2 provides tool descriptions and the number of database entries.The supplied passages do not include the entry counts.Source: §A.2 · p. 12, Table A.2 · p. 12
• The original data for each tool comes from publicly available Internet data.Source: §A.2 · p. 12
• The authors modify the source data to suit the benchmark’s requirements.Source: §A.2 · p. 12
• Modifications include adding, deleting, and altering data keys and values.Source: §A.2 · p. 12
• The authors say modifying the data effectively avoids data contamination; further details are in Appendix A.3.Source: §A.2 · p. 12

FlightSearch

• FlightSearch uses Kaggle flight records from 2022-03-01 to 2022-04-01 and generates price by multiplying distance by a random factor from 0.2 to 0.5.The retained fields include flight date, departure and arrival times, elapsed time, distance, and origin and destination city names.Source: §A.3 · pp. 12–13

DistanceMatrix

• DistanceMatrix uses Google Distance Matrix API results for driving distance and estimated travel time, with prices set to distance × 1 for self-driving and distance × 0.15 for taxi.Search results are stored in the database as a fixed dataset for evaluations.Source: §A.3 · p. 13

RestaurantSearch

• RestaurantSearch extracts restaurant names and average costs from the Kaggle Zomato dataset, then randomly assigns restaurants to cities and cuisines.The assigned cuisine categories include Chinese, American, Italian, Mexican, Indian, Mediterranean, Middle Eastern, Korean, Asian, and French.Source: §A.3 · p. 13

AttractionSearch

• AttractionSearch uses Google Places API data for each city, retaining each attraction’s name, address, phone, website, latitude, and longitude in a standardized dataset.Source: §A.3 · p. 13

AccommodationSearch

• AccommodationSearch extracts names, room types, prices, minimum nights, review ratings, and maximum occupancy from Kaggle Airbnb Open Data, then randomly assigns cities and room rules.Randomly assigned rules include no parties, smoking, children under 10, pets, or visitors.Source: §A.3 · p. 13

B.1. Baselines

• The baselines include cost-minimizing greedy search and four planning strategies: Direct, ZS-CoT (Wei et al., 2022), ReAct (Yao et al., 2022), and Reflexion (Shinn et al., 2023).Greedy search selects the first one or two cities, cheapest transport, restaurant, and accommodation, plus random daily attractions; only Direct is tested with four models, while the other strategies use GPT-3.5-Turbo.Source: §B.1 · p. 13

B.2. GPT-4-Turbo with Reflexion strategy in sole-planning mode.

• Table B.3 presents the validation-set results for GPT-4-Turbo using the Reflexion strategy, as identified in both the prose and the table caption.The supplied passages do not include the result values.Source: §B.2 · p. 13, Table B.3 · p. 14

B.3.1. TOOL-USE PROMPT

• The tool-use prompt requires interleaved Thought, Action, and Observation steps to collect valid transportation, dining, attraction, and accommodation information; nested tool use is prohibited.Available searches include flights, distances and travel costs, accommodations, restaurants, attractions, and cities.Source: §B.3.1 · p. 14
• Search results must be written to Notebook for Planner use, and the prompt directs agents to gather sufficient information before calling Planner.NotebookWrite follows searches or distance lookups, while each action calls only one function once and contains no added description.Source: §B.3.1 · pp. 14–15

B.3.2. DIRECT PLANNING PROMPT

• The Direct prompt requests a detailed, example-formatted plan using only supplied data, with commonsense details and explicit handling of travel days and the return to the departure city.It specifies details such as flight numbers, restaurant names, and accommodation names.Source: §B.3.2 · p. 15

B.3.3. REACT & REFLEXION PLANNING PROMPT

• The ReAct and Reflexion planning prompt alternates Thought, Action, and Observation, using CostEnquiry for a complete one-day subplan and Finish to submit the final plan.CostEnquiry takes the people count and plan in JSON format.Source: §B.3.3 · p. 16

B.3.4. QUERY GENERATION PROMPT

• The query-generation prompt converts JSON into a natural-language request and specifies that trips longer than three days use visiting_city_number to set destination-state coverage.Its examples illustrate encoding dates, travelers, budget, and travel preferences or constraints in the generated request.Source: §B.3.4 · p. 17

B.3.5. KEY COMPONENTS EXTRACTION PROMPT

• The key-components prompt extracts plans into JSON with day, current city, transportation, meals, attractions, and accommodation fields, standardizing attractions, transport details, and unspecified items.It formats multiple attractions with semicolons, aligns the current city to the transportation destination, preserves labels such as “Flight Number:” and “Cost:”, and removes dollar signs.Source: §B.3.5 · pp. 17–18

C.1. Example of Query and Reference Plan

• The example query requests a seven-day trip for five from Indianapolis through three Colorado cities, with a $15,100 budget, pet-friendly entire-room lodging, and four specified cuisines.The trip is dated March 11–17, 2022, and marked hard.Source: §C.1 · p. 19
• Days 1–3 drive from Indianapolis to Grand Junction, then Alamosa, with scheduled meals, attractions, and accommodations along the route.The reference plan includes a 19-hour-21-minute, 2,132-km first drive and a 4-hour-37-minute, 397-km drive from Grand Junction to Alamosa.Source: §C.1 · p. 19
• On days 4–5, the plan spends a day in Alamosa before driving to Denver and scheduling a zoo visit, meals, and lodging there.The day-5 drive is listed as 3 hours 38 minutes and 377 km.Source: §C.1 · pp. 19–20
• Day 6 schedules Denver meals, museums, and lodging, while day 7 drives back to Indianapolis and leaves the remaining itinerary fields blank.The return drive is listed as 15 hours 37 minutes and 1,747 km.Source: §C.1 · p. 20

C.2. Additional Case Study

• The additional case-study figures label cases 4–6 as using the two-stage mode.The figure captions do not provide further case outcomes in the supplied passages.Source: Figure C.1 · p. 21, Figure C.2 · p. 21, Figure C.3 · p. 22
• The remaining figures label cases 7–9 as direct-strategy sole-planning examples and case 10 as a Reflexion-strategy sole-planning example.The supplied captions identify strategies and planning mode, but not the cases’ results.Source: Figure C.4 · p. 22, Figure C.5 · p. 23, Figure C.6 · p. 23