In robotics, timing failures are often safety failures. A control loop that misses deadlines can destabilize a stable design. Therefore, we require:

• Real-time constraint: correctness depends on time as well as value.
• Determinism: bounded temporal variability (jitter) across runs.

A task \( \tau_i \) is typically modeled as a periodic or sporadic real-time job with parameters:

• Worst-case execution time (WCET): \( C_i \)
• Period or minimum inter-arrival time: \( T_i \)
• Relative deadline: \( D_i \) (often \( D_i=T_i \))
• Release (arrival) time of job \(k\): \( r_{i,k} \)
• Finish time: \( f_{i,k} \)

The absolute deadline of job \(k\) is \( d_{i,k} = r_{i,k} + D_i \), and the real-time correctness condition is

\[ f_{i,k} \le d_{i,k}\quad \text{for all jobs }k. \]

flowchart TD
  A["Robot sensing event"] --> B["Task release r_i,k"]
  B --> C["Scheduler picks next task"]
  C --> D["Task executes for C_i (worst-case)"]
  D --> E["Finish time f_i,k"]
  E --> F["Check deadline: f_i,k <= d_i,k"]
  F -->|met| G["Safe control update sent"]
  F -->|missed| H["Timing fault -> degraded / unsafe behavior"]
        

Real-time systems are classified by the consequence of missing deadlines:

• Hard real-time: any miss is unacceptable (e.g., motor current limit loops).
• Firm real-time: late results are useless but occasional misses tolerated (e.g., perception frame drops).
• Soft real-time: lateness degrades quality (e.g., high-level planning refresh).

Robotics stacks usually mix all three. Low-level embedded controllers are hard/firm, while onboard AI pipelines are soft.

We also distinguish:

• Time-triggered control (periodic sampling).
• Event-triggered reactions (interrupts, sensor events).

Let the intended sampling period be \( T \). The actual sampling instants are \( t_k \). Define sampling jitter as

\[ \delta_k = t_k - kT. \]

A system is deterministic in time if jitter is bounded:

\[ |\delta_k| \le J_{\max}\quad \text{for all }k. \]

For a discrete-time control loop (students know linear control), jitter perturbs the effective sampling period: \( T_k = T + (\delta_k-\delta_{k-1}) \). If the continuous-time plant is \( \dot{x}=Ax+Bu \), then the sampled transition becomes

\[ x_{k+1} = e^{A T_k}x_k + \left(\int_{0}^{T_k} e^{A s}\,ds\right)Bu_k. \]

Hence temporal non-determinism changes the discrete model itself, which can invalidate stability proofs based on fixed \(T\).

A common determinism metric is the coefficient of variation of response times:

\[ \text{CV}_R = \frac{\sqrt{\operatorname{Var}(R_{i,k})}}{E[R_{i,k}]}, \]

where \(R_{i,k}=f_{i,k}-r_{i,k}\) is the response time. Smaller \( \text{CV}_R \) indicates higher determinism.

Consider \(n\) periodic tasks on one CPU, preemptive, independent, with deadlines equal to periods \(D_i=T_i\). The CPU utilization is

\[ U = \sum_{i=1}^{n} \frac{C_i}{T_i}. \]

Two classical schedulers:

• Rate Monotonic (RM): fixed priority, shorter period = higher priority.
• Earliest Deadline First (EDF): dynamic priority, earliest absolute deadline = highest priority.

4.1 EDF Optimality Condition

For the above model, EDF is feasible iff

\[ U \le 1. \]

Proof sketch: Under EDF, at any time interval of length \(L\), the processor demand is bounded by \( \sum_i \left\lceil \frac{L}{T_i}\right\rceil C_i \). For \(D_i=T_i\), the demand bound is at most \(UL + \sum_i C_i\). If \(U<1\), then for sufficiently large \(L\), demand grows slower than supply \(L\), and EDF (which always schedules the most urgent job) avoids deadline misses. Conversely, if \(U>1\), average demand exceeds capacity, so no scheduler can succeed.

4.2 RM Utilization Bound (Liu–Layland)

RM is not always optimal, but it guarantees feasibility if

\[ U \le n(2^{1/n}-1) \equiv U_{\text{RM}}(n). \]

Note \( \lim_{n\to\infty} U_{\text{RM}}(n)=\ln 2 \approx 0.693\).

Proof (compact): Assume tasks are ordered by increasing period \(T_1\le \dots \le T_n\). Under RM, the worst-case completion for task \(i\) occurs when all higher-priority tasks release simultaneously. The demand in one period \(T_i\) is

\[ W_i = C_i + \sum_{j=1}^{i-1} \left\lceil \frac{T_i}{T_j}\right\rceil C_j. \]

Feasibility requires \(W_i \le T_i\) for all \(i\). Liu and Layland showed the minimum of

\[ \prod_{j=1}^{n}\left(1+\frac{C_j}{T_j}\right) \]

subject to \(W_i \le T_i\) is achieved at \( \frac{T_{i}}{T_{i-1}}=2 \), giving \( \prod_{j=1}^{n}(1+U_j)=2 \) where \(U_j=C_j/T_j\). Taking logs and using concavity of \(\ln\),

\[ \sum_{j=1}^{n} \ln(1+U_j) \le \ln 2 \;\Rightarrow\; \sum_{j=1}^{n} U_j \le n(2^{1/n}-1). \]

Thus the bound is sufficient for RM schedulability.

RM bound can be pessimistic. A tighter test computes worst-case response time. For task \(i\), higher-priority tasks are \(hp(i)=\{1,\dots,i-1\}\). The response time satisfies the fixed-point equation

\[ R_i = C_i + \sum_{j\in hp(i)} \left\lceil \frac{R_i}{T_j}\right\rceil C_j. \]

Iterate with \(R_i^{(0)}=C_i\) and

\[ R_i^{(k+1)} = C_i + \sum_{j\in hp(i)} \left\lceil \frac{R_i^{(k)}}{T_j}\right\rceil C_j, \]

until convergence or \(R_i^{(k)}>D_i\). The task is schedulable iff \(R_i \le D_i\) for all \(i\).

RTA is widely used in embedded robot controllers because it produces deterministic guarantees tied to WCET.

In Chapter 10 Lesson 1, we compared microcontrollers and CPUs. Timing uncertainty comes from:

• Preemption and multitasking (OS scheduling).
• Caches and pipelines on CPUs (variable execution).
• Interrupt storms from noisy sensors.
• Bus contention (SPI/CAN/EtherCAT introduced next lesson).

Therefore, deterministic robot layers often run on:

• bare-metal microcontrollers, or
• real-time operating systems (RTOS) with bounded latencies.

We simulate periodic tasks, check schedulability, and visualize jitter in a simple control loop timing model. (Python is for analysis; embedded execution usually uses C/C++.)

import math
from dataclasses import dataclass

@dataclass
class Task:
    C: float  # WCET
    T: float  # period
    D: float  # deadline (assume D=T by default)

def utilization(tasks):
    return sum(t.C / t.T for t in tasks)

def rm_bound(n):
    return n*(2**(1/n) - 1)

def rta_schedulable(tasks):
    # tasks sorted by increasing T (RM priorities)
    tasks = sorted(tasks, key=lambda x: x.T)
    for i, ti in enumerate(tasks):
        R = ti.C
        while True:
            interference = 0.0
            for tj in tasks[:i]:
                interference += math.ceil(R / tj.T) * tj.C
            R_next = ti.C + interference
            if R_next == R:
                break
            if R_next > ti.D:
                return False
            R = R_next
    return True

tasks = [
    Task(C=1.0, T=5.0, D=5.0),
    Task(C=1.5, T=8.0, D=8.0),
    Task(C=2.0, T=12.0, D=12.0)
]

U = utilization(tasks)
print("Utilization:", U)
print("RM sufficient bound:", rm_bound(len(tasks)))
print("RM schedulable by bound?", U <= rm_bound(len(tasks)))
print("RM schedulable by RTA?", rta_schedulable(tasks))

# Simple jitter simulation: intended T=10ms with bounded noise
import numpy as np
np.random.seed(0)
T = 0.010  # 10 ms
Jmax = 0.002
N = 1000
delta = np.random.uniform(-Jmax, Jmax, size=N)
t_k = np.arange(N)*T + delta
T_k = np.diff(t_k)

print("Observed sampling period mean:", T_k.mean())
print("Observed period std (jitter):", T_k.std())
      

Libraries that help timing analysis in Python include numpy, scipy, and real-time simulation tools such as simpy. But note that Python itself is not deterministic enough for hard real-time control.

The following shows a minimal periodic executor (conceptual RTOS style) using steady clocks. On real robots you would use an RTOS or ROS2 real-time executor, but this illustrates the idea.

#include <chrono>
#include <thread>
#include <iostream>

using Clock = std::chrono::steady_clock;

int main() {
    const auto T = std::chrono::milliseconds(5); // 5ms control period
    auto next_release = Clock::now();

    while (true) {
        auto start = Clock::now();

        // --- Task body (bounded WCET assumed) ---
        // read sensors
        // compute control
        // write actuators
        // ---------------------------------------

        auto finish = Clock::now();
        auto exec_time = std::chrono::duration_cast<std::chrono::microseconds>(finish - start);

        next_release += T;
        std::this_thread::sleep_until(next_release);

        auto lateness = Clock::now() - next_release;
        std::cout << "Exec(us)=" << exec_time.count()
                  << " lateness(us)="
                  << std::chrono::duration_cast<std::chrono::microseconds>(lateness).count()
                  << std::endl;
    }
    return 0;
}
      

In practice, C++ real-time robotics uses: rclcpp with ROS2 real-time settings, chrono monotonic clocks, and sometimes frameworks like OROCOS RTT or micro-ROS for microcontrollers.

Java is common in higher-level robot software. Here we implement RTA on task sets.

import java.util.*;

class Task {
    double C, T, D;
    Task(double C, double T, double D) { this.C = C; this.T = T; this.D = D; }
}

public class RTA {
    static boolean rtaSchedulable(List<Task> tasks) {
        tasks.sort(Comparator.comparingDouble(t -> t.T)); // RM order

        for (int i = 0; i < tasks.size(); i++) {
            Task ti = tasks.get(i);
            double R = ti.C;

            while (true) {
                double interference = 0.0;
                for (int j = 0; j < i; j++) {
                    Task tj = tasks.get(j);
                    interference += Math.ceil(R / tj.T) * tj.C;
                }
                double Rnext = ti.C + interference;
                if (Rnext == R) break;
                if (Rnext > ti.D) return false;
                R = Rnext;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        List<Task> tasks = Arrays.asList(
            new Task(1.0, 5.0, 5.0),
            new Task(1.5, 8.0, 8.0),
            new Task(2.0, 12.0, 12.0)
        );
        System.out.println("Schedulable? " + rtaSchedulable(tasks));
    }
}
      

In robotics, Java timing-critical code is rarer, but deterministic execution can be achieved with real-time Java VMs or by pushing hard real-time to C/C++ nodes.

MATLAB is useful to study how jitter affects discrete-time control models. We simulate stochastic sampling periods and compare the effective discrete system.

rng(0);
A = [0 1; -2 -0.5];
B = [0; 1];

T  = 0.01;      % nominal sample time
Jm = 0.002;     % max jitter
N  = 500;

delta = (2*rand(N,1)-1)*Jm;
t_k = (0:N-1)'*T + delta;
T_k = diff(t_k);

Phi_nom = expm(A*T);

Phi_var = zeros(2,2,N-1);
for k=1:N-1
    Phi_var(:,:,k) = expm(A*T_k(k));
end

disp("Nominal Phi:");
disp(Phi_nom);
disp("Mean Phi under jitter:");
disp(mean(Phi_var,3));
disp("Std of Phi entries:");
disp(std(reshape(Phi_var,4,[]),0,2));
      

In Simulink, you would represent jitter by using a “Variable-Step” solver and inserting a random delay block before the Zero-Order Hold, then compare stability margins to the fixed-step case.

Problem 1 (Utilization Test): Three periodic tasks have \((C_1,T_1)=(1,4)\), \((C_2,T_2)=(1.5,6)\), \((C_3,T_3)=(2,12)\) with \(D_i=T_i\). (a) Compute \(U\). (b) Decide schedulability under EDF. (c) Decide using RM bound.

Solution:

\[ U=\frac{1}{4}+\frac{1.5}{6}+\frac{2}{12} =0.25+0.25+0.166\bar{6} =0.666\bar{6}. \]

(b) Since \(U<1\), EDF guarantees feasibility. (c) RM bound for \(n=3\) is

\[ U_{\text{RM}}(3)=3(2^{1/3}-1)\approx 3(1.26-1)=0.78. \]

Because \(U\approx 0.667<0.78\), RM is also guaranteed feasible.

Problem 2 (Response-Time Analysis): Two tasks under RM: \(\tau_1=(C_1=1,T_1=5)\), \(\tau_2=(C_2=2,T_2=8)\), deadlines equal periods. Use RTA to test \(\tau_2\).

Solution:

RM priority: \(\tau_1\) higher. Fixed-point:

\[ R_2 = C_2 + \left\lceil \frac{R_2}{T_1}\right\rceil C_1 =2 + \left\lceil \frac{R_2}{5}\right\rceil. \]

Iterate: \(R_2^{(0)}=2\). Then \(R_2^{(1)}=2+\lceil 2/5\rceil=3\). Next: \(R_2^{(2)}=2+\lceil 3/5\rceil=3\). Converged \(R_2=3\le D_2=8\). Schedulable.

Problem 3 (Jitter Bound): A robot controller samples at nominal \(T=10\) ms. Actual times satisfy \(|\delta_k|\le 1\) ms. Show that the instantaneous sample period satisfies \(|T_k-T|\le 2\) ms.

Solution:

Recall \(T_k=T+(\delta_k-\delta_{k-1})\). Therefore

\[ |T_k-T| = |\delta_k-\delta_{k-1}| \le |\delta_k|+|\delta_{k-1}| \le 1\text{ ms}+1\text{ ms}=2\text{ ms}. \]

Problem 4 (Design Question): Explain why a high-level path planner can be soft real-time, but a motor torque loop must be hard real-time.

Solution:

Path planners produce guidance over long horizons. Late updates degrade performance but the previous plan still provides a safe fallback. Torque loops enforce actuator limits and stability every few milliseconds; missing deadlines can cause uncontrolled currents, overheating, or instability. Thus they require strict temporal correctness.

We formalized real-time tasks, deadlines, determinism, and jitter; derived EDF and RM schedulability conditions; and presented response-time analysis for exact fixed-priority testing. Timing guarantees are foundational for safe robot computation and will be used when we study robot buses and distributed embedded networks next.