HiMAP-Travel: 面向长期受限旅行规划的分层多智能体框架 HiMAP-Travel: Hierarchical Multi-Agent Planning for Long-Horizon Constrained Travel
通过分层并行架构和博弈协议解决LLM在长期规划中的约束漂移问题，FPR达52.65%
前置知识
约束漂移 (Constraint Drift)
当LLM智能体进行长期规划时，随着工具调用输出和推理痕迹不断积累，上下文长度增长导致对初始全局约束（如总预算）的注意力逐渐稀释。这种现象使得模型优先保持局部连贯性而非全局可行性，导致约束违反率随规划时间线单调递增。本文首次系统性地将此现象命名为'约束漂移'，并量化了其在旅行规划任务中的影响——从第1天98%的预算满足率下降到第5天的42%。
理解约束漂移是理解本文核心动机的关键。只有认识到序列规划架构的根本缺陷，才能理解为什么需要引入分层并行架构来解决这个问题。
GRPO (Group Relative Policy Optimization)
GRPO是一种无需单独Critic网络的策略优化算法。对于每个查询，采样一组G条轨迹，计算组内相对优势 A_i = (R(tau_i) - mu_G)/(sigma_G + epsilon)，其中 mu_G 和 sigma_G 分别是组内奖励的均值和标准差。通过KL散度惩罚系数 beta 防止策略偏离基础模型。相比PPO，GRPO减少了约50%的内存占用，适合多智能体训练场景。
GRPO是本文训练统一策略的核心算法。理解其工作原理有助于评估方法的可复现性和计算需求，也是理解HiMAP如何在内存受限条件下训练多智能体系统的关键。
GC-POMDP (Goal-Conditioned Partially Observable Markov Decision Process)
GC-POMDP是本文对长期旅行规划问题的形式化框架。智能体接收自然语言查询 q，该查询参数化任务 T_q = (q, K, C_hard, C_soft)，其中 K 是API接口集合，C_hard 过滤不可违反的硬约束（如预算上限），C_soft 捕获用户偏好。目标是找到最大化期望效用且满足近似确定有效性的策略。
这个形式化框架将旅行规划从直觉层面提升到理论层面，明确了硬约束与软约束的区分，为后续分层分解和奖励设计提供了数学基础。
事务性监控器 (Transactional Monitor)
事务性监控器 Sigma = (B_used, V_committed, M_trans) 是HiMAP-Travel的核心同步机制。它维护三个全局变量：累计预算支出、已提交景点/餐厅集合、城际交通模式锁。通过原子操作 check(action) 和 commit(action) 实现确定性约束执行，所有并发请求通过全局可重入互斥锁序列化。支持 checkpoint() 和 rollback() 操作用于迭代重新规划。
这是解决并行执行中资源冲突的核心机制。理解其设计对于评估系统的安全性保证和可扩展性至关重要，也是与其他多智能体系统（如ATLAS的Constraint Manager）的本质区别。
角色条件化策略 (Role-Conditioned Policy)
HiMAP-Travel使用单一策略网络通过系统提示条件化来模拟不同角色。策略输入为 x = [p_role, s_t]，其中 p_role 描述角色范围（Coordinator vs Day Planner），s_t 是当前观察状态。这种设计使得战术执行中学到的推理（如识别昂贵航班）能够迁移到协调者的战略分配角色中。训练时采用FIFO机制的角色特定分组更新。
角色条件化是本文的关键创新之一，它在保持参数共享的同时实现了行为专门化。理解这一机制有助于评估方法的内存效率和训练可行性。
研究动机
现有的序列式LLM规划架构（如ReAct、Chain-of-Thought）在长期规划任务中存在根本性缺陷。当规划时间线延长时，中间工具输出和推理痕迹不断积累，导致有效上下文长度增加，从而稀释了对初始全局约束（如总预算）的注意力。这种被作者称为'约束漂移'的现象在旅行规划任务中表现为：5天行程中，序列基线在第1天的预算满足率为98%，但到第5天急剧下降到42%。更严重的是，这种退化具有级联效应——第一天的过度支出会迫使后续天数的计划不完整，最终导致整体计划无效。现有的'验证-精化'架构（如ATLAS的Constraint Manager）虽然试图通过后验校正来缓解这一问题，但面临超线性延迟开销：一个7天行程必须被完全'幻觉'出来，才能检测到第1天的预算错误，这导致计算浪费和延迟随计划长度二次增长。
本文的目标是本文的目标是提出一种能够主动执行约束而非事后验证的可训练分层多智能体框架，将'生成-然后修复'的范式转变为'构造即正确'。具体目标包括：在TravelPlanner基准上实现超过50%的测试最终通过率(FPR)；通过并行化将延迟降低至少2倍；在相同模型、训练算法和工具条件下超越序列基线；以及证明分层分解能够稳定约束处理并减少跨种子方差。
与已有工作不同的是，本文的独特切入角度在于三个方面。首先，它首次系统性地识别并命名了'约束漂移'这一长期规划中的根本失败模式，将其与上下文长度增长建立了因果关系。其次，它提出了'正确构造'范式，通过确定性事务性监控在执行期间（而非执行后）强制执行耦合约束，这与ATLAS等依赖约束管理器的方法形成本质区别。第三，它引入了协作博弈协议，允许执行器以轻量级结构化信号（而非冗长自然语言对话）拒绝不可行的子目标并触发重新规划，实现了双向可行性反馈。这些创新的结合使得HiMAP-Travel能够在保持全局一致性的同时实现并行执行。
核心方法
HiMAP-Travel的核心直觉可以类比为'公司管理架构'：一个高层协调者（Coordinator）负责资源分配和战略决策，而多个并行的执行者（Day Executors）各自负责具体的战术执行。关键技术路线分为三层：首先，将高维用户查询投影为有效的日级边界条件集合，将全局约束（如总预算和时间跨度）分配给专门的智能体团队；其次，通过同步全局状态 Sigma 实现确定性事务性约束执行，防止并行执行中的资源冲突；最后，通过协作博弈协议实现动态重新规划，当执行器遇到不可行子目标时可以拒绝并触发重新分配。这种架构将有效上下文长度从 O(T) 降低到 O(T/D)，其中 T 是总时间线，D 是旅行天数。
本文与已有方法最本质的区别在于三个紧密集成的机制。第一，同步全局状态 Sigma 提供确定性事务性约束执行——不同于ATLAS的Constraint Manager在生成完整计划后进行验证，Sigma 在每个原子操作提交时立即验证预算守恒和非重复约束，通过全局可重入互斥锁防止资源冲突。第二，协作博弈协议实现了结构化重新分配——不同于MTP等系统依赖自然语言消息传递的慢速且易出错的协调，HiMAP-Travel使用严格JSON schema的轻量级反馈（status、deficit、violation_type字段），最小化token开销的同时保留并行执行效率。第三，统一角色条件化策略——通过GRPO训练的单一策略网络通过系统提示条件化来模拟协调者和执行者两种角色，使得战术推理能够迁移到战略分配中，实现'管理同理心'。这种集成使得HiMAP-Travel在相同模型和工具条件下，比序列基线DeepTravel高出8.67个百分点。
方法步骤详情
HiMAP-Travel的执行流程如下。步骤1：协调者接收自然语言查询 q，调用information_extractor解析为结构化任务元组 T_q = (q, C_hard, C_soft)，包括出发地、目的地、天数、预算、人数、约束条件。步骤2：协调者进行城市消歧和选择——如果visit_city_number=1，先直接搜索目的地名称，若无结果则推断为州名并搜索该州城市列表；如果visit_city_number>1，直接搜索州名并选择合适数量的城市。步骤3：协调者调用distribute_task生成元计划 Z = {z_1, ..., z_D}，每个 z_d 指定目标城市、日类型（出发/停留/中转/返回）和预算提示 b_d，满足守恒律 sum(b_d) <= B_total。步骤4：并行执行器启动——系统实例化 D+1 个逻辑线程（1个协调者 + D 个执行器），并发度上限 P=3，以 ceil(D/P) 批次调度。每个执行器在严格隔离的MDP中工作，上下文独立于其他天数的推理痕迹。步骤5：原子约束执行——当执行器采样动作 a_t 时，环境拦截并获取全局锁，验证 a_t 对 Sigma 的约束（预算不溢出、景点未重复），违反时返回结构化错误观察。步骤6：完成验证——执行器调用cost_enquiry计算当日总成本，然后调用finish触发原子check/commit操作。步骤7：协作博弈——如果任何执行器返回INFEASIBLE状态，协调者接收包含status、deficit、violation_type的结构化反馈，在下一次迭代中选择不同城市或调整行程结构，最多迭代 K_max=3 次。
技术新颖性
HiMAP-Travel的技术新颖性体现在五个方面。第一，它是首个在多智能体框架中引入确定性事务性约束执行的系统——Sigma 通过原子锁和不变量检查 I(Sigma) 提供互斥性和不变量保持的安全保证，这与ATLAS依赖神经网络约束管理器的软验证形成本质区别。第二，协作博弈协议实现了轻量级结构化重新分配——61.7%的查询在第一次迭代就成功，97.8%在三次迭代内解决，平均1.42次迭代，仅2.2%在 K_max=3 后仍不可行。第三，统一角色条件化策略通过GRPO的FIFO多角色更新机制训练——每个角色分区累积 G 条轨迹后立即计算GRPO组统计量并更新参数，将峰值内存限制为 max(G*T)*d_model 而非完整的 (D+1)*G*T*d_model。第四，分层奖励分解解决了信用分配问题——协调者优化 J_coord = lambda_global*R_global + lambda_extract*R_extract - lambda_iter*N_iter，执行器优化 J_exec = gamma_global*R_global + gamma_local*R_local + gamma_early*1_early，其中早期检测奖金激励快速失败报告。第五，上下文隔离将有效序列长度从 O(T) 降低到 O(T/D)，这是缓解约束漂移的根本方案。
实验结果
HiMAP-Travel在两个互补基准上取得了最先进的性能。在TravelPlanner单轮规划基准上，使用Qwen3-8B骨干网络，HiMAP-Travel实现了52.78%验证集和52.65%测试集的最终通过率(FPR)，交付率达到完美的100%。在受控比较中（相同模型、训练算法、工具和解码参数），HiMAP-Travel比序列基线DeepTravel高出+8.67个百分点（52.65% vs 43.98%），并将跨种子方差从7.18%降低到0.48%，实现了93%的方差缩减。具体约束层面，多样性景点约束达到100%通过率，路线可行性98.9%，沙盒合规87.7%。预算溢出失败率从12.5%降至4.1%（降低67%），重复景点从8.7%降至1.5%（降低83%）。在FlexTravelBench多轮约束适应基准上，HiMAP-Travel实现了44.34%（2轮）和37.42%（3轮）的FPR，比ATLAS分别高出+5.14和+4.72个百分点。效率方面，7天行程的端到端延迟从189.5秒降低到72秒，实现2.63倍加速，其中日规划阶段实现2.79倍加速（接近3倍理论上限）。4B模型达到8B模型94%的性能，但延迟仅为67%（48秒 vs 72秒），计算需求仅57%。
查看结构化数据
| 任务 | 指标 | 本文 | 基线 | 提升 |
|---|---|---|---|---|
| TravelPlanner 测试集 (1000 queries) | Final Pass Rate | 52.65% | ATLAS: 35.00%, MTP: 42.68%, DeepTravel: 43.98% | +17.65pp vs ATLAS, +10.0pp vs MTP, +8.67pp vs DeepTravel |
| TravelPlanner 验证集 (180 queries) | Final Pass Rate | 52.78% | DeepTravel: 45.56% | +7.22pp |
| FlexTravelBench 2-Turn | Final Pass Rate | 44.34% | ATLAS: 39.22% | +5.12pp |
| FlexTravelBench 3-Turn | Final Pass Rate | 37.42% | ATLAS: 32.68% | +4.74pp |
| 7天行程延迟 | Wall-clock (秒) | 72s | DeepTravel: 190s | 2.63倍加速 |
| 5天行程预算满足率 | Day 5 Budget Satisfaction | 91% | Sequential: 42% | +49个百分点 |
局限与改进
作者承认的局限性包括：首先，Room Rule（32.73%）和Room Type（39.36%）约束的通过率仍然较低，是系统的主要瓶颈，8B模型在这两项上甚至出现了-5.19和-5.60个百分点的退化，暗示可能存在过拟合。其次，预算溢出仍然是最常见的失败模式（34.0%），其中62%发生在前两天的早期过度支出，38%是累积漂移。第三，最小住宿夜数违反占失败的13.7%，特别是在多城市行程中呈超线性增长（2城市8.7% vs 3城市22.3%），日级执行器缺乏前瞻性的时序推理能力。第四，地理不一致性（6.4%）主要源于数据库中景点名称的误导性命名（如注册在Austin的'Williamsburg'），这是数据质量问题而非算法缺陷。第五，当预算约束与房间容量要求冲突时（6.0%的约束冲突），可能存在根本性的不可行性。从独立分析来看，虽然并行执行带来了延迟优势，但token消耗增加了约15%；此外，系统对数据库中无效元数据（如$0/night住宿）的鲁棒性不足，这些记录会导致预算利用率坍缩到43.7%。
独立分析的弱点
基于独立分析，HiMAP-Travel存在以下几个具体弱点。第一，时序推理能力不足——当前系统缺乏显式的'剩余住宿夜数'状态跟踪，导致最小住宿夜数违反成为第三大失败原因。改进方向是在 Sigma 中扩展 get_remaining_nights(city) 和 is_final_accommodation_day(day) 操作，在提交前强制执行 selected.minimum_nights <= remaining_nights()。第二，约束耦合建模缺失——预算约束和多样性约束之间存在强耦合：受限预算导致偏好低价场所，这些场所地理聚集，降低了多样性。改进方向是引入联合预算-多样性建模，或在协调者分配中加入多样性惩罚项。第三，早期可行性检测缺失——对于预算明显不足的查询（如$900预算7天行程），系统仍会尝试完整规划后才失败，浪费计算资源。改进方向是在协调者阶段加入可行性预检测，对可证明不可行的查询提前中止。第四，数据质量问题未处理——数据库中1.58%的记录价格低于$10（包括142条$0记录），这些异常值会扭曲智能体的决策。改进方向是离线k-NN插补和运行时低置信度价格降权。第五，博弈协议的适应策略有限——城市替换占66.2%的适应尝试，路线重排成功率仅46.2%。改进方向是引入更丰富的适应原语，如活动类型替换或预算内部重新分配。
未来方向
作者提出和可延伸的未来方向包括。第一，将HiMAP-Travel的核心方法论——将耦合全局约束分解为可并行求解的局部子问题——扩展到其他需要资源协调的领域，如软件模块开发（协调者定义接口，并行执行器实现功能，共享构建状态防止循环依赖）、供应链优化（枢纽协调者分配资源，路线执行器在共享容量约束下优化局部配送）和科学实验规划（资源分配与并行协议设计）。第二，引入显式的可行性检测机制，在协调者阶段识别可证明不可行的查询并提前中止，目标是将性能从当前的52.7%提升到70-80%。第三，探索更细粒度的约束执行——当前 Sigma 只跟踪预算、景点集合和交通模式，未来可以扩展到时序一致性、美食覆盖等更多约束类型。第四，研究自适应并发度——当前固定 P=3 的执行器并发可能不是最优的，可以根据查询复杂度和可用计算资源动态调整。第五，探索更高效的训练策略——当前仅使用45个训练查询，虽然通过轨迹增强缓解了过拟合，但更大的训练集可能进一步提升性能。
复现评估
复现评估显示该方法具有较高的可复现性。代码和数据方面，TravelPlanner和FlexTravelBench均为公开基准，工具API和评估脚本标准化；论文提供了完整的系统提示（附录E）和执行轨迹示例。算力需求方面，使用Qwen3-8B进行全参数微调，需要8GPU节点，100个epoch，batch size 32，gradient accumulation 4，上下文窗口8192 tokens；Qwen3-4B版本计算需求降低约57%，适合资源有限的实验室。训练数据方面，仅需TravelPlanner的45个训练查询，通过GRPO的 (D+1)*G 轨迹展开实现有效数据增强。关键复现细节包括：温度0.7、top-p 0.9的解码参数；每执行器最多15次工具调用；博弈迭代上限 K_max=3；模糊匹配阈值 tau=0.95 的景点去重。潜在困难包括：GRPO训练的超参数敏感性（学习率 5e-6、KL系数 beta=0.01、组大小 G=4）；需要实现完整的同步全局状态 Sigma 和原子锁机制；以及数据库模式与TravelPlanner v1.0的兼容性。总体而言，一个有经验的RL研究者团队预计可在2-4周内复现核心结果。
论文图表
