💻 computer science

OSDAG: Online Scheduling for Efficient Multi-Robot Collaboration

OSDAG is a novel framework that combines single-shot LLM-based task decomposition into a dependency-annotated DAG with a lightweight online scheduler to enable efficient, parallel multi-robot collaboration, significantly reducing reasoning latency and task completion time compared to existing methods.

Original authors: Thanh Nguyen Canh, Thang Tran Viet, Phuc Van Dinh, Xiem HoangVan, Nak Young Chong

Published 2026-06-16

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Thanh Nguyen Canh, Thang Tran Viet, Phuc Van Dinh, Xiem HoangVan, Nak Young Chong

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the manager of a busy kitchen with a team of chefs (robots) who have different skills. Some can chop, some can grill, and some can only stir. Your goal is to get a complex meal ready as fast as possible using a recipe written in plain English.

This paper introduces a new system called OSDAG to help manage this kitchen. It solves two major problems that other "smart" systems have:

The "Endless Chat" Problem: Some systems make every chef talk to a super-intelligent AI (an LLM) constantly to decide what to do next. This is like having the whole kitchen stop and wait for a phone call every time a chef needs to grab a knife. It gets slower and slower as you add more chefs.
The "Rigid Line" Problem: Other systems ask the AI to write the entire schedule before anyone starts cooking. If Chef A finishes their task early, they have to stand around doing nothing, waiting for Chef B to finish a task that isn't even related to them, just because the schedule said "Chef B goes first."

How OSDAG Works: The "Master Blueprint" Approach

Instead of constant chatting or rigid lines, OSDAG uses a three-step process that acts like a smart project manager:

1. The One-Time Brainstorm (LLM Reasoning)
Instead of asking the AI for advice every second, OSDAG asks it once at the very beginning. The AI reads your English instruction (e.g., "Sort these colored blocks into bowls") and looks at the kitchen's layout. It then draws a Master Blueprint (called a Directed Acyclic Graph, or DAG).

Think of this blueprint not as a list, but as a flowchart. It shows:

Who does what (which robot gets which block).
What needs to happen before what (e.g., "You can't place the block in the bowl until you pick it up").
What can happen at the same time (e.g., "Robot A can pick up a red block while Robot B picks up a blue one").

2. The Dynamic Dispatcher (Online Scheduling)
Once the blueprint is drawn, a lightweight, fast computer program takes over. This is the "dispatcher." It doesn't ask the AI again; it just watches the robots.

As soon as a robot finishes a task and becomes free, the dispatcher looks at the blueprint.
If the next task on the blueprint is ready (meaning all its "prerequisites" are done), the dispatcher immediately assigns it to that free robot.
If two robots are free and two independent tasks are ready, they both start working immediately. No waiting!

3. The Safety Check
The system constantly checks: "Is this robot close enough to the object?" and "Does this robot have the right tool?" If a robot tries to grab something it can't reach, the system fixes the plan before it happens.

Why It's Better (The Results)

The authors tested this system in computer simulations and with real robots (and even a human working alongside a robot). Here is what they found:

Speed: It is 5 to 15 times faster at planning than systems that rely on constant chatting between robots and AI.
Efficiency: It finishes tasks up to 38% faster than rigid, pre-planned schedules. This is because robots aren't standing around waiting for unrelated tasks to finish.
Success: It handles complex situations well, like figuring out that you must "open a drawer" before you can "put a cup inside," a step that other systems often missed.

The Catch

The paper notes a few limitations:

The system relies on the AI getting the "blueprint" right the first time. If the environment gets too messy or there are too many robots, the AI might make a mistake in the initial plan.
If a robot drops a block or breaks, the system doesn't have a built-in way to "re-plan" on the fly; it just stops.

In a Nutshell

OSDAG is like hiring a brilliant architect to draw a detailed, flexible construction plan once, and then hiring a quick-witted foreman to hand out tasks to workers the moment they are free. It avoids the bottleneck of endless meetings and the waste of workers standing idle, making the whole team work together much more efficiently.

Technical Summary of OSDAG: Online Scheduling for Efficient Multi-Robot Collaboration

1. Problem Statement

The paper addresses the challenge of coordinating Heterogeneous Multi-Robot Systems (MRS) for complex, long-horizon tasks. While Large Language Models (LLMs) have enabled robots to interpret natural language and adapt to novel tasks without reprogramming, existing LLM-based MRS frameworks suffer from two critical bottlenecks:

Latency from Repeated Inference: Decentralized, dialogue-based approaches (e.g., RoCo) require continuous LLM queries as the number of agents increases, causing conversation history to grow linearly and inflating execution latency.
Inefficiency of Offline Scheduling: Most current frameworks, including those combining LLMs with optimization or planning, rely on offline scheduling where the entire plan is computed before execution begins. This forces robots to remain idle while waiting for sequentially ordered predecessors, even when independent subtasks are ready to be executed in parallel.

The core problem is to develop a system that maintains the high-level reasoning capabilities of LLMs while enabling real-time, parallel execution that minimizes idle time and avoids repeated inference overhead.

2. Methodology

The proposed framework, OSDAG (Online Scheduling for Efficient Multi-Robot Collaboration), integrates LLM-based task reasoning with Directed Acyclic Graph (DAG) representation and constraint-aware online scheduling. The pipeline consists of three main stages:

A. LLM-Driven Task Decomposition (Single Inference)
Unlike dialogue-based methods, OSDAG invokes the LLM exactly once. The LLM acts as a high-level reasoner rather than a low-level controller. Given a natural language instruction, the current workspace context (object states, agent capabilities, and reachability), the LLM generates a structured list of subtasks.

Input: The prompt includes the instruction, available agents, reachable objects, executable actions, and a strict output schema.
Output: A candidate task list where each task is annotated with an assigned agent, action, target object, destination, and a set of prerequisite tasks (dependencies).
Validation: Generated tasks are validated against feasibility constraints (e.g., ensuring the assigned agent can reach the object and perform the action). Invalid plans are rejected and regenerated.

B. Task Graph Formalization (DAG Construction)
The validated task list is converted into a Directed Acyclic Graph (DAG), $G = (V, E)$ .

Vertices: Represent individual subtasks.
Edges: Represent precedence constraints (e.g., a "place" task cannot start until the corresponding "pick" task is complete).
Significance: This structure explicitly encodes both sequential dependencies (e.g., pick $\to$ place) and inter-agent dependencies (e.g., object handoffs). Crucially, it exposes independent task branches that can be executed in parallel, unlike flat action sequences.

C. Constraint-Aware Online Scheduling
A lightweight online scheduler executes the DAG in real time.

Mechanism: The scheduler continuously monitors agent states (Free or Busy) and the completion status of tasks.
Dynamic Allocation: When an agent becomes free, the scheduler immediately identifies the set of "ready" tasks (those whose predecessors are completed and for which the agent is capable). It assigns the earliest indexed ready task to the agent.
Parallelism: This event-driven approach allows independent branches of the DAG to proceed concurrently, eliminating the idle time inherent in offline, pre-committed schedules.

3. Key Contributions

The paper outlines three primary contributions:

LLM-DAG Integration: A mechanism that combines LLM reasoning with DAG-based dependency modeling, where the LLM generates a dependency-annotated graph based on agent capabilities and environmental constraints in a single inference pass.
Online Scheduling Algorithm: A real-time task allocation algorithm that ensures concurrency, minimizes idle time, and strictly adheres to dependency and resource constraints.
Empirical Validation: Comprehensive experiments in both simulation and real-world scenarios demonstrating superior performance in success rate, latency, and scalability compared to baseline models.

4. Experimental Results

The system was evaluated across five benchmark scenarios involving tabletop manipulation with 2–3 agents, covering tasks like object sorting, cleaning, and handoffs.

Reasoning Time: OSDAG achieved a 5–15× speedup in reasoning time compared to dialogue-based methods (e.g., RoCo). For a 3-agent task, RoCo required 206.3 seconds, whereas OSDAG required only 14.0 seconds. OSDAG matched the low latency of flat-sequence generators (ChatGPT-Prompts) while maintaining dependency awareness.
Makespan Reduction: By utilizing online scheduling to execute independent tasks in parallel, OSDAG reduced the total completion time (makespan) by 33% to 38% compared to offline scheduling baselines. For example, in a 5-agent handoff task, the makespan dropped from 41.6s (baseline) to 26.0s.
Success Rate: OSDAG maintained competitive success rates (80–100%). Notably, it achieved an 80% success rate on a complex task requiring implicit dependency reasoning (e.g., opening a drawer before placing items), whereas baselines like RoCo and TwoStep failed (0%) due to a lack of object-state context.
Ablation Studies:
- Removing the dependency graph caused complete failure (0% success rate) due to resource conflicts.
- Removing online scheduling increased makespan by 49–60% despite correct plans, confirming the necessity of dynamic allocation.
- Removing object/action embeddings increased reasoning time and reduced success rates due to hallucinations.

Real-World Validation: The framework was deployed on a UF850 manipulator collaborating with a human. The system successfully coordinated heterogeneous agents (robot and human) with different interfaces, validating its practical applicability.

5. Significance and Limitations

The paper claims that OSDAG represents a significant step toward efficient multi-robot coordination by bridging the gap between high-level LLM reasoning and low-level execution efficiency. Its primary significance lies in demonstrating that single-pass LLM inference combined with online DAG scheduling can outperform both dialogue-heavy decentralized systems and rigid offline planners.

However, the authors modestly acknowledge limitations:

The framework relies on the LLM to generate dependency edges; reasoning errors may increase with environmental complexity and agent count.
The current task selection policy (earliest indexed ready task) may not yield globally optimal schedules.
The system currently lacks replanning mechanisms; execution failures can cascade without dynamic recovery.