精读笔记

Problem Setting

论文标题：OSDAG: Online Scheduling for Efficient Multi-Robot Collaboration（arXiv preprint / 2026）。

这篇论文处理的是自然语言驱动的异构多机器人长时程协作：输入是高层任务、机器人能力/可达性/对象状态，输出不是单个动作序列，而是一组可并行执行但受依赖约束的子任务。关键矛盾是：LLM 擅长从语言中抽取语义任务结构，但不适合在执行期承担高频调度；而传统调度器高效但需要结构化依赖和可执行性约束。

以前方法卡在两个相反方向：dialogue-based 多 agent LLM 把协调留在语言空间里，推理开销和历史长度一起增长；centralized / flat sequence 方法虽然便宜，但会把非必要顺序也编码进计划，造成机器人空等。真正的问题不是“如何让 LLM 生成更多步骤”，而是如何只保留必要依赖，释放独立分支的并行性。

Motivation

作者的核心动机很直接：多机器人协作的效率瓶颈并不总是来自 robot execution，而经常来自 planning representation。若 LLM 输出的是线性序列，系统天然倾向保守串行；若让多个 LLM agent 对话协调，系统把调度问题变成 token 消耗和延迟问题。

因此缺的是一个中间层：既足够结构化，能被 scheduler 可靠消费；又足够语义化，能承接 LLM 对自然语言、对象状态和隐式前置条件的理解。DAG 正好承担这个角色：它把“必须先后发生”的约束与“只是生成顺序上先后”的偶然顺序分离。

Core Idea

OSDAG 的核心思想是：LLM 不参与持续协调，只做一次任务图生成；执行期完全交给轻量级在线调度器。LLM 的输出从 flat plan 改成 dependency-annotated DAG，scheduler 每当 agent 空闲时检查哪些节点前驱已完成、资源条件满足，然后立即派发。

这个改变引入的 inductive bias 是“partial order over total order”。很多机器人任务中，真正需要排序的只是 pick-before-place、handoff-before-use、open-before-store 这类局部约束；把整个任务压成全序会人为牺牲并行度。DAG 表示让系统只保留必要同步点，其他部分由执行期状态驱动展开，因此比对话协调更 scalable，也比一次性 offline sequence 更不容易产生 idle。

本质差异不在于 scheduler 算法复杂，而在于重新组织了 LLM 与控制系统的边界：LLM 负责 semantic dependency extraction，调度器负责 operational concurrency。

Method

方法里值得保留的机制只有几个。

第一，prompt grounding：把 agent reachability、action set、object state 注入 LLM 输入。它解决的是 LLM 生成不可执行动作或错误 agent assignment 的问题。这里的核心变化是把语言规划问题收缩成受 affordance 约束的结构生成问题，而不是让 LLM 在开放动作空间中自由发挥。

第二，dependency graph formalization：每个子任务包含 agent、action、object、destination、前驱任务集合，然后转成 DAG，并检查 schema、feasibility、dependency reference 和 acyclicity。它解决的是 LLM 输出无法直接执行的问题。DAG validation 并不能证明 plan 语义正确，但至少能把一部分格式错误和明显不可执行约束挡在执行前。

第三，constraint-aware online scheduling：维护 completed/running/free agent 状态，只派发前驱已完成且资源条件满足的 ready task。它解决的是 offline pre-commit 造成的空等。注意这里的选择策略只是 earliest-index，不是优化型 scheduler；因此它带来的核心变化是 online dispatch，而不是 sophisticated scheduling。

第四，resource feasibility 检查包含 holding state 和 reachability。这个部分很重要，因为 DAG 只表达先后关系，不能单独保证执行期资源状态一致。文中对复杂共享资源、碰撞、路径冲突、同步动作的建模仍然较浅。

Key Insight / Why It Works

这篇最有效的部分是把“推理”和“调度”解耦，并用 DAG 作为接口。它有效不是因为 LLM 更强，也不是因为 scheduler 更优，而是因为表示形式更接近多机器人任务的真实结构：任务通常是局部依赖图，而不是全局序列。

主要收益来源可以拆开看：

1. reasoning time 的收益主要来自 test-time compute reduction：从多轮对话变成单次 LLM 调用。这不是模型能力提升，而是系统架构上减少 LLM invocation。相比 RoCo 这类对话式方法，优势是预期中的。

2. makespan 的收益主要来自释放并行度：DAG 暴露 ready branches，online scheduler 避免等待无关任务。这是更强的 inductive bias，而不是 scaling。特别是在 handoff 或顺序依赖局部存在、但其他动作可并行的场景中，partial order 会明显优于 total order。

3. success rate 的提升部分来自 representation alignment：LLM 输出结构与执行器需要的结构更一致，减少 flat prompt 产生的歧义。但这依赖 prompt 中环境 embedding 的质量；若对象状态缺失或感知错误，LLM 很可能生成看似合理但执行错误的图。

4. w/o Graph 全失败这个 ablation 有些过强，可能反映 baseline 设计偏弱：没有依赖图不等于一定无法用其他 symbolic constraints 或 sequential fallback 成功。这个结果说明 DAG 对他们的 pipeline 必要，但不能证明 DAG 是唯一可行表示。

5. online scheduling 的核心贡献是工程上正确且必要的系统设计，但算法上非常朴素。没有 duration-aware priority、critical-path scheduling、MILP/LP comparison、uncertainty handling。因此不要把它解读为新的调度理论贡献。

总体判断：论文的 insight 是清楚的，贡献在系统分解和表示选择；不是 LLM reasoning 本身的突破，也不是 scheduling optimization 的突破。

Relation To Prior Work

它最接近三条线：LLM multi-robot dialogue coordination、LLM + symbolic planner / PDDL、LLM + dependency graph / optimization scheduling。

相对 RoCo 这类 decentralized dialogue，OSDAG 的本质差异是取消执行期语言协商，把多 agent coordination 从 conversation space 转到 graph scheduling space。这个方向更工程可控，也更适合 latency-sensitive robotics。

相对 ChatGPT-Prompts / flat sequence，OSDAG 的新增信息是显式依赖边。flat plan 最大问题是混淆了 semantic precedence 和 textual order；DAG 解决的是这个表示瓶颈。

相对 TwoStep / PDDL planning，OSDAG 更轻量，不要求完整 domain modeling，但也牺牲了形式化可验证性和符号 planner 的搜索能力。它更像 prompt-based symbolic skeleton extraction，而不是严格 classical planning。

相对 LiP-LLM 这类 dependency graph + LP makespan minimization，OSDAG 的区别在于 online dispatch 而非 offline optimized schedule。这里的实质创新较有限：dependency graph、topological constraints、ready queue scheduling 都是已有思想；新意在于把它们组合成单次 LLM decomposition + execution-time scheduler 的机器人系统，并强调避免 pre-committed offline order。

Dataset / Evaluation

实验覆盖五个 tabletop manipulation 场景，包含简单并行、三 agent 并行、隐式依赖、强顺序约束、handoff 协作。这个覆盖足以验证论文最核心的局部 claim：DAG 表示能暴露并行性，online dispatch 能减少空等，单次 LLM 调用能降低 planning latency。

但 evaluation 的外推性有限。任务规模小、对象类别少、动作 primitive 简单，dependency structure 也相对干净。真实世界实验更像 feasibility demo：一个机械臂加人类文本指令执行，说明系统接口可落地，但并没有验证复杂多机器人同步、路径冲突、动态失败恢复或大规模 agent 扩展。

baseline 比较也需要谨慎。RoCo 的高 RT 是架构性劣势，拿单次调用方法比较会天然占优；ChatGPT-Prompts 没有依赖建模，makespan 差也在预期内；TwoStep 的失败可能受 domain/context encoding 影响。文中未充分说明是否在同等 task graph quality 下比较 online scheduling 与 offline optimization，因此“online scheduling 优于 offline scheduling”的归因并不完全干净。

Limitation

最核心限制是：系统把困难从 execution-time coordination 转移到了 LLM dependency extraction。只要图错了，后端 scheduler 没有语义纠错能力。validation 只能检查 reachability、action feasibility、dependency index 和 cycle，不能检查“是否漏掉必要前置条件”或“是否多加了保守边”。

第二，scalability 上限不在 scheduler，而在 prompt 和 graph generation。agent/object 增多后，LLM 需要同时理解更多可达性、状态、资源冲突和隐式依赖；文中未充分说明 graph accuracy 如何随规模变化。单次 LLM 调用虽然省时，但也意味着没有中途澄清和分层修正。

第三，online scheduler 很弱。earliest-index ready task 可能在存在不同 duration、共享资源、critical path 的情况下产生明显次优 schedule。论文报告的 makespan gains 主要来自解除串行等待，而不是优化调度顺序；在更复杂任务中，上限会很快出现。

第四，没有 replanning。执行失败、感知漂移、抓取失败、对象位置变化会导致后续依赖图失效。作者在 conclusion 中承认这一点，但这其实是部署级瓶颈：真实机器人系统里 failure 是常态，不是 corner case。

第五，泛化 claim 要保守。当前任务看起来更像 prompt coverage + structured output 的成功，而不是强泛化规划能力。所谓隐式依赖推理可能部分来自 LLM 训练数据中的常识 retrieval；是否能处理新工具、新物理约束、新协作协议，文中未充分说明。

Takeaway

• 1. 对 LLM robotics 系统，最值得迁移的 insight 是：不要让 LLM 进入高频执行闭环；让它产出结构化中间表示，再交给传统 runtime。
• 这样通常比 multi-agent dialogue 更稳定、更低延迟。
• 2. DAG/partial-order 是多机器人任务中很强的表示 bias。
• 很多效率损失来自把任务误表示为 total order；只要能可靠提取必要依赖，就能用很简单的 scheduler 获得明显收益。

一句话总结

OSDAG 是一篇把 LLM 多机器人协作从“语言对话/线性计划”推进到“单次语义图生成 + 在线部分序调度”的系统论文，真正贡献在表示与执行边界的重划分，而不是新的 LLM 推理或调度优化算法。