⚡ electrical engineering

DAG-Based QoS-Aware Dynamic Task Placement for Networked Multi-Stage Control Pipelines

This work-in-progress paper proposes a DAG-based, QoS-aware dynamic task placement framework that optimizes the sensing-perception-planning-control pipeline in networked robotics by jointly minimizing latency, deadline violations, and switching costs through a hysteresis-enabled algorithm.

Original authors: Thien Tran, Jonathan Kua, Thuong Hoang, Minh Tran, Yuemin Ding, Jiong Jin

Published 2026-05-20

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Thien Tran, Jonathan Kua, Thuong Hoang, Minh Tran, Yuemin Ding, Jiong Jin

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 a factory floor where robots are trying to do complex tasks, like assembling delicate parts or navigating a busy warehouse. To do this, they rely on "Physical AI"—smart software that needs to see the world, understand what it sees, plan a move, and then execute that move.

The problem is that this "brain" work is getting so heavy that the robot's own onboard computer can't handle it all. If the robot tries to do everything itself, it gets overwhelmed and slows down. If it sends all the data to a remote server (the "cloud") to think for it, the signal takes too long to travel back and forth, causing the robot to jitter or miss its timing.

This paper proposes a smart, middle-ground solution called DAG-Based QoS-Aware Dynamic Task Placement. Here is what that means in plain English:

1. The "Assembly Line" Analogy (The DAG)

Think of the robot's job as a four-step assembly line:

Sensing: The robot's camera takes a picture.
Perception: The computer figures out, "That is a red box."
Planning: The computer decides, "I need to grab the red box."
Control: The robot's arm actually moves to grab it.

The authors call this a DAG (Directed Acyclic Graph), which is just a fancy way of saying "a one-way flow of tasks."

2. The "Hard-Anchored" vs. "Movable" Tasks

The paper argues that not all steps on this line should move around.

The Anchors (Sensing & Control): The camera (Step 1) and the arm motor (Step 4) must stay right on the robot. Why? Because if the robot has to wait for a signal from a server to know what it's seeing or to move its arm, the delay is too long. It's like trying to drive a car while waiting for a text message to tell you if the light is red.
The Movers (Perception & Planning): The "thinking" parts (Steps 2 and 3) are flexible. They can stay on the robot, or they can be sent to a nearby "Edge Server" (a powerful computer sitting right next to the factory floor) if the robot is too busy.

3. The "Traffic Controller" (Dynamic Task Placement)

The core of this paper is a smart "Traffic Controller" that decides where the "Thinking" steps should run. It doesn't just pick one spot and stick with it; it changes its mind in real-time based on traffic conditions.

If the robot is busy: It sends the thinking tasks to the Edge Server.
If the network is slow or glitchy: It pulls the thinking tasks back onto the robot to avoid waiting for a slow internet connection.
If the Edge Server is busy: It might split the work (Hybrid mode), sending some tasks to the server and keeping others on the robot.

4. The "No-Flip-Flopping" Rule (Hysteresis)

A major problem with smart systems is that they can get "jittery." Imagine a thermostat that turns the heat on and off every 10 seconds because the temperature fluctuates slightly. This is bad for robots.

This paper introduces a "Hysteresis" rule (a fancy word for a "cool-down" period). The system won't move the tasks unless the new spot is significantly better than the current one, and it won't move them back immediately. It forces the system to "sit still" for a while to make sure the change is actually worth it. This prevents the system from constantly flipping back and forth, which would cause chaos.

5. The "Scorecard" (QoS Cost Function)

How does the system decide what is "better"? It uses a scorecard that weighs four things:

Speed: Is the robot reacting fast enough?
Deadlines: Did the robot miss a critical timing window?
Robot Health: Is the robot's own computer overheating?
Server Health: Is the nearby Edge Server overloaded?

The system constantly calculates a "cost" score. If moving a task lowers the score (meaning better speed and less stress), it moves it. If the score doesn't improve enough to justify the move, it stays put.

Summary

In short, this paper presents a framework for smartly splitting a robot's brain between the robot itself and a nearby computer. It uses a mathematical model to ensure the robot never misses a deadline, never overheats, and never gets confused by a slow internet connection. It acts like a highly efficient manager who constantly reassigns workers to the best desks based on who is busy and how fast the phone lines are working, ensuring the factory runs smoothly without the robots tripping over their own feet.

Technical Summary: DAG-Based QoS-Aware Dynamic Task Placement for Networked Multi-Stage Control Pipelines

1. Problem Statement

The integration of Physical AI (PAI) into industrial robotics, particularly through Vision-Language-Action (VLA) models and World Foundation Models (WFMs), has created a computational mismatch. These models demand inference costs that exceed the onboard capabilities of typical industrial robots, while their sub-20 second cold-start latencies are incompatible with the sub-millisecond deadlines required for closed-loop control.

Existing deployment strategies face significant limitations:

Monolithic Local Execution: Running all stages (sensing, perception, planning, control) on the robot saturates AI-accelerated hardware, leading to high deadline violation rates (empirically reported above 40% in testbeds).
Static Edge Offloading: Permanently offloading tasks to edge servers exposes the control loop to network jitter and latency variability, which can violate safety envelopes.
Current Adaptive Placement (ATP): Existing adaptive controllers typically relocate only a single pipeline stage based on binary threshold rules. They lack a formal multi-stage model, do not optimize a multi-objective cost function, and offer no analytical resistance to task placement oscillation (chatter).

The core challenge is to design a runtime orchestration layer that dynamically places multi-stage control pipelines across a Cloud-Fog-Edge continuum while respecting closed-loop timing budgets and ensuring stability.

2. Methodology

The authors propose a Directed Acyclic Graph (DAG)-based Quality-of-Service (QoS)-aware Dynamic Task Placement (DTP) framework.

A. System Modeling

Pipeline as a DAG: The sensing–perception–planning–control pipeline is formalized as a DAG $G=(V, E_G)$ with four tasks ( $T_1$ to $T_4$ ).
Architectural Invariants:
- Hard-Anchored Stages: Sensing ( $T_1$ ) and Control ( $T_4$ ) are fixed to the physical robot hardware ( $R_1$ and $R_2$ ) to preserve sub-millisecond local reflex loops.
- Relocatable Adaptation Space: Perception ( $T_2$ ) and Planning ( $T_3$ ) are allowed to migrate between the robot and an edge server ( $E$ ).
Compute Fabric: The system considers a set of nodes $N = R \cup E \cup C$ , interconnected by industrial real-time networks (LAN, TSN, or 5G-URLLC).

B. QoS-Aware Cost Function
The framework operates over observation windows of $W$ control cycles. It defines a multi-objective cost function $J_k$ for window $k$ :
$J_k = \alpha_L \tilde{L}_{95,k} + \alpha_V VD_k + \alpha_r \tilde{U}_{r,k} + \alpha_e \tilde{U}_{e,k} + \alpha_S S(\pi_k, \pi_{k-1})$

Metrics:
- $\tilde{L}_{95,k}$ : Normalized 95th-percentile end-to-end latency (capturing tail behavior).
- $VD_k$ : Deadline violation rate (primary SLA).
- $\tilde{U}_{r,k}, \tilde{U}_{e,k}$ : Normalized CPU utilization on robots and edge servers.
Switching Penalty: The term $S(\pi_k, \pi_{k-1})$ uses Hamming distance to penalize frequent migrations, preventing "placement chatter" that degrades network stability.
Weights: In industrial settings, the weights prioritize SLA compliance ( $\alpha_V$ ) over raw latency ( $\alpha_L$ ) and stability ( $\alpha_S$ ).

C. Algorithm and Constraints

Candidate Set: To ensure tractability on edge hardware, the algorithm evaluates a small, interpretable set of placements $\Pi_{cand}$ $Π_{c an d}$ :
- LOC: Fully local ( $T_2, T_3$ on robots).
- SO: Static offload ( $T_2, T_3$ on Edge).
- HYB: Hybrid ( $T_2$ on Edge, $T_3$ on Robot).
Hysteresis Mechanism: The DTP algorithm (Algorithm 1) enforces stability via:
- Minimum Dwell Time ( $N_{min}$ ): Prevents rapid flipping when metrics fluctuate near thresholds.
- Cost-Improvement Threshold ( $\Delta_{min}$ ): Migration occurs only if the cost reduction is statistically significant.
Estimation: For non-active placements, the system estimates QoS metrics using static profiling, online emulation (routing a fraction of cycles), or conservative scaling.

3. Key Contributions

Formal DAG Model: A pipeline model that distinguishes hard-anchored safety-critical stages from a relocatable adaptation space, agnostic to the underlying network substrate.
Multi-Objective Cost Function: A window-based function that jointly optimizes tail latency, deadline violation rates, hardware utilization, and migration stability.
Stabilized DTP Algorithm: An algorithm that generalizes previous single-stage adaptive placement to concurrent multi-task placement, incorporating hysteresis and switching penalties to bound oscillation.
Validation Roadmap: A structured two-phase plan involving discrete-event simulation and Hardware-in-the-Loop (HIL) testing on physical robotic testbeds.

4. Results and Validation Strategy

As a Work-in-Progress (WiP) paper, the authors present a theoretical framework and a qualitative analysis rather than final empirical results.

Qualitative Analysis: The authors predict that the DTP policy will converge to LOC under adverse network conditions (high jitter), to SO under robot CPU stress, and to HYB when both compute and communication resources are jointly constrained.
Validation Roadmap:
- Phase 1 (Simulation): A discrete-event simulator will test cost-function sensitivity and hysteresis bounds against stress scenarios (e.g., Gaussian network fault injection, CPU stress).
- Phase 2 (HIL): A modular cloud-edge-robotics testbed will provide empirical data on compute profiles and network delays to compare the proposed DAG-QoS DTP against LOC, SO, and single-stage ATP baselines.

5. Significance and Claims

The paper claims to address the "Control–Communication–Computing (3C)" co-design gap in industrial automation. Its significance lies in:

Runtime Determinism: By anchoring $T_1$ and $T_4$ , the framework decouples actuation safety from network state, preserving sub-millisecond reflex loops.
Adaptability: The relocatable space accommodates heterogeneous compute demands (including emerging VLA/LLM workloads) without overloading hardware or hard-coding decisions.
Stability Guarantee: The Hamming-distance switching penalty provides a mathematically bounded guarantee against placement chatter, translating to observable control-loop stability.
Industry Maturity: The authors argue that a system cannot credibly claim Industry 4.0 maturity or readiness for Industry 5.0 agentic automation if it cannot guarantee a deadline violation rate ($VD$) of $\le 5\%$ across the deployment envelope.

The framework is positioned as a foundational "runtime infrastructure" or "PAI Nervous System" that enables LLM agents and VLA models to operate reliably under real-world compute and network variability. Future work is planned to expand the candidate placement set, support multi-robot fleets, and integrate online hyperparameter adaptation.