💻 computer science

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

Cet article présente ReDAG-RT, un cadre d'ordonnancement global en espace utilisateur pour ROS 2 qui garantit l'exécution déterministe et priorisée de multiples graphes de dépendances (DAG) sans modifier l'API ou le système d'exploitation, réduisant ainsi significativement les taux d'échec de délais et les temps de réponse dans les systèmes robotiques critiques.

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

Publié 2026-03-20

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

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

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous dirigez une grande cuisine de restaurant très fréquenté (c'est le système robotique). Dans cette cuisine, vous avez plusieurs équipes qui travaillent en même temps : une équipe prépare les entrées (la perception du robot), une autre cuisine les plats principaux (la planification du trajet), et une troisième s'occupe du service (le contrôle du mouvement).

Dans le système actuel de ROS 2 (le logiciel qui gère ces robots), il y a un problème majeur : toutes les commandes arrivent sur un seul et même comptoir, dans une file d'attente unique, et sont traitées dans l'ordre où elles sont arrivées, peu importe leur importance.

Le Problème : La File d'Attente Chaotique

Imaginez que le chef de la brigade (le robot) a besoin d'une information critique toutes les 20 millisecondes pour ne pas heurter un piéton (c'est une tâche "rapide" et vitale). Mais au même moment, un serveur arrive avec une commande de dessert qui doit être faite toutes les 100 millisecondes (c'est une tâche "lente" et moins urgente).

Dans le système actuel (ROS 2 par défaut) :

Si le serveur arrive 1 seconde avant le chef, sa commande est mise en premier dans la file.
Le chef doit attendre que le dessert soit préparé avant de recevoir son information vitale.
Résultat : Le robot rate son deadline, il est en retard, et il pourrait avoir un accident. C'est ce qu'on appelle une inversion de priorité. Le "lent" bloque le "rapide".

C'est comme si, dans une salle d'urgence, le patient qui a une égratignure (tâche lente) était soigné avant celui qui a une hémorragie (tâche rapide), simplement parce que l'égratignure est arrivée 5 minutes plus tôt à l'accueil.

La Solution : ReDAGRT (Le Chef d'Orchestre Intelligent)

Les auteurs de cet article, Md. Mehedi Hasan et son équipe, ont créé une solution appelée ReDAGRT. Imaginez que ReDAGRT est un nouveau chef d'orchestre qui intervient directement dans la cuisine, sans avoir besoin de reconstruire le bâtiment ou de changer les uniformes des cuisiniers.

Voici comment cela fonctionne avec des analogies simples :

1. La File d'Attente Prioritaire (Le Tri Intelligent)

Au lieu d'une seule file d'attente "Premier arrivé, premier servi", ReDAGRT met en place un système de tri automatique.

Dès qu'une tâche arrive, le chef d'orchestre regarde son rythme (sa fréquence).
Règle d'or : Plus une tâche doit être répétée souvent (rythme rapide), plus elle a de la priorité.
Si la tâche "Éviter le piéton" (20ms) et la tâche "Préparer le dessert" (100ms) arrivent en même temps, la tâche rapide est immédiatement placée tout en haut de la pile. Le dessert attendra patiemment.

2. La Gestion des Équipes (Les Limites de Concurrency)

Parfois, une seule équipe (un DAG) essaie de faire trop de choses en même temps et encombre la cuisine.

ReDAGRT impose des limites : "L'équipe des entrées ne peut avoir que 2 plats en préparation simultanément".
Cela empêche une seule équipe de monopoliser tous les cuisiniers et de bloquer les autres équipes. C'est comme si on disait : "Ne faites pas 10 plats en même temps, faites-en 2, puis attendez que ce soit fini."

3. Pas de Chantier, Juste une Mise à Jour Logicielle

Ce qui est génial avec ReDAGRT, c'est qu'il n'a pas besoin de changer le moteur du robot (le système d'exploitation Linux) ni de réécrire tout le code des applications. Il agit comme un logiciel intermédiaire (middleware) qui s'interpose intelligemment entre les tâches et les processeurs. C'est comme ajouter un logiciel de gestion de trafic intelligent sur une route existante, sans avoir besoin de construire de nouveaux ponts.

Les Résultats : Pourquoi c'est une révolution ?

Les chercheurs ont testé leur système avec des scénarios complexes (plusieurs robots, plusieurs tâches en même temps) et les résultats sont impressionnants :

Moins d'accidents (Moins de "Deadlines manqués") : Le taux d'échec (quand le robot rate une tâche critique) a diminué de près de 30 %.
Plus de rapidité : Le temps de réponse le plus lent (le "pire des cas") a été réduit de 43 %. Le robot réagit beaucoup plus vite et de manière plus prévisible.
Moins de stress pour le système : En limitant le nombre de tâches simultanées par équipe, ils ont réduit les conflits entre les équipes de 40 %.

En Résumé

Le système ROS 2 actuel, c'est comme une file d'attente de supermarché où tout le monde est traité pareil, ce qui pose problème quand il y a une urgence.

ReDAGRT, c'est comme installer un système de "Coupe-file" intelligent basé sur l'urgence réelle :

Il identifie qui a le plus besoin d'être servi rapidement.
Il empêche les grosses équipes de bloquer les petites.
Il garantit que les tâches vitales (comme éviter un obstacle) sont toujours traitées en premier, peu importe qui est arrivé avant.

C'est une avancée majeure pour rendre les robots plus sûrs, plus fiables et capables de fonctionner dans des environnements critiques (comme les voitures autonomes ou les robots de sauvetage), le tout sans avoir à tout réinventer.

Titre : ReDAGRT : Ordonnancement Global par Priorité de Taux pour l'Exécution Multi-DAG Temps Réel dans ROS 2

1. Problématique : Les Limites de ROS 2 Temps Réel

Les systèmes robotiques modernes reposent sur ROS 2 (Robot Operating System 2) comme middleware dominant. Ces systèmes exécutent généralement plusieurs pipelines de calcul concurrents (perception, localisation, planification, contrôle), structurés sous forme de Graphes Acycliques Dirigés (DAG) de callbacks.

Cependant, les exécuteurs par défaut de ROS 2 (SingleThreadedExecutor et MultiThreadedExecutor) présentent des défauts structurels majeurs pour les applications temps réel critiques :

Absence de priorité globale : Les callbacks sont gérés dans une file d'attente globale de type FIFO (First-In-First-Out) sans respect des priorités basées sur la fréquence d'activation.
Inversion de priorité inter-DAG : Un callback de faible fréquence (ex: planification) peut s'exécuter avant un callback de haute fréquence et critique (ex: contrôle), simplement parce qu'il est arrivé plus tôt dans la file. Cela viole les principes classiques de l'ordonnancement temps réel (Rate-Monotonic).
Interférence non bornée : L'absence de mécanisme de contrôle d'accès entre les DAGs entraîne une contention incontrôlée, augmentant la variabilité du temps de réponse (jitter) et provoquant des dépassements de délais (deadline misses), même à des niveaux d'utilisation modérés.

2. Méthodologie : L'Architecture ReDAGRT

Le papier propose ReDAGRT, un framework d'ordonnancement global intégré dans l'espace utilisateur de ROS 2, sans modifier l'API ROS 2, l'interface de l'exécuteur ni le noyau Linux.

Principes Clés :

Modèle de Tâche Multi-DAG : Le système modélise la charge de travail comme un ensemble de DAGs indépendants ( $G_k$ ) partageant les mêmes ressources d'exécution. Chaque tâche $\tau_i$ est caractérisée par son temps d'exécution pire cas ( $C_i$ ), sa période ( $T_i$ ) et son échéance ( $D_i = T_i$ ).
Ordonnancement par Priorité de Taux (Rate-Monotonic - RM) :
- Une file d'attente globale unique est maintenue pour tous les callbacks prêts.
- Les priorités sont assignées statiquement selon la période : plus la période est courte (fréquence élevée), plus la priorité est haute ( $T_i < T_j \implies P_i > P_j$ ).
- Cela garantit que les tâches critiques de haute fréquence préemptent systématiquement les tâches moins critiques, éliminant l'inversion de priorité.
Contrôle de Concurrency par DAG : Le framework impose des limites strictes au nombre de callbacks actifs simultanément par DAG. Cela permet de limiter l'interférence entre les pipelines.
Sémantique de Préemption : L'ordonnanceur vérifie à chaque point de décision si une tâche prête a une priorité strictement supérieure à la tâche en cours d'exécution. Si oui, une préemption est déclenchée.
Analyse de Faisabilité : Le papier dérive des bornes de temps de réponse et des conditions de faisabilité basées sur la théorie classique de Liu et Layland, adaptées aux contraintes de précédence intra-DAG.

3. Contributions Principales

Analyse Structurelle : Identification et caractérisation de l'inversion de priorité inter-DAG comme une faille fondamentale des exécuteurs ROS 2 par défaut.
Modèle Formel : Développement d'un modèle d'interférence formel pour les systèmes Multi-DAG, permettant de borner l'interférence ( $I_i$ ) et de calculer des temps de réponse worst-case.
Implémentation et Validation : Conception et publication open-source de ReDAGRT, un exécuteur unifié qui fonctionne entièrement dans l'espace utilisateur, compatible avec l'API ROS 2 existante.

4. Résultats Expérimentaux

Les expériences ont été menées dans un environnement ROS 2 Humble avec des charges de travail synthétiques Multi-DAG (périodes mixtes, criticité mixte) comparées aux exécuteurs par défaut.

Performances Clés :

Réduction des Dépassements de Délais : ReDAGRT réduit le taux de dépassement de délais combiné jusqu'à 29,7 % par rapport aux configurations de base (en passant de 4 à 8 threads).
Amélioration de la Prédictibilité : Compression de 42,9 % du temps de réponse au 99ème percentile (passant de 49 ms à 28 ms), indiquant une réduction drastique du jitter.
Comparaison avec les Exécuteurs Par Défaut :
- Par rapport au MultiThreadedExecutor, ReDAGRT offre une réduction de 13,7 % du taux de dépassement de délais.
- Par rapport au SingleThreadedExecutor, l'amélioration est encore plus marquée, évitant les latences pathologiques (de l'ordre de 1,7 s contre quelques millisecondes).
Impact des Limites de Concurrency : L'utilisation de limites de concurrency asymétriques (différentes pour chaque DAG) réduit l'interférence de 40,8 % par rapport aux configurations symétriques, validant l'importance du contrôle d'accès par DAG.
Scalabilité : Les performances s'améliorent jusqu'à 8 threads, au-delà desquels les coûts de synchronisation (contention de verrous) commencent à limiter les gains.

5. Signification et Impact

Ce travail démontre qu'il est possible d'obtenir un comportement déterministe et analysable pour l'exécution Multi-DAG dans ROS 2 sans modifier le système d'exploitation sous-jacent.

Pour la Robotique Critique : ReDAGRT fournit une base théorique et pratique pour déployer des systèmes cyber-physiques (CPS) sûrs, où la garantie de respect des délais est essentielle (ex: véhicules autonomes, robots chirurgicaux).
Approche Middleware : En résolvant le problème au niveau du middleware (espace utilisateur) plutôt qu'au niveau du noyau, la solution reste portable et compatible avec l'écosystème ROS 2 existant.
Fondement Théorique : Le papier comble le fossé entre la théorie de l'ordonnancement temps réel (RM, analyse de réponse) et la pratique de la robotique logicielle, offrant des outils pour raisonner sur la faisabilité des systèmes complexes.

En conclusion, ReDAGRT transforme l'exécuteur ROS 2 d'un modèle "best-effort" en un système temps réel prévisible, capable de gérer des charges de travail hétérogènes et concurrentes avec des garanties temporelles formelles.