在最短路径总长之下路由多智能体：Transient Multiagent Pathfinding 的参数化复杂度刻画
核心概要
该工作研究 Transient Multiagent Pathfinding（智能体到达终点后立即消失的无碰撞多智能体路径规划），以顺序路由给出的上界 L=1+Σdist(si,ti) 与目标完工时间 λ 之间的差距 ζ=L−λ 及智能体数 k 为参数，证明该问题在 k+ζ 下固定参数可解（2^{O(k²ζ)}·n^{O(1)}），并给出 k 单独参数化 W[1]-难、ζ 单独参数化在终点可重复时 W[1]-难、k+ζ 下不存在多项式核的下界，同时证明当所有终点互不相同时问题仅以 ζ 为参数也是固定参数可解（2^{O(ζ³)}·n^{O(1)}）。
深度剖析
主结果：Transient Multiagent Pathfinding 在组合参数 k+ζ 下是固定参数可解的，算法运行时间为 2^{O(k²ζ)}·n^{O(1)}。 此前该问题的参数化研究多集中于智能体数、完工时间或图的树宽等自然参数；本文首次采用 above-and-below-guarantee 范式，把参数设为相对顺序路由上界 L 的改进量 ζ，并与 k 组合。 定理证明由一系列结构性引理支撑：先给出 2^{O(kλ)}·n^{O(1)} 的着色编码算法（引理 7）与 (kn)^{O(k)} 的 XP 算法（引理 6），再通过引理 9–16 的充分条件把一般情形归约到最短路径长度 O(ζ) 的特殊情形，最后按终点距离分情形完成证明。
下界：以 k 单独参数化是 W[1]-难的（即使图是 subcubic），以 ζ 单独参数化在终点不要求互不相同时也是 W[1]-难的，且 k+ζ 下不存在多项式核（除非 coNP⊆NP/poly）。 这些结果与主定理互补，说明组合参数化 k+ζ 在某种意义上不可再削弱，从而给出该问题在所考虑参数下近乎完整的复杂度刻画。 W[1]-难由从 Layered Vertex-Disjoint Shortest Paths 出发的参数化归约得到（定理 23、推论 24、定理 25）；无多项式核由从同一问题出发的多项式参数变换得到（定理 26）。
正面特例：当所有终点两两不同时，上界改进为 L*_{R,G}=Σdist(si,ti)−⌊(k−1)/2⌋，且问题仅以 ζ 为参数即可在 2^{O(ζ³)}·n^{O(1)} 时间内求解。 这刻画出一个自然子类，在该子类中单一参数 ζ 就足以获得固定参数可解性，与终点可重复时 ζ 单独参数化 W[1]-难形成对照。 关键引理 21 证明三个终点互不相同的智能体中总有两个能以 dist(si,ti)+dist(sj,tj)−1 的完工时间无冲突路由；引理 22 由此给出上界 L*_{R,G}；定理 2 再结合主定理完成算法。
基础结构性事实：顺序路由给出紧上界 L=1+Σdist(si,ti)，且该问题可归约为时间展开图上的 Disjoint Paths。 该上界此前作为直观策略存在，本文将其形式化并证明其紧性（路径图两端点互换的例子），同时给出把无碰撞约束编码进时间展开图 G*_λ 的构造。 引理 3 给出上界与调度性质；观察 4 与观察 5 建立与时间展开图上顶点不相交路径的等价性，进而得到 XP 与着色编码两类算法。
启示与展望
该结果适用于智能体到达终点后立即消失、每步可移动或等待、且同一时刻不允许两个智能体占用同一顶点或同一条边的模型；算法以智能体数 k 与相对上界 L 的改进量 ζ 为参数，因此当 ζ 很小而 k 可控时最有用。终点互不相同的特例把上界改进为 L*_{R,G}，使单一参数 ζ 即可给出固定参数算法。这些结论刻画的是可解性的复杂度边界，而非具体系统上的调度质量。
文中指出若干开放问题：最小完工时间是否普遍满足 λ≤2·max_i dist(si,ti)+k 尚未证明或反驳；仅以 ζ 为参数时问题究竟属于 XP 还是 para-NP-难仍未确定；在平面图或有界度图上以 k 为参数是否固定参数可解也仍开放。此外，本文为理论分析，未包含实验评估，实际系统上的表现需要另行验证。