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

• URL: http://arxiv.org/abs/2603.04750v1
• Date: Thu, 05 Mar 2026 02:55:53 GMT
• Title: HiMAP-Travel: Hierarchical Multi-Agent Planning for Long-Horizon Constrained Travel
• Abstract summary: We propose HiMAP-Travel, a hierarchical multi-agent framework that splits planning into strategic coordination and parallel day-level execution.<n>On TravelPlanner, HiMAP-Travel with Qwen3-8B achieves 52.78% validation and 52.65% test Final Pass Rate (FPR)
• Score: 17.262462566213244
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• LePlanner: An Iterative Amortized Controller For World Models [0.0]
  We propose LePlanner, an amortized iterative controller that learns to construct and refine latent action sequences through a frozen world-model predictor.<n>LePlanner is trained with an arrival-and-hold objective that encourages the controller to reach the goal at the earliest feasible horizon and remain there.<n>It achieves success rates of 98% on PushT, 100% on Reacher, 100% on TwoRooms, and 92% on the OGBench Cube task.
  arXiv  Detail & Related papers  (2026-09-12T10:01:21Z)
• Planner-Conditioned Diffusion for Coordinated Multi-Agent Exploration [7.151235176774153]
  Coordinated multi-agent exploration requires efficient individual coverage and non-redundant coverage across agents.<n>We propose a Planner-Conditioned Diffusion Policy (PCDP) for graph-based multi-agent exploration.
  arXiv  Detail & Related papers  (2026-08-17T08:07:20Z)
• Scalable Long-Horizon Planning with Staggered Updates for Lifelong MAPF [5.199189722211842]
  Lifelong Multi-Agent Path Finding (LMAPF) requires generating collision-free paths for large agent fleets under strict real-time constraints.<n>We propose Path Updates over Staggered Horizons (PUSH), a LMAPF planner capable of coordinating thousands of agents in under a second.
  arXiv  Detail & Related papers  (2026-08-07T01:56:19Z)
• AgentSwing: Adaptive Parallel Context Management Routing for Long-Horizon Web Agents [115.18197165538943]
  Large language models (LLMs) evolve into autonomous agents for long-horizon information-seeking.<n>Existing context management methods typically commit to a single fixed strategy throughout the entire trajectory.<n>We introduce a probabilistic framework that characterizes long-horizon success through two complementary dimensions: search efficiency and terminal precision.
  arXiv  Detail & Related papers  (2026-03-29T02:59:27Z)
• Hierarchical LLM-Based Multi-Agent Framework with Prompt Optimization for Multi-Robot Task Planning [0.9453554184019106]
  Multi-robot task planning requires decomposing natural-language instructions into executable actions.<n>PDDL planners provide rigorous guarantees but struggle to handle ambiguous or long-horizon missions.<n>We present a hierarchical multi-agent LLM-based planner with prompt optimization.
  arXiv  Detail & Related papers  (2026-02-25T08:08:26Z)
• MagicAgent: Towards Generalized Agent Planning [73.21129030631421]
  We present textbfMagicAgent, a series of foundation models specifically designed for generalized agent planning.<n>We introduce a lightweight and scalable synthetic data framework that generates high-quality trajectories across diverse planning tasks.<n>We show that MagicAgent-32B and MagicAgent-30B-A3B achieve superior performance across diverse open-source benchmarks.
  arXiv  Detail & Related papers  (2026-02-22T01:39:16Z)
• HiPER: Hierarchical Reinforcement Learning with Explicit Credit Assignment for Large Language Model Agents [36.77027704958893]
  HiPER is a novel Hierarchical Plan-Execute RL framework that separates high-level planning from low-level execution.<n>HiPER achieves state-of-the-art performance on challenging interactive benchmarks, reaching 97.4% success on ALFWorld and 83.3% on WebShop with Qwen2.5-7B-Instruct.
  arXiv  Detail & Related papers  (2026-02-18T03:31:34Z)
• Programming over Thinking: Efficient and Robust Multi-Constraint Planning [54.77940831026738]
  SCOPE is a framework that disentangles query-specific reasoning from generic code execution.<n>SCOPE achieves state-of-the-art performance while lowering cost and latency.
  arXiv  Detail & Related papers  (2026-01-14T02:58:07Z)
• Bridging Planning and Execution: Multi-Agent Path Finding Under Real-World Deadlines [9.228609005424348]
  We propose REMAP, an execution-informed MAPF planning framework for time-sensitive applications.<n>Our framework integrates the proposed ExecTimeNet to accurately estimate execution time based on planned paths.<n>Experiments show that REMAP achieves up to 20% improvement in solution quality over baseline methods.
  arXiv  Detail & Related papers  (2025-11-26T20:08:52Z)
• ParaCook: On Time-Efficient Planning for Multi-Agent Systems [62.471032881396496]
  Large Language Models (LLMs) exhibit strong reasoning abilities for planning long-horizon, real-world tasks.<n>We present ParaCook, a benchmark for time-efficient collaborative planning.
  arXiv  Detail & Related papers  (2025-10-13T16:47:07Z)
• Wide-Horizon Thinking and Simulation-Based Evaluation for Real-World LLM Planning with Multifaceted Constraints [39.01715254437105]
  This paper introduces the Multiple Aspects of Planning (MAoP) to solve planning problems with multifaceted constraints.<n>Instead of direct planning, MAoP leverages the strategist to conduct pre-planning from various aspects and provide the planning blueprint for planners.
  arXiv  Detail & Related papers  (2025-06-14T09:37:59Z)
• Decompose, Plan in Parallel, and Merge: A Novel Paradigm for Large Language Models based Planning with Multiple Constraints [31.631832677979826]
  We propose a novel parallel planning paradigm, which Decomposes, Plans for subtasks in Parallel, and Merges subplans into a final plan (DPPM)<n>Specifically, DPPM decomposes the complex task based on constraints into subtasks, generates the subplan for each subtask in parallel, and merges them into a global plan.<n> Experimental results demonstrate that DPPM significantly outperforms existing methods in travel planning tasks.
  arXiv  Detail & Related papers  (2025-06-03T09:33:13Z)
• Extendable Long-Horizon Planning via Hierarchical Multiscale Diffusion [62.91968752955649]
  This paper tackles a novel problem, extendable long-horizon planning-enabling agents to plan trajectories longer than those in training data without compounding errors.<n>We propose an augmentation method that iteratively generates longer trajectories by stitching shorter ones.<n>HM-Diffuser trains on these extended trajectories using a hierarchical structure, efficiently handling tasks across multiple temporal scales.
  arXiv  Detail & Related papers  (2025-03-25T22:52:46Z)
• Planning with Multi-Constraints via Collaborative Language Agents [13.550774629515843]
  This paper introduces Planning with Multi-Constraints (PMC), a zero-shot methodology for collaborative multi-agent systems.<n>PMC simplifies complex task planning with constraints by decomposing it into a hierarchy of subordinate tasks.<n>PMC achieved an average 42.68% success rate on TravelPlanner, significantly higher than GPT-4 (2.92%), and outperforming GPT-4 with ReAct on API-Bank by 13.64%.
  arXiv  Detail & Related papers  (2024-05-26T10:33:17Z)
• A Feedback Scheme to Reorder a Multi-Agent Execution Schedule by Persistently Optimizing a Switchable Action Dependency Graph [65.70656676650391]
  We consider multiple Automated Guided Vehicles (AGVs) navigating a common workspace to fulfill various intralogistics tasks. One approach is to construct an Action Dependency Graph (ADG) which encodes the ordering of AGVs as they proceed along their routes. If the workspace is shared by dynamic obstacles such as humans or third party robots, AGVs can experience large delays. We present an online method to repeatedly modify acyclic ADG to minimize route completion times of each AGV.
  arXiv  Detail & Related papers  (2020-10-11T14:39:50Z)
• Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints [52.58352707495122]
  We present a multi-robot allocation algorithm that decouples the key computational challenges of sequential decision-making under uncertainty and multi-agent coordination. We validate our results over a wide range of simulations on two distinct domains: multi-arm conveyor belt pick-and-place and multi-drone delivery dispatch in a city.
  arXiv  Detail & Related papers  (2020-05-27T01:10:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.