Resumen Técnico: Optimización de Colonia de Hormigas de Doble Capa para la Asignación de Tareas y el Enrutamiento de Multi-Robots

Definición del Problema

El artículo aborda el problema de la Asignación de Tareas de Multi-Robots (MRTA, por sus siglas en inglés) en el contexto de aplicaciones de entrega y logística. El desafío central consiste en coordinar una flota de robots móviles para ejecutar un conjunto de tareas de entrega, donde cada tarea consiste en una ubicación de recogida específica y una ubicación de entrega.

El problema de optimización se define como un proceso de decisión acoplado que requiere dos salidas simultáneas:

1. Asignación de Tareas: Determinar qué robot realiza cada tarea específica.
2. Secuenciación de Tareas: Determinar el orden óptimo en el que un robot ejecuta sus tareas asignadas.

El objetivo es minimizar la distancia total de viaje de toda la flota asegurando que cada tarea sea ejecutada exactamente una vez por un solo robot. Los autores señalan que los enfoques existentes suelen tratar la asignación, la secuenciación y la ejecución como etapas independientes optimizadas por separado. Esta separación puede conducir a una coordinación global subóptima, movimiento redundante y una reducción de la eficiencia del sistema. El artículo formula el MRTA como un problema de optimización unificado donde las decisiones de asignación y secuenciación son interdependientes.

Metodología: Optimización de Colonia de Hormigas de Doble Capa (ACO)

Para resolver el problema de optimización formulado, los autores proponen un algoritmo de Optimización de Colonia de Hormigas de Doble Capa (Bi-Layer ACO). A diferencia de los métodos jerárquicos tradicionales que resuelven las capas secuencialmente, este enfoque integra dos capas de decisión interdependientes en un único proceso de colonia.

Marco Central

El algoritmo emplea una metaheurística basada en la población inspirada en el comportamiento de forrajeo de las hormigas. Cada "hormiga" en la colonia construye una solución completa navegando simultáneamente a través de dos capas de decisión:

1. Capa de Asignación de Tareas:

   • Determina la asignación de tareas a los robots ($x_{i,j}$).
   • Utiliza una matriz de feromonas $\tau_{assign} \in \mathbb{R}^{m \times n}$ (tareas $\times$ robots) que representa la deseabilidad aprendida de asignar la tarea $j$ al robot $i$.
   • La información heurística ($\eta_{assign}$) se deriva del inverso de la distancia entre la posición inicial del robot y la ubicación de recogida de la tarea.

2. Capa de Secuenciación de Tareas:

   • Determina el orden de visita ($\pi_i$) para las tareas asignadas a cada robot.
   • Utiliza una matriz de feromonas $\tau_{seq} \in \mathbb{R}^{m \times m}$ que representa la deseabilidad de la transición de la tarea $j$ a la tarea $k$ dentro de la ruta del mismo robot.
   • La información heurística ($\eta_{seq}$) se deriva del inverso de la distancia entre la entrega de la tarea actual y la recogida de la siguiente tarea.

Ejecución del Algoritmo

El algoritmo procede a través de ciclos iterativos:

1. Construcción: Cada hormiga asigna probabilísticamente las tareas a los robots basándose en los valores de feromona y heurística de la capa de asignación. Una vez realizadas las asignaciones, la capa de secuenciación construye la ruta para cada robot. La primera tarea se selecciona basándose en la proximidad al inicio del robot, y las tareas subsiguientes se muestrean basándose en la feromona de secuenciación y los valores heurísticos.
2. Evaluación: Se calcula la distancia total de viaje para la solución construida, sumando las distancias de todos los robots (inicio-a-recogida, recogida-a-entrega, y entrega-a-siguiente-recogida).
3. Actualización de Feromonas: Después de que todas las hormigas construyen sus soluciones, los rastros de feromona en ambas matrices se actualizan. Esto implica:
   • Evaporación: Reducción de los niveles de feromona existentes para prevenir el estancamiento.
   • Refuerzo: Depósito de nueva feromona proporcional a la calidad de la solución ($Q/C(a)$), donde las mejores soluciones (menor costo) depositan más feromona. Las ecuaciones de actualización aseguran que tanto las parejas de asignación como las transiciones de tareas específicas en la ruta sean reforzadas.

Contribuciones Clave

El artículo identifica las siguientes contribuciones primarias:

• Función Objetivo Unificada: La formulación de una nueva función de costo que transforma el MRTA en un problema de optimización acoplado, capturando explícitamente la interdependencia entre la distribución global de tareas y la planificación de rutas locales.
• Arquitectura ACO de Doble Capa: La introducción de un nuevo marco algorítmico que integra la asignación y la secuenciación en un solo proceso de colonia utilizando dos matrices de feromona distintas e interconectadas. Esto permite la optimización simultánea de la asignación de tareas y la planificación de rutas.
• Validación del Desempeño: Experimentos comparativos exhaustivos que demuestran la eficacia del método propuesto frente a la Programación Lineal Entera Mixta (MILP) y la Optimización por Enjambre de Partículas (PSO).

Resultados Experimentales

El método propuesto fue evaluado en un entorno de simulación ROS 2 Humble y Gazebo utilizando tres robots TurtleBot3. Los experimentos se realizaron en tres escenarios con 5, 10 y 20 tareas.

Métricas de Desempeño:

• Distancia Total de Viaje: El Bi-Layer ACO logró consistentemente la menor distancia media total de viaje en todos los tamaños de tareas.
  • Comparado con MILP, el ACO redujo la distancia total aproximadamente un 17.7% (con 5 tareas).
  • Comparado con PSO, el ACO redujo la distancia total aproximadamente un 9.8%.
• Tiempo de Finalización: El método propuesto también demostró tiempos de finalización de tareas más rápidos.
  • Comparado con los métodos base, el ACO redujo el tiempo de finalización casi un 20%.
• Estabilidad y Escalabilidad:
  • El ACO exhibió desviaciones estándar más bajas tanto en distancia como en tiempo en comparación con PSO y MILP, lo que indica una convergencia más estable.
  • A medida que la complejidad de las tareas aumentó (hasta 20 tareas), el ACO mantuvo un desempeño superior, mientras que MILP y PSO mostraron una mayor dispersión y costos más altos.

Significación y Reivindicaciones

El artículo afirma que el marco de trabajo Bi-Layer ACO aborda eficazmente la limitación de separar la asignación de tareas y el enrutamiento en los enfoques de MRTA existentes. Al optimizar estas decisiones de forma conjunta, el método reduce el movimiento redundante y mejora la eficiencia general de la misión.

Los autores concluyen que el Bi-Layer ACO es una solución escalable y confiable para tareas de entrega multi-robot, ofreciendo un equilibrio entre exploración y explotación que produce rutas más cortas y consistentes que los métodos exactos tradicionales (MILP) u otras metaheurísticas (PSO). El trabajo sugiere que este enfoque unificado es particularmente valioso para mejorar la eficiencia de los sistemas de logística y entrega del mundo real. Se señala como trabajo futuro la extensión del enfoque a entornos dinámicos, flotas de robots heterogéneas y restricciones de comunicación.