arXiv:2607.00156cs.RO2026-07

提出DIVE策略,让多智能体路径规划更高效省内存。

Dual-Informed Vertical Expansion for Multi-Objective Node Selection in Anytime Conflict-Based Search

  • 基于双信息引导的垂直扩展策略,动态优化搜索路径
  • 减少搜索中断次数,早期给出可行解并带证明间隙
  • 适合高密度或内存受限场景,支持快速响应和预热

冲突基搜索(CBS)是多智能体路径规划(MAPF)的主流精确算法,但其高层节点选择通常被视为固定实现细节。标准的最佳优先策略虽能减少展开节点、快速闭合最优性证明,却可能维持大规模前段队列,打断父子扩展序列,且直到结束才提供可行解。本文将节点选择提升为首要设计决策,提出双信息引导的垂直扩展(DIVE)策略:在每次探索中从当前最优边界前沿出发,沿有希望的子节点推进以利用父子局部性,并通过当前解剪枝限制无效探索。通过分支定界视角形式化节点选择,证明改变遍历策略不影响正确性,并分析展开节点数、探索中断、队列大小与原对偶边界进展间的权衡。理论预测三种互补极端:最佳优先注重节点效率,迭代加深注重内存效率,而DIVE在保持常规最优边界锚定的同时,实现探索效率。标准MAPF基准测试验证了这一权衡图谱:DIVE持续减少探索中断,提前提供带证明间隙的可行解,队列内存使用显著低于最佳优先策略,并在密集或内存受限场景中受益于预热和简单响应变体。

原文摘要 · Abstract (English)

Conflict-Based Search (CBS) is a leading exact algorithm for Multi-Agent Path Finding (MAPF), but its high-level node-selection rule is usually treated as a fixed implementation detail. Standard best-first selection is strong for minimizing expanded nodes and closing the optimality certificate, yet it can maintain a large frontier, interrupt parent-child expansion sequences, and provide no feasible incumbent until termination. This paper studies node selection as a first-class design choice for exact CBS. We introduce Dual-Informed Vertical Expansion (DIVE), a policy that is best-bound between dives and depth-oriented within a dive. DIVE starts each dive from the current best-bound frontier, follows promising children to exploit parent-child locality, and uses incumbent pruning to limit unproductive excursions. We formalize CBS node selection through a branch-and-bound view, prove that the traversal policy can be changed without affecting exactness, and analyze the resulting trade-offs among expanded nodes, dive breaks, queue size, and primal-dual bound progress. The analysis predicts three complementary extremes. Best-first search is node efficient, iterative deepening is memory efficient, and DIVE is dive efficient while retaining regular best-bound reanchoring. Experiments on standard MAPF benchmarks support this trade-off map. DIVE consistently reduces dive breaks, provides early incumbents with certified gaps, uses substantially less queue memory than best-first search, and benefits from warm starts and simple responsive variants in dense or memory-limited regimes.

多智能体路径规划搜索优化算法设计

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。