Do We Run Large-Scale Multi-Robot Systems on the Edge? More Evidence for Two-Phase Performance in System Size Scaling

Auteurs: Jonas Kuckling, Robin Luckey, Viktor Avrutin, Andrew Vardy, Andreagiovanni Reina, Heiko Hamann · ICRA 2024

Licences

• Accès libre
• Article: CC BY 4.0

Tout ce qui suit s'appuie sur l'article complet sous sa licence CC BY 4.0 ; sa figure est montrée en citant les auteurs.

En bref

Des simulations de trois systèmes multi-robots montrent que la performance se scinde, à une taille d'essaim critique, en exécutions quasi optimales et quasi nulles ; un modèle de population relie cela à des bifurcations et à de longs régimes transitoires.

Pourquoi c'est important

Les opérateurs qui règlent des flottes ou des essaims de robots pour un débit maximal pourraient, sans le savoir, les faire fonctionner au bord de l'effondrement, et de longs régimes transitoires peuvent faire paraître un tel système sain pendant un temps avant qu'il ne s'effondre. Le modèle prédit aussi une hystérésis, de sorte qu'ajouter ou retirer des robots en cours de fonctionnement, comme le font certaines méthodes de scalabilité robuste, peut provoquer des sauts soudains de performance.

Problème

La performance d'un essaim est généralement présentée comme une moyenne en fonction de la densité de l'essaim, qui augmente, atteint un pic à une taille critique de système, puis diminue. Cette moyenne peut masquer un résultat bimodal dans lequel, près de la taille critique, certaines exécutions sont presque optimales et d'autres s'effondrent dans la congestion, de sorte qu'un système réglé pour une performance moyenne maximale peut se trouver proche de l'effondrement.

Solution proposée

Les auteurs simulent trois systèmes (un entrepôt de robots de stockage AFLE suspendus à des rails, avec plus de 3000 unités, le regroupement d'objets en essaim avec la méthode lasso, et une taxie émergente vers une balise lumineuse) et tracent la distribution complète de la performance en fonction de la taille de l'essaim au lieu de la moyenne. Ils modélisent ensuite l'effet de deux façons : une file d'attente M/M/1 dont le temps de service dépend de la longueur de la file, et un modèle de population à trois états (solo, grupo, fermo) écrit sous forme d'équations différentielles ordinaires et analysé avec les outils de la dynamique non linéaire.

Idées clés

• Près de la taille critique du système, les résultats sont bimodaux : les exécutions fonctionnent soit près de la performance maximale, soit s'effondrent à une performance quasi nulle, avec presque rien entre les deux.
• Dans le modèle de population, une bifurcation nœud-col signifie qu'un robot ajouté peut faire basculer le système d'une productivité élevée à une productivité faible, et que retirer des robots ne le fait revenir qu'à une taille d'essaim plus petite (hystérésis).
• Le temps transitoire croît de façon sur-exponentielle près de l'état critique (ralentissement critique), ce que les auteurs rattachent à une bifurcation fronce de codimension 2 dans l'espace des paramètres (N, k1) ; un système peut donc fonctionner en « sursis » avant de s'effondrer.
• Une simple file d'attente M/M/1 modifiée reproduit déjà l'augmentation linéaire et l'effondrement à un taux d'arrivée critique, et ses courbes ressemblent à celles du modèle de population.

Principaux résultats

• Entrepôt (96 répétitions par taux d'arrivée) : le débit a augmenté linéairement avec le taux d'arrivée jusqu'à environ 10⁴ AFLE par heure, après quoi certaines exécutions se sont effondrées dans une congestion à débit quasi nul tandis que d'autres sont restées au maximum.
• Regroupement d'objets (1000 exécutions par taille d'essaim, de 1 à 20 robots) : meilleure performance autour de 6 robots ; à partir de 10 robots, les résultats se sont scindés en exécutions réussies et non réussies.
• Taxie émergente (800 exécutions par taille d'essaim, de 2 à 40 robots, données issues de travaux antérieurs) : vitesse maximale atteinte vers 15 robots, où une seconde phase à faible vitesse est apparue.
• File M/M/1 modifiée (taux d'arrivée moyen de 0,4 à 0,9, 500 échantillons chacun) : effondrement à un taux d'arrivée moyen critique d'environ 0,65.
• Modèle de population avec les taux par défaut : le nombre de robots solo culmine à N = 31 puis chute rapidement ; avec k1 = 0,001, deux bifurcations nœud-col délimitent une plage bistable, et la Fig. 6 montre l'espace d'états à N = 40 à l'intérieur de celle-ci.

Limites

• Les auteurs indiquent que la question de savoir quel modèle décrit le mieux la performance à deux phases reste ouverte, et que des recherches futures devront montrer si l'effet est réel et pertinent dans les applications industrielles.
• Les trois scénarios sont des simulations ; le modèle d'entrepôt est un monde en grille avec une circulation à sens unique et sans physique, et les sections de rails de stockage ne sont pas modélisées.
• Les résultats de taxie émergente sont repris d'une publication antérieure plutôt que réexécutés.
• Les constantes de la file d'attente sont décrites comme arbitraires et les deux modèles sont présentés comme capturant le comportement qualitativement ; l'article ne les ajuste pas aux données de simulation.

Impact sur le domaine

Lauréat du prix IEEE ICRA 2024 Best Paper Award on Multi-Robot Systems, avec 14 citations. L'article renvoie au code open source de son simulateur de regroupement d'objets et à une vidéo ; aucune publication du simulateur d'entrepôt n'est mentionnée.

Résumé

Avec le nombre croissant de robots mobiles qui arrivent dans des applications réelles, davantage de robots coexistent dans le même espace, interagissent et collaborent éventuellement. Des méthodes pour doter de tels systèmes d'une scalabilité en taille de système sont connues, par exemple, de la robotique en essaim. Des exemples de stratégies sont le comportement auto-organisé, une approche strictement décentralisée et la limitation de la communication entre robots. Malgré l'application de telles stratégies, tout système multi-robots s'effondre au-delà d'une certaine taille critique de système (c'est-à-dire de nombre de robots), car trop de robots partagent une ressource (par exemple l'espace, un canal de communication). Nous apportons, sur la base de simulations, des éléments supplémentaires montrant qu'à ces tailles critiques de système, la performance du système se sépare en deux phases : une performance presque optimale et une performance minimale. Nous conjecturons que dans des applications réelles configurées pour une taille de système optimale, le système supposément très performant pourrait en réalité vivre en sursis, car il se trouve dans un régime transitoire vers l'effondrement. Nous proposons deux options de modélisation (fondées sur la théorie des files d'attente et sur un modèle de population) qui pourraient aider à étayer ce raisonnement.

Liens

• arXiv 2310.11843: https://arxiv.org/abs/2310.11843
• DOI 10.1109/ICRA57147.2024.10610771: https://doi.org/10.1109/ICRA57147.2024.10610771
• PDF: https://arxiv.org/pdf/2310.11843v1
• Code: https://github.com/avardy/cwaggle_lasso