Research map / Multi-agent systems and games / LLM agents

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

ICML 2026 · Multi-agent systems and games › LLM agents · approach: Agentic benchmarks and orchestration · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes HiMAP-Travel, a hierarchical multi-agent planner with a Coordinator, parallel day executors, a transactional constraint monitor, cooperative bargaining, and a single GRPO-trained role-conditioned Qwen3 policy for constrained travel planning.

Problem

LLM agents drift from global hard constraints (budget, diversity, non-duplication) over long-horizon multi-day travel itineraries, and verify-and-refine methods are slow.

Approach

Decompose planning into a strategic Coordinator that allocates per-day budget hints and parallel Day Executors, with deterministic enforcement of shared constraints via an external transactional monitor (check/commit/checkpoint/rollback) and a structured bargaining feedback loop, all powered by one GRPO-trained policy using role prompts.

Key results

• HiMAP-Travel (Qwen3-8B) reaches 52.65% test FPR vs 43.98% for the controlled DeepTravel baseline (+8.67 pp), averaged over 4 seeds.
• On FlexTravelBench, HiMAP-Travel (8B) reaches 44.34% (2-turn) and 37.42% (3-turn) FPR.
• Parallel execution reports 2.63x wall-clock speedup on 7-day trips (72s vs 189.5s).

Surprising findings

• Removing the global state monitor still leaves 43.2% FPR, suggesting the policy handles most planning autonomously.
• Naive batch updates reduce FPR only by 1.58 pp, while the 4B model reaches 49.80% test FPR, close to the 8B model.

Limitations

• Training uses only 45 queries, raising overfitting concerns the authors acknowledge.
• Rollback assumes tentative bookings can be released cost-free, a simulation assumption.
• Latency and efficiency results rely on simulated database query latency.

Experimental setup

Datasets: TravelPlanner training split (45 queries)

Benchmarks: TravelPlanner FlexTravelBench

Metrics: Final Pass Rate Delivery Rate Commonsense micro/macro Hard constraint micro/macro latency

Baselines: DeepTravel ATLAS MTP ReAct Reflexion

Builds on: GRPO ReAct TravelPlanner

Closest papers by meaning

• ATLAS: Constraints-Aware Multi-Agent Collaboration for Real-World Travel Planning (ICLR 2026 · similarity 0.89)
• Wide-Horizon Thinking and Simulation-Based Evaluation for Real-World LLM Planning with Multifaceted Constraints (NeurIPS 2025 · similarity 0.88)
• WorldTravel: A Realistic Multimodal Travel-Planning Benchmark with Tightly Coupled Constraints (ICML 2026 · similarity 0.87)
• TravelPlanner: A Benchmark for Real-World Planning with Language Agents (ICML 2024 · similarity 0.86)
• TRIP-Bench: A Benchmark for Long-Horizon Interactive Agents in Real-World Scenarios (ICML 2026 · similarity 0.86)
• Mosaic: Runtime-Efficient Multi-Agent Embodied Planning (ICML 2026 · similarity 0.85)