💻 computer science

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

Este artículo presenta ReDAG-RT, un marco de programación global basado en prioridades de tasa que, sin modificar ROS 2, garantiza la ejecución determinista y con análisis de tiempo real de múltiples grafos acíclicos dirigidos, reduciendo significativamente las tasas de pérdida de plazos y los tiempos de respuesta en sistemas ciberfísicos críticos.

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

Publicado 2026-03-20

📖 4 min de lectura☕ Lectura para el café

CC BY 4.0

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

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina que un robot moderno es como una cocina de restaurante muy ocupada.

En esta cocina, hay varios chefs trabajando al mismo tiempo:

Un chef hace la salsa (Percepción: ver el mundo).
Otro chef corta las verduras (Localización: saber dónde está).
Otro planifica el menú (Planificación: decidir a dónde ir).
Y el jefe de cocina sirve los platos (Control: mover el robot).

Cada tarea es como una cadena de pasos (un "DAG" en términos técnicos) que debe seguir un orden lógico.

El Problema: La Cocina Caótica (ROS 2 por defecto)

En la versión actual de ROS 2 (el sistema operativo de los robots), todos estos chefs lanzan sus pedidos a una única pila de platos en la mesa central. No importa si un pedido es urgente (como "¡Frenar de inmediato!") o si es algo lento (como "Limpiar el polvo").

¿Qué pasa?
El camarero (el "Executor") simplemente toma el plato que llegó primero a la pila.

Si el chef de la salsa (una tarea lenta) pone su plato en la pila justo antes que el jefe de cocina (una tarea rápida y urgente), el camarero le sirve a la salsa primero.
Resultado: El robot tarda demasiado en frenar o girar. Se produce lo que los expertos llaman "inversión de prioridad": lo menos importante bloquea a lo más importante. Es como si el camarero le diera el postre al cliente antes de traerle el agua porque el postre llegó a la mesa un segundo antes.

La Solución: ReDAGRT (El Nuevo Jefe de Sala)

Los autores de este paper crearon ReDAGRT, que actúa como un nuevo y estricto Jefe de Sala que no toca la cocina, sino que organiza la pila de pedidos.

Aquí está la magia en analogías simples:

La Regla de la Frecuencia (Rate-Priority):
El nuevo Jefe de Sala ignora quién llegó primero. En su lugar, mira qué tan rápido se repite la tarea.
- Analogía: Si el corazón del robot (que late 50 veces por segundo) necesita un plato, ese plato tiene prioridad sobre el plato del chef que solo limpia el polvo una vez cada 10 segundos.
- Regla de oro: "Cuanto más rápido se repite la tarea, más alto es el puesto en la fila". Esto asegura que las tareas críticas siempre se sirvan primero.
La Pila de Pedidos Inteligente:
En lugar de una pila desordenada, ReDAGRT usa una pila mágica ordenada.
- Si llega un pedido urgente, se coloca automáticamente arriba de todo, empujando a los pedidos lentos hacia abajo.
- Si el robot está muy ocupado, el sistema sabe exactamente cuántos platos puede manejar cada chef a la vez para que no se saturen.
Sin tocar la cocina:
Lo genial es que este Jefe de Sala funciona dentro del restaurante sin necesidad de cambiar las recetas de los chefs ni reformar la cocina (no modifica el código base de ROS 2 ni el sistema operativo). Solo organiza el flujo de trabajo.

¿Qué lograron? (Los Resultados)

En sus pruebas, compararon la cocina caótica (ROS 2 normal) con la cocina organizada (ReDAGRT):

Menos platos quemados: Redujeron en casi un 30% los casos en que un robot no cumplía su tarea a tiempo (como no frenar a tiempo).
Respuesta más rápida: Las tareas más urgentes tardaron un 43% menos en completarse. Es como si el robot pudiera pensar y actuar mucho más rápido cuando es necesario.
Previsibilidad: Antes, el robot a veces tardaba 1 segundo y otras 100 milisegundos (impredecible). Ahora, el tiempo es constante y seguro, como un reloj suizo.

En Resumen

ReDAGRT es como poner un semáforo inteligente en el cerebro de un robot. En lugar de dejar que los coches (tareas) compitan desordenadamente en la intersección, el semáforo da prioridad a los coches de emergencia (tareas rápidas y críticas) sobre los camiones de reparto lentos.

Esto permite que los robots sean más seguros, más rápidos y capaces de trabajar en entornos donde un error de tiempo podría ser peligroso, todo sin tener que reconstruir el robot desde cero.

1. El Problema: Inversión de Prioridad y Falta de Determinismo en ROS 2

El sistema operativo robótico ROS 2 se ha convertido en el middleware dominante, donde las pipelines de percepción, planificación y control se estructuran naturalmente como Grafos Acíclicos Dirigidos (DAGs) de callbacks. Sin embargo, los ejecutores por defecto de ROS 2 (SingleThreadedExecutor y MultiThreadedExecutor) presentan limitaciones críticas para sistemas de tiempo real y seguridad crítica:

Falta de Ordenamiento Global: Los ejecutores utilizan colas de lista de espera (FIFO) compartidas sin una política de prioridad global entre diferentes DAGs.
Inversión de Prioridad Cross-DAG: Un callback de baja frecuencia (baja prioridad temporal) puede ejecutarse antes que uno de alta frecuencia (alta prioridad) simplemente porque llegó antes a la cola o adquirió un hilo primero. Esto viola los principios clásicos de programación de tiempo real (Rate-Monotonic).
Interferencia No Acotada: Bajo cargas concurrentes, la interferencia entre pipelines independientes es impredecible, lo que provoca inestabilidad en los tiempos de respuesta, aumento de la variabilidad (jitter) y fallos en los plazos (deadline misses).
Limitación de Análisis: La ausencia de una jerarquía de prioridad unificada impide aplicar análisis de viabilidad (schedulability) clásicos a todo el sistema.

2. Metodología: ReDAGRT

El artículo presenta ReDAGRT, un marco de programación global en espacio de usuario diseñado para integrarse dentro de la capa de ejecución de ROS 2 sin modificar la API, la estructura de los gráficos de la aplicación o el planificador del kernel de Linux.

Arquitectura y Diseño:

Cola de Listo Global Unificada: ReDAGRT reemplaza las colas locales por una única cola de prioridad global que contiene todos los callbacks listos de todos los DAGs.
Asignación de Prioridad Estática (Rate-Monotonic - RM): La prioridad se asigna estrictamente basándose en el período de activación del tarea ( $T_i$ ). Tareas con períodos más cortos (mayor frecuencia) reciben prioridad más alta ( $T_i < T_j \implies P_i > P_j$ ).
Límites de Concurrencia por DAG: Se introducen límites configurables (max_active) para controlar cuántos callbacks de un mismo DAG pueden estar activos simultáneamente, evitando que un solo DAG sature los recursos.
Semántica de Despacho Preemptivo: El planificador selecciona la tarea con la prioridad más alta (menor período) de la cola global. Si una tarea de mayor prioridad se vuelve lista, se produce una preemptión inmediata sobre la tarea actual.
Modelo Formal: Se formaliza un modelo de tareas multi-DAG donde la interferencia se acota matemáticamente. La interferencia máxima que una tarea $i$ puede sufrir está limitada por la suma de los tiempos de ejecución peores (WCET) de todas las tareas de mayor prioridad ($hp(i)$).

3. Contribuciones Clave

El artículo ofrece tres contribuciones principales:

Análisis Estructural: Identifica y caracteriza la "inversión de prioridad cross-DAG" como una deficiencia fundamental de los ejecutores actuales de ROS 2, demostrando cómo colapsan pipelines independientes en una cola FIFO sin garantías temporales.
Modelo de Interferencia Formal: Desarrolla un modelo matemático basado en la teoría Rate-Monotonic que deriva ecuaciones de tiempo de respuesta y condiciones de viabilidad para sistemas multi-DAG, cuantificando cómo ReDAGRT transforma la interferencia no acotada en una cantidad analizable.
Implementación y Validación de Código Abierto: Presenta ReDAGRT como un ejecutor de usuario que no requiere modificaciones del kernel ni de la API de ROS 2, validado empíricamente contra los ejecutores estándar bajo cargas de trabajo mixtas y de múltiples períodos.

4. Resultados Experimentales

Los experimentos se realizaron en un entorno ROS 2 Humble utilizando cargas de trabajo sintéticas multi-DAG. Los resultados comparativos muestran mejoras significativas:

Reducción de Fallos de Plazo: Se logró una reducción de hasta un 29.7% en la tasa combinada de fallos de plazo (miss rate) al escalar de 4 a 8 hilos, comparado con los ejecutores base.
Mejora en Tiempos de Respuesta:
- Reducción del 42.9% en el tiempo de respuesta del percentil 99 (de 49 ms a 28 ms), lo que indica una mayor predictibilidad y menor jitter.
- El tiempo de respuesta mediano disminuyó de 21 ms a 14 ms.
Comparativa con Ejecutores Base:
- ReDAGRT superó al MultiThreadedExecutor con una reducción del 13.7% en la tasa de fallos de plazo bajo utilidades comparables.
- Mostró un comportamiento de degradación "graceful" (suave) bajo alta carga, a diferencia del SingleThreadedExecutor, que sufrió aumentos catastróficos en la latencia (hasta 1.7 segundos de retraso máximo).
Efecto de Límites de Concurrencia: Las configuraciones asimétricas de límites de concurrencia (ej. 2 callbacks para un DAG y 5 para otro) redujeron la interferencia en un 40.8% en comparación con configuraciones simétricas, validando la importancia de controlar el "footprint" paralelo de cada DAG.

5. Significado e Impacto

ReDAGRT representa un avance fundamental para la robótica de tiempo real basada en ROS 2:

Determinismo en Espacio de Usuario: Demuestra que es posible lograr programación determinista y analizable para múltiples DAGs sin depender de parches del kernel de Linux o cambios en la API de ROS 2, facilitando su adopción en sistemas existentes.
Fundamento Teórico para CPS: Proporciona una base principista para el despliegue de sistemas ciberfísicos (CPS) de seguridad crítica, donde la predictibilidad temporal es obligatoria.
Resolución de Interferencia: Transforma un problema de contención no acotada en un problema de programación de prioridad fija resoluble, permitiendo a los ingenieros garantizar tiempos de respuesta y cumplir con plazos críticos en entornos de middleware compartidos.

En resumen, ReDAGRT cierra la brecha entre la flexibilidad de ROS 2 y los requisitos estrictos de los sistemas de tiempo real, ofreciendo una solución práctica, analizable y de alto rendimiento para la ejecución concurrente de pipelines robóticos complejos.