精读笔记
Problem Setting
《Stigmergic Graph Memory: An Environment-Aware Approach for Many-to-Many Multi-Agent Pickup and Delivery》（arXiv preprint / 2026）实际处理的是 many-to-many MAPD 里的 endpoint instantiation，而不是单纯 MAPF routing。请求只给 SKU，source 和 destination 都有多个可行位置，因此系统的早期决策不是“怎么去目标”，而是“应该把这个请求实例化成哪个目标组合”。
真正困难点在于 allocation decision 会改变未来交通结构。静态距离最短的 source-destination pair 可能在局部 assignment 上合理，但多个 agent 持续选择同类 endpoint 后，会把瓶颈通道、交叉口、服务点推入拥塞。此时 MAPF 后端即使保持 collision-free，也只能在已经高冲突的目标集合上处理等待、绕行和重规划。
所以关键矛盾是：many-to-many 给了系统空间灵活性，但传统 assignment objective 没有利用执行反馈来决定这份灵活性应该如何转化为拥塞控制。以前方法卡在把 traffic information 放在 routing 层，而不是 endpoint selection 层。
Motivation
已有 M2M / M2M-wSKU 的基本缺口是，它们用 travel estimate 和库存分布项评估 endpoint，但这些 cost 在执行前计算，不知道这些选择是否会反复制造拥塞。它们优化的是局部服务代价，不是系统级交通负载。
已有 highway、guidance graph、traffic-flow cost 的缺口相反：它们能影响路线，但通常在 task goals 已经固定之后才生效。如果 source 和 destination 已经把 agent 推向拥塞区域，再好的 route bias 也只能做局部缓解。
作者的核心观察是，many-to-many MAPD 的 flexibility 本身就是一个 congestion-control resource。缺的不是更强的 collision checker，而是把 recent execution signals 前馈到 endpoint instantiation 的机制。
Core Idea
SGM 的核心思想是把仓库图变成一个带短期执行记忆的环境：节点和有向边记录最近等待、阻塞、流量、延迟、endpoint pressure 和成功通行等信号，并随时间衰减。这个 memory 不改变可行性约束，只改变 feasible candidate 的排序和合法边的 cost。
本质变化是建模方式从 static assignment 变成 environment-aware assignment。prior 多数是在目标已定后做 routing guidance；SGM 把执行反馈接到目标生成之前，使 controller 能决定哪些 source-destination pair 不应该继续进入 planner。
这个 inductive bias 很直接：近期造成拥塞的区域短期内大概率仍是高代价区域，因此不要继续把新任务绑定到这些区域。它不要求全局长期预测，也不要求学习一个复杂 traffic model，只需要把局部执行 trace 作为在线负反馈信号使用。这也是它可能比端到端学习或重型 integrated optimization 更 scalable 的地方。
Method
SGM 的方法可以压缩为三个机制。
第一，decaying graph memory。它解决在线交通状态既有惯性又会变化的问题。memory channel 分开记录 endpoint pressure、waiting、blocking、traversal、flow 等信号，避免把不同语义的事件揉成一个粗糙 congestion scalar。核心变化是 planner 外部多了一个可被 assignment 读取的环境状态。
第二，memory-guided endpoint steering。对每个 feasible agent-source-destination，在 M2M-style baseline cost 上加入沿 proxy path 的近期边惩罚。它解决的是静态 endpoint selection 看不到执行后果的问题。这里 proxy path 只是 scoring instrument，不是最终计划；它的作用是把候选 endpoint 和近期拥塞区域建立关联。
第三，bounded route guidance。SGM 将 directed-edge memory 映射为正且有上界的 traversal cost，让 RHCR/PBS 在保持原 MAPF 约束的前提下偏好低冲突方向。它解决 execution burden，而不是主要吞吐问题。
queue preservation 是另一个实际有效的控制器选择：保留 agent 队列可减少每步重建造成的目标抖动。但它也让主方法和 baseline 的差异不完全只来自 memory。
Key Insight / Why It Works
这篇最重要的 insight 是：many-to-many MAPD 的高杠杆位置不是 routing，而是 endpoint instantiation。只要系统有多个可行 source / destination，选择哪个 endpoint pair 就已经决定了未来 traffic demand 的空间分布。SGM 有效，是因为它把 congestion control 前移到了目标进入 planner 之前。
从结果归因看，核心贡献几乎肯定是 endpoint memory，而不是 route memory。endpoint-only 基本保留 full SGM throughput，而 routing-only 和 recent-routing control 不能产生类似收益。这说明所谓 stigmergic route guidance 更像辅助 execution efficiency；真正的新东西是把 recent execution memory 用作 allocation feature。
这不是 scaling result，也不是 data coverage result；它更像一个 better inductive bias：用短期环境记忆对 flexible task instantiation 做负反馈。也可以理解为 test-time memory reuse：系统没有学到长期模型，而是在运行时复用最近执行轨迹来修正下一批目标选择。
需要直说的是，SGM 没有形成真正的长期状态建模或预测式 planning。它依赖 recency heuristic：最近堵的地方短期继续有风险。这个假设在稳定仓库流量下很强，在非平稳需求或突发扰动下可能失效。route guidance 的价值主要是降低 planner time、blocked moves 和 replans，不应被解读为吞吐提升的主因。
Relation To Prior Work
最接近的 prior 有两条：M2M-style many-to-many allocation，以及 lifelong MAPF / MAPD 里的 highway、traffic-flow cost、guidance graph。SGM 的位置正好在两者之间：它不是替代 MAPF planner，也不是只做 route bias，而是把 graph guidance 的 execution feedback 接入 M2M allocation。
和 M2M / M2M-wSKU 的本质差异是 objective 信息源不同。M2M 用静态 travel / inventory cost 来实例化 endpoint；SGM 让同一个 endpoint choice 依赖近期实际执行状态。因此它新增的信息不是另一个距离项，而是 execution-time congestion signal。
和 highway / traffic-flow 方法的本质差异是作用界面不同。highway 类方法在目标已定后影响路径；SGM 在目标未定时影响 source-destination 选择。这个差异比具体 memory channel 更重要。
看似新的 stigmergy 概念，其实是 decaying environmental trace 的老思想重组。实质创新在于把这种 trace 放到 many-to-many endpoint instantiation，而不是把它包装成 pheromone routing。
Dataset / Evaluation
实验覆盖五个 50x27 warehouse / maze layouts、三种 fleet load、paired request replay 和多个 seed；对核心 claim 来说，paired protocol 是合理的，因为它减少了 request stream variance。主实验确实支持“SGM 在这些 small-map warehouse benchmarks 上提高 throughput”。
更有说服力的是 ablation 和 routing controls：recent routing alone 与 static highway 没有带来同等级提升，而 endpoint-only 几乎复现 full SGM 的完成量。这直接验证了论文最重要的机制归因：endpoint steering 是主因。
但 evaluation 的外推边界很明显。没有真实机器人，没有连续动力学，没有动态库存扰动，没有强非平稳 demand，也没有大规模真实仓库拓扑。medium-scale transfer 只有有限 seed，更多是在证明不是只对五个小图过拟合，而不是证明工业规模泛化。
另一个问题是 baseline provenance。M2M 是 reconstructed baseline，且 baseline queue handling 与 SGM controller policy 有差异。文中做了 matched cap 和 no-queue-preserve，但仍不能完全排除工程集成差异带来的增益放大。
Limitation
SGM 成立依赖 endpoint flexibility。如果 SKU 的 feasible source / destination 很少，或者业务约束强到 endpoint 基本固定，主机制会退化成普通 route guidance，而实验已经显示 routing-only 的吞吐收益有限。
它也依赖近期执行记忆对未来有预测性。稳定 demand、稳定 layout、重复性 traffic pattern 下这个假设合理；如果 shift 很快，decaying memory 可能把旧拥塞当成当前风险，导致 endpoint steering 过度避让。
scalability 上限文中未充分说明。虽然有 shortlist 和 candidate cap，但在更大 SKU catalog、更高 endpoint multiplicity、更复杂库存约束下，候选生成和 scoring 仍可能成为主要成本。ASGM 的 compute-throughput trade-off 表明 full SGM 不是免费层。
增益来源不完全干净。endpoint memory、route memory、queue preservation、event-driven repair、baseline reconstruction 差异交织在一起；虽然 ablation 指向 endpoint steering，但主实验的绝对 gain 可能包含一部分 controller engineering。
真实 deployment gap 也很大。RHCR/PBS 下的离散图、秒级 timestep、预执行 blocking prevention 与真实 AMR 的连续运动、局部控制、通讯延迟、充电、载荷和安全区约束之间还有距离。
Takeaway
- 第一，many-to-many MAPD 的 endpoint selection 应该被当成 congestion-control problem，而不是 assignment bookkeeping。
- 这个视角比具体 SGM channel 更值得迁移。
- 第二，execution memory 最有价值的接口未必是 routing；在存在目标灵活性的系统里，把 feedback 接到目标实例化之前通常更有杠杆。
- 第三，bounded preference layer 是一个实用设计：不碰可行性约束、不改 collision predicates，只改变排序和 cost。
一句话总结
这篇论文把 many-to-many MAPD 的核心控制点从“目标已定后的路径引导”前移到“目标实例化时的拥塞感知选择”，是一次基于在线执行记忆的 allocation-level inductive bias 重组。