让完成任务的智能体留在目标点时，最小化总代价问题变难了。
Goal Staying Makes Sum-of-Costs Anonymous Multi-Agent Path Finding NP-Hard
- 在时间展开流模型中加入目标停留约束，使线性规划解非整数
- 通过3-SAT归约证明目标停留下的总代价最小化是NP难问题
- 揭示了智能体是否留驻目标点导致复杂度从多项式到NP难的突变
匿名多智能体路径寻找（AMAPF）在某些目标下存在多项式时间网络流算法，包括使工期、总距离和总代价（SoC）最小化，当智能体到达目标后消失时。本文表明标准的目标停留型AMAPF本质不同。首先，通过在标准时间展开流模型中引入目标停留约束，构建了总代价最小化的线性规划模型，并证明其松弛解非整数。随后，通过从3-SAT问题的归约，证明目标停留情形下的总代价最小化是NP难的。结合消失型可在多项式时间内求解的结果，该研究确立了由完成后的智能体是否停留所决定的精确复杂度边界。
原文摘要 · Abstract (English)
Anonymous Multi-Agent Path Finding (AMAPF) admits polynomial-time network-flow algorithms for several objectives, including makespan, total distance, and sum-of-costs (SoC) when agents disappear upon reaching goals. We show that standard goal-staying AMAPF is fundamentally different. We first formulate SoC minimization by augmenting the standard time-expanded flow model with goal-settlement constraints and show that the resulting linear programming relaxation is non-integral. We then prove that minimizing SoC in goal-staying AMAPF is NP-hard via a reduction from 3-SAT. Together with the polynomial-time result for the disappearing variant, this establishes a sharp complexity boundary determined by whether completed agents remain at their goals.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。