cs.ROMar 18, 2026

ReDAG-RT: Global Rate-Priority Scheduling for Real-Time Multi-DAG Execution in ROS 2

Authors: Md. Mehedi Hasan, Rafid Mostafiz, Bikash Kumar Paul, Md. Abir Hossain, Ziaur Rahman

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

ROS 2 has become a dominant middleware for robotic systems, where perception, estimation, planning, and control pipelines are structured as directed acyclic graphs of callbacks executed under a shared executor. However, default ROS 2 executors use best-effort dispatch without cross-DAG priority enforcement, leading to callback contention, structural priority inversion, and deadline instability under concurrent workloads. These limitations restrict deployment in time-critical and safety-sensitive cyber-physical systems. This paper presents ReDAGRT, a user-space global scheduling framework for deterministic multi-DAG execution in unmodified ROS 2. The framework introduces a Rate-Priority driven global ready queue that orders callbacks by activation rate, enforces per-DAG concurrency bounds, and mitigates cross-graph priority inversion without modifying the ROS 2 API, executor interface, or underlying operating system scheduler. We formalize a multi-DAG task model for ROS 2 callback pipelines and analyze cross-DAG interference under Rate-Priority scheduling. Response-time recurrences and schedulability conditions are derived within classical Rate-Monotonic theory. Experiments in a ROS 2 Humble environment compare ReDAGRT against SingleThreadedExecutor and MultiThreadedExecutor using synthetic multi-DAG workloads. Results show up to 29.7 percent reduction in deadline miss rate, 42.9 percent reduction in 99th percentile response time, and 13.7 percent improvement over MultiThreadedExecutor under comparable utilization. Asymmetric per-DAG concurrency bounds further reduce interference by 40.8 percent. These results demonstrate that deterministic and analyzable multi-DAG scheduling can be achieved entirely in the ROS 2 user-space execution layer, providing a practical foundation for real-time robotic middleware in safety-critical systems.

Figures & tables

Fig. 1: Cross-DAG priority inversion under the default ROS 2 executor and the ReDAG RT solution. (A) Multiple independent DAGs collapse into a shared FIFO queue with no global priority ordering. (B) Low-frequency callbacks execute before high-frequency ones, causing priority inversion and deadline misses. (C) ReDAG RT enforces Rate-Monotonic ordering via a unified priority queue. (D) Deterministic execution eliminates priority inversion and bounds response times.
ApproachMulti-DAGGlobal QueueKernel ModAPI CompatFormal AnalysisEvaluation
Default Execs [ 11 ]×\times×\times✓\checkmark✓\checkmark×\timesBaseline
PiCAS [ 17 , 18 ]×\times×\times??Chain-levelReal HW
EventsEx [ 21 , 22 ]Tree×\times✓\checkmark∼\simRTA (restricted)Sim
ROSRT [ 23 ]✓\checkmarkOS-level✓\checkmark✓\checkmark×\timesAutoware
ROSCH [ 24 ]✓\checkmark×\times?∼\simDAG-syncAutoware
PREEMPT_RT [ 16 ]✓\checkmarkLinux×\times✓\checkmark×\timesThroughput
TABLE I: Comparison of ROS 2 Real-Time Scheduling Approaches
Fig. 2: ReDAG RT layered user-space scheduling architecture. Periodic DAG workloads Gk=(Vk,Ek)G_{k}=(V_{k},E_{k}) release tasks upon period expiration. A dependency-aware release stage validates timing and precedence constraints before admitting ready tasks into a unified global Rate-Monotonic priority queue ordered by arg⁡min⁡τi∈R Ti\arg\min_{\tau_{i}\in\mathcal{R}}\,T_{i} . The ReDAG RT executor performs fixed-priority preemptive arbitration across all DAGs and dispatches to the unmodified Linux execution layer. An integrated Timing Monitor computes RiR_{i} , LiL_{i} , and MRi\mathrm{MR}_{i} online, with event-driven re-scheduling closing the control loop.
ExecutorUtilizationMiss RateMax Lateness ( μ\mu s)
SingleThreadedExecutor0.60.7481,764,841
MultiThreadedExecutor (4T)0.80.5527,153
TABLE II: Baseline ROS 2 Executor Performance
Fig. 3: Effect of thread count on ReDAG RT deadline miss rate. Increasing worker threads reduces interference until saturation near eight threads.
Fig. 4: Sensitivity of ReDAG RT performance to deadline scaling. Moderate deadline relaxation reduces miss rate, while excessive slack increases interference windows.
Fig. 5: Impact of per-DAG concurrency limits on combined deadline miss rate. Asymmetric concurrency bounds significantly reduce cross-DAG interference.
Fig. 6: Cumulative distribution function (CDF) of callback response times comparing default ROS 2 executors and ReDAG RT . A leftward shift indicates reduced latency and tighter tail bounds under rate-priority scheduling.
SchedulerMedian (ms)95th %ile (ms)99th %ile (ms)
ROS 2 Default213749
ReDAG RT142228
TABLE III: Response Time Percentiles: Default ROS 2 Executors vs. ReDAG RT
SystemConfigurationMiss Rate
SingleThreadedExecutorU=0.6U=0.60.748
MultiThreadedExecutor4 Threads0.552
ReDAG RTBest Configuration0.476
ReDAG RTAvg. (6 Threads)0.686
TABLE IV: Comparison Between Default ROS 2 Executors and ReDAG RT
More in this topic

Real-Time Scheduling

Real-time scheduling allocates processors, accelerators, and network resources so tasks meet timing deadlines under workload and resource constraints.

See all 30 papers

Explore similar work

CardsList
Jun 8, 2026

Deterministic Execution of ROS 2 Applications via Lingua Franca

The Robot Operating System 2 (ROS 2) is a widely used middleware for robotic systems, characterized by a publish-subscribe (pub-sub) communication mechanism in which computation is structured as callbacks dispatched by ROS 2 executors. Despite its popularity, the pub-sub pattern in ROS 2 is inherently nondeterministic: the order in which these callbacks run is nondeterministic even within a single executor, and distributed deployments add further nondeterminism from the interleaving of messages across nodes and from network latency. Such nondeterminism often leads to concurrency issues and makes it virtually impossible to analyze for safeness and provide guarantees. We present a framework that is able to convert an unmodified ROS 2 application and run it under Lingua Franca (LF), a coordination language for deterministic execution using logical time, so that the same input always produces the same deterministic execution order. We first describe which ROS 2 features can be executed deterministically under logical time. Such features enable the possibility to establish an automatic conversion framework to extract information from a ROS 2 application and directly convert it into an LF program. The rich features of LF, such as logical-time delays, federated execution across processes, and fault handling, can then be applied to make the ROS 2 application be executed in a deterministic and timing-predictable manner without changing the ROS 2 code. We evaluate the framework on a synthetic example and on the Autoware reference system. We show that the order in which callbacks are executed differs in default ROS 2, while also having end-to-end latencies that vary across executions. In contrast, our LF-controlled ROS 2 system produces a deterministic execution order and consistent end-to-end latencies.

Harun Teper, Shaokai Lin, Shulu Li +2

TU Dortmund University · Dortmund, Germany · University of California, Berkeley +3

Robotics
AskPDF
Jun 13, 2026

OSDAG: Online Scheduling for Efficient Multi-Robot Collaboration

Coordinating heterogeneous multi-robot systems (MRS) for complex, long-horizon tasks requires both flexible high-level reasoning and efficient execution-time scheduling. Existing LLM-based approaches struggle to balance reasoning efficiency and execution flexibility. Flat sequential plans are efficient to generate but overlook parallel execution opportunities, while repeated LLM reasoning introduces high latency, and offline schedules may unnecessarily keep robots idle due to fixed execution orders. This paper presents OSDAG, a novel framework that resolves this trade-off by employing a Directed Acyclic Graph (DAG) as the central representation for multi-robot coordination, coupled with constraint-aware online scheduling. The LLM is typically invoked once as a semantic parser that decomposes a natural-language instruction into a dependency-annotated task graph encoding precedence relations, together with robot capability and resource-feasibility constraints. A lightweight online scheduler then dynamically dispatches dependency-ready tasks to their assigned robots as soon as they become idle, exposing available parallelism while preserving correctness. Experiments across five benchmark scenarios demonstrate that OSDAG achieves 5−15×5-15\times faster reasoning time than dialogue-based methods, reduces makespan by up to 38%38\% over sequential baselines, and maintains competitive success rates. Both simulation and real-world experiments on human-robot collaboration tasks validate the effectiveness and practicality of the proposed approach for efficient multi-robot coordination. The website and resources are available at http://thanhnguyencanh.github.io/LLM_DAG4MultiRobot

Thanh Nguyen Canh, Thang Tran Viet, Phuc Van Dinh +2

School of Information Science, Japan Advanced Institute of Science and Technology, Nomi, 923-1211, Ishikawa, Japan. · University of Engineering and Technology, Vietnam National University, 10000, Hanoi, Vietnam. · Department of Robotics, Hanyang University, Ansan, 15588, Gyeonggi, Korea.

Multi-Robot SystemsLarge Language Model-Based Robot PlanningMulti-Robot CoordinationHuman-Robot CollaborationRobot Task Planning
AskPDF
May 21, 2026

RED: Adaptive Real-Time DAG Scheduling for Robotic Inference under Environmental Dynamics

Robots deployed in dynamic environments must contend with environment-driven changes that reshape computation at runtime: new tasks may appear, precedence relations can shift, and overall workload structure evolves, all of which degrade performance, especially when multi-task inference is required under tight resource and real-time budgets. We present RED, a real-time scheduling framework for multi-task deep neural network workloads on resource-constrained robotic platforms that adapts to Robotic Environmental Dynamics (RED) while preserving end-to-end timing guarantees under modeling assumptions. The core of RED is a deadline-aware scheduler that assigns intermediate sub-deadlines, allowing it to accommodate evolving computation graphs and asynchronous inference induced by unpredictable conditions. The framework also supports flexible deployment of MIMONet (multi-input multi-output neural networks), commonly used in multi-tasking robots to alleviate memory pressure through weight sharing. RED explicitly leverages this shared-parameter property via a workload refinement and graph-reconstruction procedure that aligns MIMONet structure with schedulability requirements, improving compatibility and efficiency. We implement RED on NVIDIA Jetson family platforms and on an Apple M-series MacBook and evaluate it on navigation-oriented workloads representative of real robotic scenarios. Experiments show consistent gains over existing methods in throughput, deadline satisfaction, robustness to interference, adaptability, and runtime overhead.

Zexin Li, Tao Ren, Johnathan Liu +2

University of California, Riverside, USA · University of Pittsburgh, USA · University of Maryland, Baltimore County, USA +1

Efficient Neural Network InferenceReal-Time Scheduling
AskPDF