HULK: Large-scale Hierarchical Coordination under Continual and Uncertain Temporal Tasks

Resumen Técnico: HULK – Coordinación Jerárquica a Gran Escala bajo Tareas Temporales Continuas e Inciertas

Enunciado del Problema
El artículo aborda el desafío de coordinación en sistemas multiagente heterogéneos a gran escala que operan bajo tareas temporales continuas e inciertas. A diferencia de los enfoques tradicionales que asumen conjuntos de tareas estáticos y completamente conocidos, resolubles mediante programación entera fuera de línea, este trabajo considera escenarios donde:

1. Las tareas se generan en línea: Nuevas misiones se liberan o cancelan dinámicamente por demandas externas, requiriendo actualizaciones frecuentes de los planes.
2. Incertidumbre en las subtareas: La cantidad exacta de subtareas dentro de una misión y sus ubicaciones específicas a menudo son desconocidas en el momento de la liberación (por ejemplo, el número de víctimas en una zona de rescate o paquetes en un lote de entrega).
3. Restricciones de Lógica Temporal: Las tareas se especifican como fórmulas de Lógica Temporal Lineal co-segura sintáctica (sc-LTL) sobre acciones colaborativas, involucrando ordenamiento complejo, concurrencia y restricciones de recursos.

Los métodos centralizados existentes (por ejemplo, Programación Lineal Entera Mixta) se vuelven computacionalmente intratables cuando se aplican recursivamente a secuencias infinitas de tareas, mientras que los enfoques descentralizados ingenuos luchan por lograr consistencia y optimalidad globales.

Metodología: El Marco HULK
Los autores proponen HULK (Coordinación Jerárquica a Gran Escala bajo Tareas Temporales Continuas e Inciertas), un marco jerárquico que entrelaza la asignación global de tareas con la coordinación local de subtareas. La solución opera en dos capas distintas:

1. Asignación Global de Tareas con Horizonte Deslizante:

   • Descomposición: Las misiones en línea se descomponen en conjuntos parcialmente ordenados de tareas colaborativas (posets) basados en sus especificaciones sc-LTL.
   • Formación de Subequipos: En lugar de asignar agentes individuales a cada tarea, el algoritmo determina subequipos óptimos. Emplea un algoritmo basado en búsqueda para asignar secuencias de tareas a subequipos dentro de un horizonte finito ($H$), optimizando para restricciones de capacidad, costos de navegación y ordenamiento de tareas.
   • Asignación Consciente de Redundancia: Se utiliza un solver de Programación Lineal Entera Mixta (MILP) para mapear agentes específicos a los subequipos formados, minimizando el tiempo de inicio estimado para la primera tarea en la secuencia de cada subequipo.

2. Coordinación Local Dinámica de Subtareas:
   Una vez asignada una tarea a un subequipo, este ejecuta estrategias de coordinación local adaptadas a la naturaleza de las subtareas (que son inciertas en número y ubicación):

   • Estáticas y Conocidas: Si las ubicaciones y cantidades de las subtareas son conocidas (por ejemplo, entrega estándar), el problema se formula como un MILP para optimizar el enrutamiento y las acciones colaborativas.
   • Estáticas y Desconocidas: Si las ubicaciones/cantidades son desconocidas pero estáticas (por ejemplo, búsqueda y rescate), se utiliza un método de Exploración y Coordinación Simultánea (SEC). Los agentes exploran la región para detectar subtareas, seguidos por un algoritmo de asignación rodante para asignar las subtareas detectadas en lotes.
   • Dinámicas y Conocidas: Si las subtareas son móviles (por ejemplo, capturar objetivos en movimiento), se emplea una estrategia de Formación Dinámica de Coaliciones (DCF). Los agentes forman coaliciones para rodear objetivos, actualizando los esquemas de coalición a medida que se completan las subtareas.

Adaptación en Línea y Replanificación
El marco desencadena la replanificación (re-ejecución de la asignación global) basándose en condiciones específicas:

• Se completan más de la mitad de las tareas asignadas del horizonte.
• Se liberan nuevas misiones.
• La coordinación local para un subequipo devuelve una solución inviable.
  Crucialmente, las tareas que se están ejecutando actualmente no se interrumpen para garantizar la estabilidad.

Contribuciones Clave
El artículo reclama tres contribuciones principales:

1. Aplicabilidad: El algoritmo jerárquico soporta agentes heterogéneos, especificaciones de lógica temporal y acciones colaborativas.
2. Robustez: El sistema es robusto ante la liberación continua de tareas, fallos contingentes de agentes e incertidumbres en cantidades y ubicaciones de subtareas.
3. Escalabilidad y Eficiencia: El enfoque es computacionalmente eficiente, evitando la complejidad exponencial de la optimización global sobre todo el conjunto de tareas mediante el uso de un enfoque de horizonte deslizante y coordinación local.

Resultados Experimentales
El método se validó en simulación con una flota de 80 agentes heterogéneos (Tipos A, B y C) realizando 30 misiones que comprendían 492 subtareas.

• Rendimiento: El método propuesto logró una tasa de éxito del 100% con un tiempo de respuesta promedio de 62.7 segundos.
• Comparación: Comparado contra líneas base (C-MILP, planificadores basados en muestreo y enfoques codiciosos), HULK demostró tiempos de planificación significativamente menores (aproximadamente 50 veces más rápido que C-MILP-1) y tasas de éxito más altas.
• Escalabilidad: Las pruebas con tamaños de flota aumentados (hasta 150 agentes) y cantidades de tareas mostraron que el tiempo de planificación aumentó solo marginalmente (por ejemplo, de 1.6s a 1.8s en promedio), manteniendo una tasa de éxito del 100% incluso con una tasa de fallo de agentes del 5%.
• Eficiencia: El enfoque jerárquico redujo el tiempo máximo de planificación de niveles prohibitivos (>15 minutos para métodos de horizonte infinito) a menos de 5 segundos.

Significado
El artículo posiciona a HULK como una evolución necesaria para los sistemas multiagente que operan en entornos dinámicos del mundo real. Argumenta que las soluciones estáticas y fuera de línea son inadecuadas para flujos continuos de tareas con parámetros inciertos. Al desacoplar la asignación global de la ejecución local y manejar la incertidumbre mediante estrategias de coordinación especializadas, HULK permite que equipos a gran escala operen de manera eficiente y robusta sin requerir recomputación global constante. El trabajo destaca que la coordinación jerárquica es esencial para equilibrar la tratabilidad computacional con la necesidad de satisfacción global de misiones en dominios temporales inciertos.