精读笔记
Problem Setting
[On the Hardness of Optimal Motion on Trees]（arXiv preprint / 2026）
这篇论文实际处理的是：在树上，最优 MAPF/PMG 是否仍然计算困难。这里的重点不是找一条可行路径；树上 labeled/colored PMG 的可行性早有多项式算法。真正的问题是最优性：最少移动次数、最小 makespan、最小 flowtime 是否能利用树的简单拓扑得到多项式算法。
困难点在于树没有环、没有交叉 gadget、没有高 treewidth，传统从 SAT/flow/crossover 等构造硬性的套路不容易直接落下去。树上 agent 不能互相穿越，路径唯一，这一方面简化了 feasibility，另一方面也制造了强顺序依赖。关键矛盾是：树结构消除了几何复杂性，但保留甚至强化了“谁必须先让路、谁必须先进入目标”的全局排序约束。论文的判断是，最优 PMT/MAPF 在树上的困难不来自图结构复杂，而来自 stack-like LIFO 约束与公共瓶颈。
Motivation
已有路线的问题是分散：distance、makespan、flowtime 通常需要不同 gadget；labeled 与 colored 也常分开处理；树上的已有 hardness 主要集中在 makespan，且限制条件并未统一解决 PMT 距离最优和 colored PMG 的长期空白。
作者的核心观察是 Stack Rearrangement 是树上运动的一个非常自然的子结构。每个栈就是一条路径，多个栈共享一个中心节点；从一个栈顶拿物体放到另一个栈顶，正好是 pebble/agent 通过中心从一条树枝移动到另一条树枝。于是，如果 optimal SR 本身 hard，那么树上最优运动的 hard 就不需要复杂图 gadget，而可以直接从 LIFO 依赖和中心瓶颈推出。
关键缺口有两个：一是 SR 最优复杂性本身此前未定；二是 colored PMG 的 optimal hardness 在任意图类上都缺失。论文的策略是先补上 SR 这个源头，再把它作为统一硬性生成器。
Core Idea
核心思想是把树上多体运动等价地看成“多栈系统上的重排”。树枝不是 corridor，而是 stack；中心点不是普通 hub，而是唯一 pop-push 接口。由于树上路径唯一且同一路径上的 agents/pebbles 不能穿越，任意从栈内位置到外部的有效移动都必须以栈顶顺序暴露出来。这就把 MAPF/PMT 的时空冲突问题降维成了栈重排中的顺序依赖问题。
这个视角的本质区别在于：prior hardness 往往构造复杂 interaction gadget 来模拟选择、变量、子句或交叉；本文不靠图的复杂性，而靠最优性 lower bound 的 tightness。对于 distance，shortest-path lower bound 是基准，relocation/detour 正好产生额外 2 的代价；对于 makespan，中心点每个时间只能承载一个 transit，SR move 数对应时间长度；对于 flowtime，中心最后访问时刻的排列给出一个强下界，padding/gate 用来把 relocation 的时序差异统一放大。换句话说，它把多个目标函数都压到同一个“中心通道访问序列”的 combinatorial skeleton 上。
Method
1. LSR hardness：解决 labeled 情形的基础源问题。MFAS 的边被编码成两个 edge objects 和两个 vertex-object stack 之间的依赖。如果每个 object 只移动一次，则 edge (i,j) 强制 o_i 必须早于 o_j；有向环无法满足，因此必须 relocation 某些边对象。额外移动数精确对应 feedback arc set 大小。这个机制的作用是把“最优栈重排”变成“最少打断多少顺序依赖”。
2. 2-colored SR hardness：解决 colored 情形不能依赖标签顺序的问题。作者用 3-Partition 构造红/蓝容量循环：清空 item stacks 会消耗红目标容量并释放蓝目标容量；清空 checkpoint 则反向恢复容量。若每个 item 最多移动一次，每一阶段必须正好凑出 K 的容量，因此得到三元划分。这里 hardness 来自容量守恒，而不是身份匹配。
3. SR 到 PMT distance：stack path 嵌入 subdivided star 或 comb。shortest-path 总距离 L 是天然 lower bound；没有 relocation 的 SR 解对应所有 pebbles 沿最短路一次到位；relocation 对应进入 buffer leaf 的 detour，增加 2。反向方向依赖这样一个事实：超过 L 的代价只能来自非最短 detour，因此可抽取为 SR relocation。
4. atomic traversal lemma：这是 comb/max-degree-3 版本的关键。若某 pebble 沿树上最短路移动，则其 moves 可重排为连续完成的 atomic traversal。它排除了“多个 direct pebble 交错移动导致不对应 stack move”的问题，使 PMT 解可规整为 SR move 序列。
5. SR 到 MAPF makespan/flowtime：makespan 中，中心 c 的连续占用序列模拟 SR moves，时间 M+1 对应 M 次 pop-push。flowtime 中，利用每个 agent 最后一次访问中心的时间 t_a，得到 flowtime = sum t_a + target-depth term。colored zero-relocation 情况下，最优就是 t_a = 1..N；labeled 情况再引入 gate/padding agents，使任何 relocation 都至少延迟大量 padding final transits，从而把 relocation 数稳定映射到 flowtime 增量。
Key Insight / Why It Works
最重要的 insight 是：树上最优运动的困难不是“路径选择”，而是“顺序依赖压缩”。在树上路径唯一，所以每个 agent 应该怎么走几乎没有自由；真正的自由是何时释放哪个栈顶、何时占用中心、是否需要临时绕到 buffer。最优性问题因此退化为对一个全局 partial order 的最小破坏。这也是为什么 MFAS 和 3-Partition 都能自然落进来。
LSR 的 MFAS 归约是 labeled 部分最核心的贡献。它把每条有向边变成“若不额外移动，就强制一个顶点顺序”的 gadget；最优额外移动数等价于打断多少边依赖。这个机制非常干净，且直接解释了 PMT 的 distance hardness：detour 就是 feedback arc removal。
colored 部分的核心不是路径冲突，而是容量 accounting。由于同色可互换，不能再靠对象身份制造依赖；作者改用红/蓝目标容量的可达性来锁定阶段结构。这个构造强在它证明 two colors 已经足够，且 one-move-per-item 判定已经 hard；这比一般 colored MAPF 的 gadget 更接近问题本质。
makespan 的归约相对直接，主要是 SR move 序列与中心瓶颈的时间序列同构。flowtime labeled 的 padding/gate 构造则更像技术性放大器：它不是新的运动结构 insight，而是为了消除 relocation 发生早晚对 sum-of-costs 的影响。这里可以判断，论文最实质的贡献在 stack-hardness 与 distance/makespan 的统一嵌入；labeled flowtime 的部分更偏 engineering of reductions，但必要且有效。
这不是 scaling、retrieval、data coverage 类型的工作；它的增益来自 better latent structure / inductive bias：把 tree MAPF 的 latent structure 识别为 stack rearrangement。这个抽象的迁移价值较高，因为它提供了一个比传统 graph gadget 更小、更可复用的 hardness core。
Relation To Prior Work
与 Kornhauser 等经典 PMG feasibility 工作的关系是直接补上 optimality gap：可行性在树上简单，但最优性并不随之简单。与 Yu、Surynek、Demaine 等一般图/网格 MAPF hardness 相比，本文不依赖复杂图类；它把 hardness 推到 subdivided stars 和最大度 3 树，说明 treewidth=1 本身不能救最优 MAPF。
与近期树上 makespan hardness 工作相比，本文的本质推进是统一性和目标覆盖：不只是 makespan，而是 distance/PMT 和 flowtime；不只是 labeled，也包括 2-colored。尤其 colored PMG 的 hardness 是此前缺口，本文给出任意图类上的首个结果且已经在树上成立。
与 token swapping on trees 的关系更多是对照而非继承。Token swapping 允许相邻 token 交换，运动原语不同；本文处理的是通过空位移动/并行无碰撞移动，stack bottleneck 更强。看似都在树上研究 token/pebble 最优运动，但底层困难机制并不相同。
实质创新是把 Stack Rearrangement 提升为统一硬性源头，并同时解决 SR 自身开放问题。SR 到 tree MAPF 的嵌入思路可能曾被观察到，但此前没有形成完整复杂性框架；本文新增的信息是：SR 不只是建模便利，而是树上最优运动的核心 obstruction。
Dataset / Evaluation
这是一篇理论复杂性论文，没有 dataset、实验 benchmark、真实机器人或仿真评测。evaluation 的形式是归约覆盖范围：labeled/2-colored、distance/makespan/flowtime、subdivided stars/max-degree-3 trees。
这些证明基本支持核心 claim：树上最优运动在标准目标下 NP-hard，并且 hard 已经出现在非常简单的树类中。尤其 subdivided star 的结果很强，因为它把 branching vertices 限到 1；max-degree-3 comb 则说明 hardness 不依赖高阶 hub。
但 evaluation 没有回答实际算法层面的难度分布：NP-hard 实例是高度结构化的 stack instances，是否代表仓储 MAPF 或一般树状通道场景中的 empirical hardness，文中未充分说明。这不削弱理论结论，但限制了对 practical solver 设计的直接推断。
Limitation
第一，边界还没完全压紧。labeled LSR/PMT 使用 depth 3，作者认为可压到 depth 2，但当前版本没有完成。对于 subdivided star，branching vertex 已经是 1；但 depth、叶数、空位数、agent density 等参数化边界仍未系统刻画。
第二，flowtime labeled 的构造依赖大量 padding agents。这个机制有效，但说明归约需要人为放大 relocation 的延迟效应；它证明复杂性，但没有像 distance 那样揭示一个完全自然的一一代价对应。若研究实际 flowtime solver，这部分 insight 的迁移性弱于 LSR/PMT 的 shortest-path lower bound 机制。
第三，结果主要是 NP-hardness，不含 approximation hardness 或 fixed-parameter lower bounds。对于“额外 detour 数很小”“接近 shortest-path lower bound”“栈深固定很小”“颜色数固定且结构受限”等更细粒度情形，论文只给出部分暗示。
第四，colored hardness 依赖 3-Partition 的容量构造，栈深 K 随实例数值变化；虽然 strong NP-complete 保证多项式规模，但该构造更像容量编码而非一般 colored motion 中常见的局部冲突结构。其实际泛化意义需要谨慎解读。
第五，论文发现 lower-bound attainability 在 labeled PMT on trees 可多项式检测，这与 NP-hardness 共存，说明 hardness 位于“需要少量额外 detour/relocation 的优化层”。这一点尚未展开，可能是后续正向算法更有价值的入口。
Takeaway
- 1. 树上 MAPF/PMG 的最优困难核心可以被抽象为 Stack Rearrangement；这比传统 gadget 化 reductions 更可迁移，也更解释性。
- 2. 对树结构的直觉需要修正：treewidth=1 消除了路径选择复杂性，但不会消除全局顺序依赖；LIFO + bottleneck 已足够产生 NP-hardness。
- 3. colored motion 的真正边界在 1 color 与 2 colors 之间。
- unlabeled 可用 flow/network-flow 思路解决，但只要两个颜色，容量与阶段结构就能编码强 NP-hard 问题。
一句话总结
这篇论文把树上最优 PMT/MAPF 的长期开放复杂性问题归约到 Stack Rearrangement 这一统一硬性核心，证明困难本质来自 LIFO 顺序依赖与中心瓶颈，而不是图结构复杂性。