arXiv:2510.07276cs.AIcs.MA2025-10

提出按优先级排序的目标路径规划方法,解决多目标协作效率问题。

Multi-Objective Multi-Agent Path Finding with Lexicographic Cost Preferences

  • 用优先级顺序替代传统帕累托前沿,直接生成符合用户偏好的解
  • 可在最多10个目标下高效求解,成功率显著高于现有方法
  • 适合需明确优先级的多智能体协同场景,如物流调度、救援行动

现实世界中多个智能体需在共享环境中协调行动,同时权衡多个可能冲突的目标。现有多目标多智能体路径规划(MO-MAPF)算法通常通过计算帕累托前沿生成无冲突路径,但未显式优化用户定义的偏好,即使偏好已知;且随目标数增加,性能急剧下降。本文提出一种基于字典序偏好的MO-MAPF建模框架,并设计算法Lexicographic Conflict-Based Search(LCBS),直接计算与目标优先级一致的单一解。LCBS将优先级感知的低层A*搜索与基于冲突的搜索结合,避免构建帕累托前沿,实现由目标偏好驱动的高效规划。我们分析了算法的最优性与可扩展性,实验证明其在最多10个目标的实例上仍能计算最优解,远超现有方法极限。在标准和随机化MAPF基准测试中,相比最先进基线,成功率达更高,尤其在目标数量增加时优势更明显。

原文摘要 · Abstract (English)

Many real-world scenarios require multiple agents to coordinate in shared environments, while balancing trade-offs between multiple, potentially competing objectives. Current multi-objective multi-agent path finding (MO-MAPF) algorithms typically produce conflict-free plans by computing Pareto frontiers. They do not explicitly optimize for user-defined preferences, even when the preferences are available, and scale poorly with the number of objectives. We propose a lexicographic framework for modeling MO-MAPF, along with an algorithm \textit{Lexicographic Conflict-Based Search} (LCBS) that directly computes a single solution aligned with a lexicographic preference over objectives. LCBS integrates a priority-aware low-level $A^*$ search with conflict-based search, avoiding Pareto frontier construction and enabling efficient planning guided by preference over objectives. We provide insights into optimality and scalability, and empirically demonstrate that LCBS computes optimal solutions while scaling to instances with up to ten objectives -- far beyond the limits of existing MO-MAPF methods. Evaluations on standard and randomized MAPF benchmarks show consistently higher success rates against state-of-the-art baselines, especially with increasing number of objectives.

多智能体路径规划多目标优化字典序

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