HiMAP-Travel: Hierarchical Multi-Agent Planning for Long-Horizon Constrained Travel
HiMAP-Travel solves long-horizon travel planning with budget and diversity constraints, achieving 52.65% FPR on the test set.
Key Findings
Methodology
HiMAP-Travel employs a hierarchical multi-agent framework splitting planning into strategic coordination and parallel execution. A Coordinator allocates resources, while Executors independently plan. Key mechanisms include a synchronized global state, cooperative bargaining protocol, and GRPO-trained unified policy.
Key Results
- On TravelPlanner, HiMAP-Travel achieves 52.65% test FPR, outperforming DeepTravel by +8.67 pp.
- On FlexTravelBench, it achieves 44.34% (2-turn) and 37.42% (3-turn) FPR, reducing latency by 2.5x.
- Compared to ATLAS and MTP, HiMAP-Travel improves FPR by +17.65 pp and +10.0 pp, respectively.
Significance
This study addresses 'Constraint Drift,' a key challenge in long-horizon planning, significantly improving global constraint satisfaction rates. By leveraging hierarchical architecture and parallel execution, HiMAP-Travel reduces computational delays while maintaining high accuracy, offering a novel approach to complex constraint optimization.
Technical Contribution
Contributions include: 1) a synchronized global state mechanism ensuring constraint consistency in parallel execution; 2) a lightweight cooperative bargaining protocol for dynamic sub-goal adjustment; 3) a GRPO-trained unified policy enabling parameter sharing and role specialization.
Novelty
HiMAP-Travel is the first to integrate hierarchical multi-agent architecture with synchronized global state mechanisms in travel planning, avoiding the high latency of 'generate-then-fix' methods.
Limitations
- Strict budget/time constraints may require more negotiation iterations, increasing computational cost.
- Relies on predefined tool APIs, limiting adaptability to dynamic environments.
- Performance in highly complex multi-turn scenarios still has room for improvement.
Future Work
Future work could explore adaptability to dynamic environments, optimize bargaining efficiency, and extend to other domains like supply chain optimization.
AI Executive Summary
HiMAP-Travel is a hierarchical multi-agent framework designed to tackle long-horizon travel planning under hard constraints like budgets and diversity. Traditional monolithic models often suffer from 'Constraint Drift,' where global constraints are violated as planning progresses. HiMAP-Travel addresses this by separating strategic coordination and parallel execution.
The framework introduces key innovations such as a synchronized global state, cooperative bargaining protocol, and a unified GRPO-trained policy. The Coordinator divides global constraints into day-level sub-goals, while Executors independently generate daily plans within isolated contexts. This approach minimizes context contamination and proactively resolves constraint violations during execution.
Experimental results demonstrate HiMAP-Travel's superiority on TravelPlanner and FlexTravelBench benchmarks, achieving 52.65% test FPR and reducing latency by 2.5x. This research provides a scalable solution to complex constraint optimization problems and lays the groundwork for future multi-agent systems in dynamic environments.
Deep Analysis
Background
Recent advancements in LLMs have enabled significant progress in automated planning. However, long-horizon tasks remain challenging due to 'Constraint Drift,' where global constraints like budgets degrade over time. This issue is particularly pronounced in travel planning, where early errors cascade into downstream failures.
Core Problem
Long-horizon travel planning requires satisfying multiple hard constraints, such as budgets and route feasibility. Traditional methods rely on sequential generation and post-hoc correction, which become computationally expensive and error-prone as planning length increases.
Innovation
Key innovations include: 1) Hierarchical architecture: separates strategic coordination from tactical execution; 2) Synchronized global state: ensures constraint consistency during parallel execution; 3) Cooperative bargaining protocol: allows Executors to reject infeasible sub-goals and trigger re-planning; 4) Unified policy: GRPO-trained shared parameters enable role specialization.
Methodology
- �� Strategic Coordinator: decomposes global constraints into day-level sub-goals.
- �� Parallel Executors: generate daily plans independently, avoiding context contamination.
- �� Synchronized Global State: enforces constraints using atomic locks.
- �� Cooperative Bargaining Protocol: dynamically adjusts infeasible sub-goals via lightweight feedback.
- �� GRPO Training: optimizes a unified policy for multi-role specialization.
Experiments
Experiments were conducted on TravelPlanner and FlexTravelBench benchmarks, featuring single-turn and multi-turn scenarios. Using Qwen3-8B, models were trained for 100 epochs. Metrics include Final Pass Rate (FPR), budget adherence, and latency.
Results
HiMAP-Travel achieves 52.65% test FPR on TravelPlanner, outperforming DeepTravel by +8.67 pp. On FlexTravelBench, it achieves 44.34% (2-turn) and 37.42% (3-turn) FPR, reducing latency by 2.5x.
Applications
The method can be applied to travel planning, logistics optimization, and complex resource allocation tasks, especially where multiple hard constraints must be satisfied.
Limitations & Outlook
The framework's adaptability to dynamic environments is limited, and strict constraints may increase computational costs. Future work could optimize bargaining efficiency and explore broader applications.
Plain Language Accessible to non-experts
Imagine a travel agency planning a complex multi-day trip. The manager (Coordinator) assigns budgets and goals for each day, like visiting a museum on Day 1 and a beach on Day 2. Each team member (Executor) independently plans their assigned day, choosing restaurants and hotels. To avoid conflicts, they use a shared whiteboard (synchronized global state) to track budgets and locations. If a plan is infeasible, like exceeding the budget, they notify the manager, who adjusts the plan. This ensures the trip is efficient and meets all requirements.
ELI14 Explained like you're 14
Imagine you and your friends planning a super cool five-day trip! You take charge of Day 1, your friend handles Day 2, and so on. To stay on budget and avoid visiting the same place twice, you all use a shared online spreadsheet to track plans. If someone notices a problem, like running out of money, they tell the group leader to fix it. This way, your trip is awesome and stress-free!
Glossary
Hierarchical Multi-Agent
A system where tasks are divided into layers and handled by different agents collaboratively.
Used to split travel planning into strategic and tactical levels.
Constraint Drift
A phenomenon where attention to global constraints decreases as planning progresses.
Leads to budget overruns or duplicate selections in long-horizon tasks.
Synchronized Global State
A shared global storage ensuring real-time constraint checks and corrections.
Maintains consistency across parallel Executors.
Cooperative Bargaining Protocol
A lightweight feedback mechanism allowing Executors to reject infeasible goals and trigger re-planning.
Used to dynamically adjust sub-goals.
GRPO (Group Relative Policy Optimization)
A reinforcement learning algorithm optimizing policies based on group-relative advantages.
Trains the unified policy for multi-role specialization.
Open Questions Unanswered questions from this research
- 1 How can the system adapt to dynamic environments with changing constraints?
- 2 Can the bargaining protocol be made more computationally efficient?
- 3 How can this framework generalize to other domains like supply chain optimization?
Applications
Immediate Applications
Travel Planning
Generates multi-day travel plans meeting budget and preferences, reducing manual effort.
Logistics Optimization
Optimizes routes and costs under multi-constraint conditions for goods transportation.
Long-term Vision
Smart City Resource Allocation
Optimizes dynamic allocation of resources like transportation and energy in cities.
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.