HiMAP-Travel: Hierarchical Multi-Agent Planning for Long-Horizon Constrained Travel

The Viet Bui; Wenjun Li; Yong Liu

cs.AIMar 5, 2026

HiMAP-Travel: Hierarchical Multi-Agent Planning for Long-Horizon Constrained Travel

Authors: The Viet Bui, Wenjun Li, Yong Liu

Organizations: Singapore Management University

Abstract

Sequential LLM agents fail on long-horizon planning with hard constraints like budgets and diversity requirements. As planning progresses and context grows, these agents drift from global constraints. We propose HiMAP-Travel, a hierarchical multi-agent framework that splits planning into strategic coordination and parallel day-level execution. A Coordinator allocates resources across days, while Day Executors plan independently in parallel. Three key mechanisms enable this: a transactional monitor enforcing budget and uniqueness constraints across parallel agents, a bargaining protocol allowing agents to reject infeasible sub-goals and trigger re-planning, and a single policy trained with GRPO that powers all agents through role conditioning. On TravelPlanner, HiMAP-Travel with Qwen3-8B achieves 52.78% validation and 52.65% test Final Pass Rate (FPR). In a controlled comparison with identical model, training, and tools, it outperforms the sequential DeepTravel baseline by +8.67~~pp. It also surpasses ATLAS by +17.65~~pp and MTP by +10.0~pp. On FlexTravelBench multi-turn scenarios, it achieves 44.34% (2-turn) and 37.42% (3-turn) FPR while reducing latency 2.5x through parallelization.

Figures & tables

Method	Hierarchical	Parallel	Context	Global	Iterative	RL
	(Coord/Work)	Execution	Isolation	Verifier/CM	Refine/Neg.	Trained
ReAct ( Yao et al., 2022 )
Reflexion ( Shinn et al., 2023 )					✓
PMC ( Dang et al., 2025 )	✓
EvoAgent ( Yuan et al., 2025 )					✓
HIPLAN ( Li et al., 2025 )	✓				✓

Table 1: Feature-level comparison of representative agentic planning methods. ✓ denotes the method supports the feature. CM = Constraint Manager.

Figure 1: The HiMAP-Travel Architecture. The Coordinator projects the query into sub-goals $z_{d}$ . Parallel Executors generate day-plans $\tau_{d}$ while synchronizing via the Global State $\Sigma$ . If constraints are violated, the Bargaining Protocol triggers re-allocation.

Day	Sequential	HiMAP	Improvement
Day 1	98%	99%	+1 pp
Day 3	76%	95%	+19 pp
Day 5	42%	91%	+49 pp
Average	73.2%	95.0%	+21.8 pp

Table 2: Budget Satisfaction by Day (5-Day Trips)

Constraint-Level Analysis:
Metric	DeepTravel	HiMAP-Travel
Final Pass Rate	43.98%	52.65%
Commonsense Micro	93.28%	94.62%
Commonsense Macro	60.62%	67.00%
Hard Constraint Micro	45.66%	50.47%
Hard Constraint Macro	60.12%	66.05%

Table 3: Performance Comparison by Metric (Test Set, 8B Models)

Panel of Figure 2 — Figure 2: Training Dynamics. HiMAP-Travel (Red/Green) achieves superior Hard Constraint convergence vs sequential baseline.

		Validation (180 queries)					Test (1000 queries)
Method	Delivery	Commonsense		Hard Constr.		FPR	Commonsense		Hard Constr.		FPR
		Micro	Macro	Micro	Macro		Micro	Macro	Micro	Macro
Multi-Agent Frameworks (Published Results)
MTP (GPT-4 w/ hint)	96.7/97.4	87.29	43.33	47.14	46.67	33.33	91.46	50.00	53.96	45.12	42.68
ATLAS (Gemini-2.5-Pro)	100/100	48.33	88.54	82.62	74.44	44.44	85.81	40.50	77.64	70.60	35.00
Sequential RL Baseline (Our Evaluation)

Table 4: Performance on TravelPlanner Benchmark. We report results on both validation and test splits for representative methods. DeepTravel and HiMAP-Travel results are evaluated under the official TravelPlanner harness with identical experimental conditions. Complete baseline comparison is provided in Appendix C.2 .

Scenario	Method	Delivery	Commonsense		Hard Constraint		Final Pass
			Micro	Macro	Micro	Macro
2-Turn Local: Add local constraint (Cuisine, Room rule, or Room type) in Turn 2
Local Add Avg (#189)	ReAct (GPT-4)	100.00	85.84	44.41	67.29	43.72	29.58
	ATLAS (Gemini-2.5-Pro)	100.00	75.48	59.80	77.23	64.62	38.86
	HiMAP-Travel (4B)	100.00	76.80	61.25	79.15	66.50	41.25
	HiMAP-Travel (8B)	100.00	78.62	62.15	80.35	67.40	44.96

Table 5: Performance on FlexTravelBench: Multi-Turn Constraint Adaptation. Results show performance across 2-turn (single constraint addition) and 3-turn (sequential constraint revelation) scenarios. Numbers in parentheses indicate instance count. ATLAS and ReAct report per-constraint results (Cuisine, Room rule, Room type for Local; Budget, Number of People for Global). HiMAP-Travel reports aggregated results across all constraint types within each scenario. Micro: weighted by instance count; Macro: averaged across seeds.

Method	Latency (s)	Compute (s)	Tokens (k)
ReAct (Qwen3-8B)	180	180	12.5
DeepTravel (4B)	165	165	11.8
DeepTravel (8B)	190	190	12.3
HiMAP-Travel (4B)	48	120	13.8
HiMAP-Travel (8B)	72	210	14.2

Table 6: Computational Efficiency Metrics (7-Day Itinerary)

Configuration	FPR	$\Delta$
Full System	52.78%	—
w/o Synchronized Monitor	43.2%	-9.58 pp
w/o Coordinator	39.8%	-12.98 pp
w/o Bargaining	48.9%	-3.88 pp
w/o Parallelism	45.6%	-7.18 pp

Table 7: Ablation Study (Qwen3-8B, Validation)

Appendix figures & tables30 assets

Supplementary material from the paper’s appendix.

Appendix

State Fields	Description
$B_{total},B_{used}$	Global budget cap and cumulative spend
$V_{committed}$	Set of visited venues (restaurants, attractions)
$M_{trans}$	Inter-city transport mode lock
Operations	Semantics
check(action)	Validate action against $I(\Sigma)$ ; return OK or error code
commit(action)	Atomically update $\Sigma$ if valid; otherwise reject with error code

Appendix

Table 8: Synchronized Global State Interface

Tool Name	Agent Type	Function
Coordinator Tools
information_extractor	Coordinator	Parses natural language query $q$ into structured task tuple $\mathcal{T}_{q}=\langle q,\mathcal{C}_{hard},\mathcal{C}_{soft}\rangle$ containing origin, destination, days, budget, people, house rules, cuisine, room type, transportation restrictions, and dates
distribute_task	Coordinator	Implements hierarchical decomposition $q\to\{z_{1},\dots,z_{D}\}$ with city assignments, budget hints satisfying $\sum b_{d}\leq B_{total}$ , day types (departure/stay/travel/return), and globally selected ground transportation mode
Day Planner Search Tools
city_search	Day Planner	Returns all cities in a specified state from the TravelPlanner city database, sorted alphabetically
flight_search	Day Planner	Queries flight database by origin, destination, and date; returns flight numbers, times, and prices sorted by ascending cost

Appendix

Table 9: Complete Tool Library for HiMAP-Travel Agents

Benchmark	Statistic	Value
TravelPlanner (single-turn planning)
TravelPlanner	Splits (train/val/test)	45 / 180 / 1,000
TravelPlanner	Trip duration	3 / 5 / 7 days
TravelPlanner	Budget range	$900–$ 23,800
TravelPlanner	Group size range	1–8 people
TravelPlanner	Constraints	13 total (8 commonsense, 5 hard)

Appendix

Table 10: Benchmark statistics (TravelPlanner vs. FlexTravelBench).

	Training		Validation
Constraint Count	Count	%	Count	%
2–3 constraints	18	40.0	72	40.0
4 constraints	17	37.8	68	37.8
5+ constraints (Hard)	10	22.2	40	22.2

Appendix

Table 11: Distribution of Simultaneous Constraint Count

Statistic	Train (45)	Validation (180)
Mean Duration (days)	5.00 $\pm$ 1.63	5.00 $\pm$ 1.63
Mean Group Size	2.67 $\pm$ 1.86	2.46 $\pm$ 1.80
Mean Budget ($)	5,669 $\pm$ 4,556	5,296 $\pm$ 4,414
Budget Range ($)	900–19,400	900–23,800
Mean Cities Visited	1.67 $\pm$ 0.85	1.69 $\pm$ 0.87
Constraint Coverage	100%	100%

Appendix

Table 12: TravelPlanner Dataset Statistics (Train and Validation Splits)

Constraint	Validation Rule
Commonsense Constraints (8 total)
is_not_absent	All days must specify current_city , transportation , meals ( breakfast / lunch / dinner ), attraction , accommodation ; fields may be “-” (intentional omission) but not null
is_valid_information_in_sandbox	All venue names must exist in TravelPlanner databases with fuzzy name matching (substring containment) but strict city-state equality; detects hallucinated venues
is_valid_information_in_current_city	All activities must occur in current_city for that day; on travel days (“ from City1(State1) to City2(State2) ”), activities permitted in either city
is_reasonable_visiting_city	First city reachable from origin, last city connects back to origin for return, intermediate cities in destination state for multi-city trips
is_valid_restaurants	No restaurant may appear twice across all meals for all days; exact string matching on “ Name, City(State) ” format

Appendix

Table 13: TravelPlanner Constraint Taxonomy and Validation Rules (13 Total)

Difficulty Tier	Complexity Range	Train	Valid
Easy	9.0–20.0	15 (33.3%)	60 (33.3%)
Medium	20.1–45.0	15 (33.3%)	60 (33.3%)
Hard	45.1–63.0	15 (33.3%)	60 (33.3%)
Overall Mean $\pm$ Std	–	34.0 $\pm$ 22.2	34.0 $\pm$ 22.2

Appendix

Table 14: Task Complexity Distribution

Phase	Sequential	HiMAP	Speedup	% of Total
	(DeepTravel)	(Parallel)		(HiMAP)
Coordinator Planning	—	8.2 $\pm$ 1.4	—	11.4%
Day Planning (Executors)	145.3 $\pm$ 22	52.1 $\pm$ 8.3	2.79 $\times$	72.4%
Model Inference	98.7	35.4	2.79 $\times$	49.2%
Tool I/O (DB queries)	46.6	16.7	2.79 $\times$	23.2%
Bargaining Iterations	—	7.8 $\pm$ 3.2	—	10.8%

Appendix

Table 15: Detailed Latency Breakdown for 7-Day Itinerary (Qwen3-8B, seconds)

Duration	Sequential	HiMAP	Speedup	Scaling
	(seconds)	(seconds)		Factor
3 days	98 $\pm$ 15	48 $\pm$ 7	2.04 $\times$	1.0 $\times$
5 days	142 $\pm$ 21	58 $\pm$ 9	2.45 $\times$	1.21 $\times$
7 days	190 $\pm$ 28	72 $\pm$ 12	2.64 $\times$	1.50 $\times$
Growth Rate	Linear ( $O(D)$ )	Sub-linear	—	—

Appendix

Table 16: Latency Scaling by Trip Duration (Qwen3-8B)

Model	Sequential	HiMAP	Speedup
Qwen3-4B	165 $\pm$ 19	48 $\pm$ 6	3.44 $\times$
Qwen3-8B	190 $\pm$ 28	72 $\pm$ 12	2.64 $\times$

Appendix

Table 17: Latency by Model Size (7-Day Itinerary)

Commonsense Constraints
Constraint	4B Val	8B Val	$\Delta$	Category
Diverse Attractions	100.00	100.00	0.00	Strong
Diverse Restaurants	99.86	99.93	+0.07	Strong
Non-conflicting Transport	99.17	99.58	+0.41	Strong
Reasonable City Route	98.19	98.75	+0.56	Strong
Complete Information	92.10	96.52	+4.42	Strong

Appendix

Table 18: TravelPlanner: Constraint-Level Pass Rates (Averaged Across Seeds)

2-Turn Scenarios: Constraint Addition
Scenario	Model	Final Pass	Delivery	Commonsense	Commonsense	Hard Constraint
		Rate (%)	Rate (%)	Micro (%)	Macro (%)	Macro (%)
Local Add	4B	41.25	100.00	76.80	61.25	66.50
Local Add	8B	44.96	100.00	78.62	62.15	67.40
Global Add	4B	40.85	100.00	68.20	70.15	71.20
Global Add	8B	43.72	100.00	69.45	71.30	72.35

Appendix

Table 19: FlexTravelBench: Detailed Results by Scenario (matching Final Pass metric from Table 5 )

Metric	4B Val	8B Val	4B Test	8B Test
	(180)	(180)	(1000)	(1000)
Delivery Rate (%)	100.0 $\pm$ 0.0	100.0 $\pm$ 0.0	100.0 $\pm$ 0.0	100.0 $\pm$ 0.0
Commonsense Micro (%)	95.57 $\pm$ 2.15	95.64 $\pm$ 0.18	94.72 $\pm$ 0.25	94.62 $\pm$ 0.16
Commonsense Macro (%)	72.36 $\pm$ 2.15	73.61 $\pm$ 0.79	66.03 $\pm$ 1.50	67.00 $\pm$ 0.48
Hard Constraint Micro (%)	70.89 $\pm$ 1.54	76.85 $\pm$ 0.52	46.44 $\pm$ 0.84	50.47 $\pm$ 0.80
Hard Constraint Macro (%)	59.17 $\pm$ 2.08	63.33 $\pm$ 0.83	63.45 $\pm$ 1.26	66.05 $\pm$ 1.01

Appendix

Table 20: Complete Evaluation Results: HiMAP-Travel on TravelPlanner Benchmark

Metric	4B Val	4B Test	8B Val	8B Test
Delivery Rate	100.0	100.0	100.0	100.0
Commonsense Micro	95.57	94.72	95.64	94.62
Commonsense Macro	72.36	66.03	73.61	67.00
Hard Constraint Micro	70.89	46.44	76.85	50.47
Hard Constraint Macro	59.17	63.45	63.33	66.05
Final Pass Rate	48.61	49.80	52.78	52.65

Appendix

Table 21: Validation vs Test Split Comparison

Validation Set (180 queries)
Model	Split	Method	Delivery	Comm.	Comm.	Hard	Hard	FPR
				Micro	Macro	Micro	Macro
4B	validation	DeepTravel	96.81 $\pm$ 1.94	90.00 $\pm$ 2.22	59.58 $\pm$ 8.82	63.15 $\pm$ 3.76	49.44 $\pm$ 4.04	35.28 $\pm$ 7.38
4B	validation	HiMAP-Travel	100.0 $\pm$ 0.0	95.57 $\pm$ 2.15	72.36 $\pm$ 2.15	70.89 $\pm$ 1.54	59.17 $\pm$ 2.08	48.61 $\pm$ 2.15
8B	validation	DeepTravel	97.64 $\pm$ 4.09	92.60 $\pm$ 3.63	67.64 $\pm$ 5.13	71.43 $\pm$ 2.48	58.61 $\pm$ 2.13	45.56 $\pm$ 6.49
8B	validation	HiMAP-Travel	100.0 $\pm$ 0.0	95.64 $\pm$ 0.18	73.61 $\pm$ 0.79	76.85 $\pm$ 0.52	63.33 $\pm$ 0.83	52.78 $\pm$ 0.79

Appendix

Table 22: Controlled Comparison: HiMAP-Travel (Hierarchical) vs DeepTravel (Sequential)

Tier	Method	Count	FPR	Budget	Diversity
				Violation	Score
Easy	DeepTravel	333	61.3 $\pm$ 8.5	2.8%	94.2%
Easy	HiMAP-Travel	333	72.4 $\pm$ 1.2	1.9%	97.1%
	Improvement	–	+11.1 pp	-0.9 pp	+2.9 pp
Medium	DeepTravel	334	44.8 $\pm$ 9.2	4.5%	89.7%
Medium	HiMAP-Travel	334	56.3 $\pm$ 0.8	3.2%	93.5%

Appendix

Table 23: Performance by Difficulty Tier: HiMAP vs DeepTravel (8B models, test set)

Difficulty Tier	Count	Final Pass Rate	Budget Violation	Diversity Score	Avg. Latency (s)
Easy	60	78.3% (47/60)	2.1%	94.7%	58
Medium	60	65.0% (39/60)	4.2%	91.5%	67
Hard	60	36.8% (22/60)	4.1%	87.2%	72
Overall	180	52.78%	4.1%	92.0%	68

Appendix

Table 24: Baseline System Performance Across Difficulty Tiers

Constraint Type	Easy	Medium	Hard	Overall
Budget Adherence	97.9%	96.3%	91.2%	95.2%
Cuisine Requirements	95.8%	89.7%	82.7%	89.4%
Room Type/Capacity	96.2%	92.1%	87.3%	91.7%
Restaurant Diversity	97.1%	93.2%	78.3%	92.3%
Attraction Diversity	95.4%	91.5%	76.7%	90.1%
Transportation Mode	98.3%	95.1%	89.7%	94.5%

Appendix

Table 25: Constraint-Specific Pass Rates by Difficulty Tier

Metric	Full System	w/o $\Sigma$	$\Delta$ (abs)	$\Delta$ (%)
Overall Performance
Final Pass Rate	52.78%	41.2%	-11.58	-21.9%
Hard Set FPR	36.8%	18.4%	-18.4	-50.0%
Medium Set FPR	65.0%	52.8%	-12.2	-18.8%
Easy Set FPR	78.3%	71.6%	-6.7	-8.6%
Constraint Adherence

Appendix

Table 26: Performance Impact of Removing Synchronized Global State

Metric	Full System	Flat MARL	$\Delta$ (abs)	$\Delta$ (%)
Pass Rate Metrics
Overall FPR	52.78%	38.5%	-14.28	-27.1%
Hard Set FPR	36.8%	19.5%	-17.3	-47.0%
Medium Set FPR	65.0%	48.3%	-16.7	-25.7%
Easy Set FPR	78.3%	67.8%	-10.5	-13.4%
Budget Management

Appendix

Table 27: Impact of Removing Hierarchical Coordinator on Performance

High-Cost City Selection (NYC, SF, LA) - Should Avoid
Budget Tier	Budget/Day	Full System	Flat MARL	$\Delta$
Tight Budget ( $<$ $600/day)	$400–$ 600	8.3%	41.2%	+32.9
Moderate Budget	$600–$ 1000	22.1%	38.7%	+16.6
Ample Budget ( $>$ $1000/day)	$1000+	67.4%	71.3%	+3.9
Appropriate Cost-Tier Selection Rate
Hard Queries (Tight)	—	78.0%	34.2%	-43.8

Appendix

Table 28: City Selection Quality Analysis by Budget-to-Duration Ratio

Metric	Full System	w/o Bargaining	$\Delta$ (abs)	$\Delta$ (%)
Pass Rate Performance
Overall FPR	52.78%	48.9%	-3.88	-7.4%
Hard Set FPR	36.8%	22.4%	-14.4	-39.1%
Medium Set FPR	65.0%	58.7%	-6.3	-9.7%
Easy Set FPR	78.3%	73.5%	-4.8	-6.1%
Failure Mode Distribution

Appendix

Table 29: Performance Impact of Disabling Cooperative Bargaining

Configuration	Final Pass	Hard Constraint	Budget Viol.	Failure Mode
HiMAP-Travel (Full System)	52.78%	36.8%	4.1%	Balanced
Ablation 1: No Global State ( $\Sigma$ )	41.2%	18.4%	12.5%	High Duplication
Ablation 2: No Coordinator (Flat)	38.5%	19.5%	28.4%	High Overspending
Ablation 3: No Bargaining	48.9%	22.4%	15.2%	Infeasible Alloc.
Ablation 4: No Early Detect	50.1%	31.2%	5.6%	High Latency

Appendix

Table 30: System Component Ablation Analysis (Validation Set). Isolating the impact of (1) Synchronized Global State (

\Sigma

), (2) Hierarchical Coordinator, and (3) Cooperative Bargaining. Note that ”Flat MARL” corresponds to removing the Coordinator but keeping

\Sigma

and decentralized executors.

Iteration	Cumulative Success	Marginal Success	Total Attempts	Success Rate
Iteration 1 (No Feedback)	111 / 180	111	180	61.7%
Iteration 2 (1st Feedback)	162 / 180	51	69	73.9%
Iteration 3 (2nd Feedback)	176 / 180	14	18	77.8%
Iteration 3+ (Failure)	176 / 180	0	4	0.0%
Final Success Rate	97.8%	—	—	—
Mean Iterations	1.42	—	—	—

Appendix

Table 31: Bargaining Protocol Convergence Analysis (N=180 Validation Queries)

Adaptation Type	Frequency	%	Success Rate	Avg. Latency (s)
City Change	47	66.2%	78.7%	26.3
Route Reordering	13	18.3%	46.2%	18.1
Transport Mode Switch	6	8.5%	91.7%	12.4
Fewer Cities Visited	5	7.0%	100.0%	15.7
Total Adaptations	71	100%	74.6%	23.1

Appendix

Table 32: Coordinator Adaptation Strategies and Effectiveness

Failure Category	Count	% of	DeepTravel	HiMAP
		Failures	Rate	Rate
Budget Overflow	68	34.0%	12.5%	4.1%
Early overspend (Days 1-2)	42	21.0%	8.3%	1.8%
Cumulative drift	26	13.0%	4.2%	2.3%
Duplicate Venues	47	23.5%	8.7%	1.5%
Restaurants	31	15.5%	5.8%	0.9%

Appendix

Table 33: Failure Mode Distribution with Comparative Analysis. Manual analysis of 200 randomly sampled failures from the 473 failed test instances, comparing HiMAP-Travel against the sequential DeepTravel baseline.

Total Budget: $1,231 /$ 2,300 (53.5% utilization)
Day	City	Accommodation	Location	Issue
1	Austin(TX)	Spacious Williamsburg 1BR	Austin, TX	Valid
2	Austin(TX)	Spacious Williamsburg 1BR	Austin, TX	Valid
3	Reno(NV)	(Return day)	—	—
Constraint Violation: Accommodation name references NYC borough despite Austin registration

Appendix

Table 34: Failure Instance #44: Geographic Metadata Inconsistency

Total Budget: $610 /$ 1,700 (35.9% utilization vs. 85–95% typical)
Day	Accommodation	Price/Night	Min. Nights	Issue
1	100 Sq. Ft. Penthouse	$0	1 night	Invalid pricing
2	1 BR in Carroll Gardens	$397	2 nights	Min. nights violated
3	(Return day)	—	—	—
Dual Failure: Invalid metadata + temporal constraint violation

Appendix

Table 35: Failure Instance #49: Compounded Metadata and Temporal Violations

Total Budget: $1,642 /$ 1,900 (86.4% utilization - otherwise successful plan)
Day	City	Accommodation	Min. Nights	Actual Nights
1	Asheville(NC)	FANTASTIC 1BR Columbus	2 nights	2 nights (✓)
2	Asheville(NC)	(Same as Day 1)	—	—
3	Charlotte(NC)	Luxury 2BR Williamsburg	1 night	1 night (✓)
4	Charlotte(NC)	Affordable Refurbished Room	2 nights	1 night (×)
5	Oklahoma City	(Return day)	—	—

Appendix

Table 36: Failure Instance #155: Cascading Multi-City Temporal Violation

Primary Failure Mode	Count	% of Failures	Mean Budget Util.	Avg. Iterations
Minimum Nights Violations	87	13.7%	48.3%	1.2
Budget Overruns	201	31.6%	107.4%	2.8
Diversity Constraint Violations	143	22.4%	89.1%	1.9
Sandbox Violations (Data Quality)	41	6.4%	72.6%	1.4
Incomplete Information Extraction	63	9.9%	65.2%	1.1
Transportation Inconsistencies	28	4.4%	81.3%	1.6

Appendix

Table 37: Comprehensive Failure Mode Distribution Across Test Set (N=637)

Travel Planning

See all 21 papers

DeepTravel: An End-to-End Agentic Reinforcement Learning Framework for Autonomous Travel Planning Agents
Sep 26, 2025Yansong Ning, Rui Liu, Jun Wang +6Agentic RL Travel Planning
The Hong Kong University of Science and Technology (Guangzhou) · Didichuxing Co. Ltd
Trip+: Benchmarking Agents in Personalized Interactive Travel Planning
Jun 19, 2026Junle Chen, Wei Chen, Yehong Xu +6LLM Agent Evaluation AI Agent Benchmarks
HKUST · Tencent Hy · HKUST(GZ)
Decoupled Travel Planning with Behavior Forest
Apr 23, 2026Duanyang Yuan, Sihang Zhou, Yanning Hou +7LLM Planning Travel Planning
College of Intelligence Science and Technology, National University of Defense Technology, Changsha 410073, China · College of Computer Science and Technology, National University of Defense Technology, Changsha 410073, China · College of Systems Engineering, National University of Defense Technology, Changsha 410073, China +1

Sep 26, 2025J/K move · Enter open · S save

DeepTravel: An End-to-End Agentic Reinforcement Learning Framework for Autonomous Travel Planning Agents

Yansong Ning, Rui Liu, Jun Wang, Kai Chen+5

The Hong Kong University of Science and Technology (Guangzhou) · Didichuxing Co. Ltd

Agentic RL Travel Planning LLM Agent Training LLM Agent Planning RL for Tool Use

Open paper AskPDF arXiv

Travel planning (TP) agent has recently worked as an emerging building block to interact with external tools/resources for travel itinerary generation, ensuring an enjoyable user experience. Despite its benefits, existing studies rely on hand-craft prompt and fixed agent workflow, hindering more flexible and autonomous TP agents. This paper proposes DeepTravel, an end-to-end agentic reinforcement learning framework for building an autonomous travel planning agent, capable of autonomously planning, executing tools, and reflecting on tool responses to explore, verify, and refine intermediate actions in multi-step reasoning. To achieve this, we first construct a robust travel sandbox by caching transportation, accommodation and POI data, facilitating TP agent training without being constrained by real-world APIs limitations (e.g., inconsistent outputs). Moreover, we develop a hierarchical reward modeling system, where a trajectory-level verifier first checks spatiotemporal feasibility and filters unsatisfied travel itinerary, and then the turn-level verifier further validate itinerary's detail consistency with tool responses, enabling efficient and precise reward service. Finally, we propose the reply-augmented reinforcement learning method that enables TP agent to periodically replay from a failure experience buffer, emerging notable agentic capacity. We deploy the trained TP agent in the DiDi Enterprise Solutions application. A three-month online test shows that it achieves 82% accuracy in travel itinerary generation. Comprehensive offline evaluations further demonstrate that DeepTravel enables small-sized LLMs (e.g., Qwen3-32B) to significantly outperform frontier LLMs (e.g., OpenAI o1/o3 and DeepSeek-R1) and existing TP agent frameworks.

Abstract

Travel Planning

Explore similar work

DeepTravel: An End-to-End Agentic Reinforcement Learning Framework for Autonomous Travel Planning Agents

Trip+: Benchmarking Agents in Personalized Interactive Travel Planning

Decoupled Travel Planning with Behavior Forest