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

arXiv: https://arxiv.org/abs/2603.04750 · HTML: https://mlsanity.com/paper/2603.04750/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Placed in General LLM agent frameworks and benchmarks, one of 16 directions in LLM agents and tool use.
- Builds on 12 of its 18 references that are in the map.
- First posted on arXiv 5 Mar 2026.

## Placed in

- LLM agents and tool use / [General LLM agent frameworks and benchmarks](https://mlsanity.com/agents/general-llm-agent-frameworks-and-benchmarks/)

## Builds on (most cited first, 12 of 12)

- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Reflexion: Language Agents with Verbal Reinforcement Learning](https://mlsanity.com/paper/2303.11366/) (2023)
- [Toolformer: Language Models Can Teach Themselves to Use Tools](https://mlsanity.com/paper/2302.04761/) (2023)
- [TravelPlanner: A Benchmark for Real-World Planning with Language Agents](https://mlsanity.com/paper/2402.01622/) (2024)
- [EvoAgent: Towards Automatic Multi-Agent Generation via Evolutionary Algorithms](https://mlsanity.com/paper/2406.14228/) (2024)
- [Multi-Agent Collaboration via Evolving Orchestration](https://mlsanity.com/paper/2505.19591/) (2025)
- [DeepTravel: An End-to-End Agentic Reinforcement Learning Framework for Autonomous Travel Planning Agents](https://mlsanity.com/paper/2509.21842/) (2025)
- [ATLAS: Constraints-Aware Multi-Agent Collaboration for Real-World Travel Planning](https://mlsanity.com/paper/2509.25586/) (2025)
- [Flex-TravelPlanner: A Benchmark for Flexible Planning with Language Agents](https://mlsanity.com/paper/2506.04649/) (2025)
- [HiPlan: Hierarchical Planning for LLM-Based Agents with Adaptive Global-Local Guidance](https://mlsanity.com/paper/2508.19076/) (2025)

## Built on by (most cited first, 2 of 2)

- [Demystifying Reinforcement Learning for Long-Horizon Tool-Using Agents: A Comprehensive Recipe](https://mlsanity.com/paper/2603.21972/) (2026)
- [AdaPlanBench: Evaluating Adaptive Planning in Large Language Model Agents under World and User Constraints](https://mlsanity.com/paper/2606.05622/) (2026)

## Abstract (arXiv)

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.