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

Résumé technique : HULK – Coordination hiérarchique à grande échelle sous des tâches temporelles continues et incertaines

Énoncé du problème
L'article aborde le défi de la coordination dans des systèmes multi-agents hétérogènes à grande échelle opérant sous des tâches temporelles continues et incertaines. Contrairement aux approches traditionnelles qui supposent des ensembles de tâches statiques et entièrement connus, résolubles par programmation en nombres entiers hors ligne, ce travail considère des scénarios où :

1. Les tâches sont générées en ligne : De nouvelles missions sont lancées ou annulées dynamiquement par des demandes externes, nécessitant des mises à jour fréquentes des plans.
2. Incertitude des sous-tâches : Le nombre exact de sous-tâches au sein d'une mission et leurs emplacements spécifiques sont souvent inconnus au moment du lancement (par exemple, le nombre de victimes dans une zone de sauvetage ou de colis dans un lot de livraison).
3. Contraintes de logique temporelle : Les tâches sont spécifiées sous forme de formules de logique temporelle linéaire co-sûre syntaxique (sc-LTL) sur des actions collaboratives, impliquant des ordonnancements complexes, de la concurrence et des contraintes de ressources.

Les méthodes centralisées existantes (par exemple, la programmation linéaire en nombres entiers mixtes) deviennent computationnellement intraitables lorsqu'elles sont appliquées de manière récursive à des séquences infinies de tâches, tandis que les approches décentralisées naïves peinent à assurer la cohérence globale et l'optimalité.

Méthodologie : Le cadre HULK
Les auteurs proposent HULK (Coordination hiérarchique à grande échelle sous des tâches temporelles continues et incertaines), un cadre hiérarchique qui entrelace l'affectation globale des tâches avec la coordination locale des sous-tâches. La solution opère sur deux couches distinctes :

1. Affectation globale des tâches à horizon glissant :

   • Décomposition : Les missions en ligne sont décomposées en ensembles partiellement ordonnés de tâches collaboratives (posets) basés sur leurs spécifications sc-LTL.
   • Formation de sous-équipes : Au lieu d'affecter des agents individuels à chaque tâche, l'algorithme détermine les sous-équipes optimales. Il utilise un algorithme basé sur la recherche pour assigner des séquences de tâches à des sous-équipes dans un horizon fini ($H$), en optimisant les contraintes de capacité, les coûts de navigation et l'ordonnancement des tâches.
   • Allocation consciente de la redondance : Un solveur de programmation linéaire en nombres entiers mixtes (MILP) est utilisé pour mapper des agents spécifiques aux sous-équipes formées, en minimisant le temps de démarrage estimé pour la première tâche de la séquence de chaque sous-équipe.

2. Coordination dynamique locale des sous-tâches :
   Une fois qu'une sous-équipe se voit assigner une tâche, elle exécute des stratégies de coordination locales adaptées à la nature des sous-tâches (dont le nombre et l'emplacement sont incertains) :

   • Statique et connu : Si les emplacements et les nombres de sous-tâches sont connus (par exemple, une livraison standard), le problème est formulé comme un MILP pour optimiser le routage et les actions collaboratives.
   • Statique et inconnu : Si les emplacements/nombres sont inconnus mais statiques (par exemple, recherche et sauvetage), une méthode d'Exploration et Coordination Simultanées (SEC) est utilisée. Les agents explorent la région pour détecter les sous-tâches, suivis d'un algorithme d'attribution en roulement pour allouer les sous-tâches détectées par lots.
   • Dynamique et connu : Si les sous-tâches sont mobiles (par exemple, la capture de cibles en mouvement), une stratégie de Formation Dynamique de Coalitions (DCF) est employée. Les agents forment des coalitions pour encercler les cibles, mettant à jour les schémas de coalition au fur et à mesure que les sous-tâches sont accomplies.

Adaptation en ligne et replanification
Le cadre déclenche une replanification (réexécution de l'affectation globale) sur la base de conditions spécifiques :

• Plus de la moitié des tâches de l'horizon assigné sont terminées.
• De nouvelles missions sont lancées.
• La coordination locale d'une sous-équipe renvoie une solution non réalisable.
  Crucialement, les tâches actuellement en cours d'exécution ne sont pas préemptées afin d'assurer la stabilité.

Contributions clés
L'article revendique trois contributions principales :

1. Applicabilité : L'algorithme hiérarchique prend en charge des agents hétérogènes, des spécifications de logique temporelle et des actions collaboratives.
2. Robustesse : Le système est robuste face au lancement continu de tâches, aux défaillances contingentes des agents et aux incertitudes concernant les quantités et les emplacements des sous-tâches.
3. Évolutivité et efficacité : L'approche est computationnellement efficace, évitant la complexité exponentielle de l'optimisation globale sur l'ensemble des tâches en utilisant une approche à horizon glissant et une coordination locale.

Résultats expérimentaux
La méthode a été validée par simulation avec une flotte de 80 agents hétérogènes (types A, B et C) réalisant 30 missions comprenant 492 sous-tâches.

• Performance : La méthode proposée a atteint un taux de réussite de 100 % avec un temps de réponse moyen de 62,7 secondes.
• Comparaison : Par rapport aux références (C-MILP, planificateurs basés sur l'échantillonnage et approches gourmandes), HULK a démontré des temps de planification nettement inférieurs (environ 50 fois plus rapide que C-MILP-1) et des taux de réussite plus élevés.
• Évolutivité : Des tests avec des tailles de flotte accrues (jusqu'à 150 agents) et des nombres de tâches ont montré que le temps de planification n'augmentait que marginalement (par exemple, de 1,6 s à 1,8 s en moyenne), tout en maintenant un taux de réussite de 100 % même avec un taux de défaillance d'agents de 5 %.
• Efficacité : L'approche hiérarchique a réduit le temps de planification maximal de niveaux prohibitifs (>15 minutes pour les méthodes à horizon infini) à moins de 5 secondes.

Signification
L'article positionne HULK comme une évolution nécessaire pour les systèmes multi-agents opérant dans des environnements dynamiques réels. Il soutient que les solutions statiques et hors ligne sont inadéquates pour les flux continus de tâches présentant des paramètres incertains. En découplant l'affectation globale de l'exécution locale et en gérant l'incertitude grâce à des stratégies de coordination spécialisées, HULK permet à des équipes à grande échelle d'opérer efficacement et de manière robuste sans nécessiter de recomputation globale constante. Le travail met en évidence que la coordination hiérarchique est essentielle pour équilibrer la faisabilité computationnelle avec la nécessité de satisfaire les missions globales dans des domaines temporels incertains.