OSDAG: Online Scheduling for Efficient Multi-Robot Collaboration

Thanh Nguyen Canh

Thang Tran Viet

Phuc Van Dinh

Xiem HoangVan

Nak Young Chong

School of Information Science, JAIST, Japan
VNU University of Engineering and Technology, Vietnam
Department of Robotics, Hanyang University, Korea
, 2026.

[Paper]

[Code]

Multi-Robot Systems (MRS) enable heterogeneous agents to collaboratively accomplish complex tasks that exceed individual robot capabilities. Recent advances in Large Language Models (LLMs) have introduced flexible task decomposition and natural language interfaces for MRS. However, existing LLM-based approaches suffer from two critical limitations: (1) excessive reliance on LLM inference, leading to high computational costs and latency, and (2) dependence on offline scheduling, which forces sequential execution, causing prolonged robot idle time, and increases overall makespan. This paper presents OSDAG, a novel framework that integrates LLM-based task reasoning with Directed Acyclic Graph (DAG) representation and constraint-aware online scheduling. The LLM decomposes high-level natural language instructions into dependency-annotated subtasks, which are formalized as a DAG encoding precedence and resource constraints. A dynamic scheduler then allocates ready tasks to idle agents in real time, maximizing parallel execution while preserving task dependencies. Experiments across five benchmark scenarios demonstrate that OSDAG achieves 7–15 x faster reasoning time compared to dialogue-based methods, reduces makespan by up to 48% over sequential baselines, and maintains competitive success rates. Both simulation and real-world experiments on dual-arm manipulation tasks validate the effectiveness and practicality of the proposed approach for efficient multi-robot coordination.

Paper

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

OSDAG: Online Scheduling for Efficient Multi-Robot Collaboration

2026.

[pdf]

Overview

System overview of OSDAG. The framework processes a high-level natural language instruction through three stages: (1)~LLM-driven Task Decomposition grounds the instruction into agent-assigned, dependency-annotated sub-tasks using environment context and capability descriptions; (2)~Task Graph Formalization constructs a DAG encoding precedence and resource constraints; (3)~Constraint-Aware Online Scheduling dynamically assigns ready tasks to idle agents in real time, maximizing parallel execution while preserving task dependencies.

Illustration of the online scheduling process. Steps~(1)--(5) demonstrate dynamic task allocation across three robots. Dashed rectangles indicate ongoing tasks; robots are tagged as busy or free based on current status. Upon task completion, agents immediately receive new assignments satisfying precedence and resource constraints, eliminating idle time and maximizing parallel efficiency.

Simulation environments for the five evaluation tasks.

Experiments Results

Performance comparison across all tasks. We report Success Rate (SR, %), Step Success Efficiency (SSE), Reasoning Time (RT, seconds), and Makespan (MS, seconds) averaged over 10 trials. Best results are in bold. "--" indicates execution failure.

Ablation study results. We evaluate each component's contribution by systematic removal. Removing dependency graphs causes complete failure (SR=0). Disabling online scheduling increases makespan by up to 63% despite correct plans.


Simulation Demonstration.


Real experiment.

Code

[github]

Citation

1. Canh T. N., Viet T. T., Dinh P. V., HoangVan X., Chong A.Y. OSDAG: Online Scheduling for Efficient Multi-Robot Collaboration. , 2026.

@article{canh2026human, 
                                  

                                    author    = {Canh, Thanh Nguyen and Viet, Thang Tran and Dinh, Phuc Van and HoangVan, Xiem and Chong, Nak Young}, 
                                  

                                    title     = {OSDAG: Online Scheduling for Efficient Multi-Robot Collaboration}, 
                                  

                                    booktitle = {}, 
                                  

                                    year      = {2026}, 
                                  

                                    address   = {}, 
                                  

                                    month     = {}, 
                                  

                                    DOI       = {}
                                  

                                }

Acknowledgements

This work was supported by JST SPRING, Japan Grant Number JPMJSP2102.
This webpage template was borrowed from https://akanazawa.github.io/cmr/.