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

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

Licenze

• Open access
• Articolo: CC BY 4.0

Tutto ciò che segue si basa sull'articolo completo secondo la sua licenza CC BY 4.0; la figura è riportata citando gli autori.

In breve

Le simulazioni di tre sistemi multi-robot mostrano le prestazioni che si dividono in esecuzioni quasi ottimali e quasi nulle oltre una dimensione critica dello sciame; un modello di popolazione collega il fenomeno a biforcazioni e transitori lunghi.

Perché è importante

Chi regola flotte o sciami di robot per il massimo throughput può, senza saperlo, farli funzionare al limite di un collasso, e transitori lunghi possono far sembrare sano un tale sistema per un certo tempo prima che collassi. Il modello prevede anche un'isteresi, per cui aggiungere o togliere robot durante il funzionamento, come fanno alcuni metodi di scalabilità robusta, può causare salti improvvisi delle prestazioni.

Problema

Le prestazioni di uno sciame sono di solito riportate come media in funzione della densità dello sciame, che sale, raggiunge un picco a una dimensione critica del sistema e poi scende. Tale media può nascondere un esito bimodale in cui, vicino alla dimensione critica, alcune esecuzioni hanno prestazioni quasi ottimali e altre collassano per congestione, per cui un sistema regolato per il picco delle prestazioni medie può trovarsi vicino al collasso.

Soluzione proposta

Gli autori simulano tre sistemi (un magazzino di robot di stoccaggio AFLE sospesi su rotaie con oltre 3000 unità, il raggruppamento di oggetti da parte di uno sciame con il metodo lasso e la tassia emergente verso un faro luminoso) e rappresentano l'intera distribuzione delle prestazioni in funzione della dimensione dello sciame invece della media. Modellano poi l'effetto in due modi: una coda M/M/1 il cui tempo di servizio dipende dalla lunghezza della coda, e un modello di popolazione a tre stati (solo, grupo, fermo) scritto come equazioni differenziali ordinarie e analizzato con gli strumenti della dinamica non lineare.

Idee chiave

• Vicino alla dimensione critica del sistema gli esiti sono bimodali: le esecuzioni o operano vicino alle prestazioni massime o collassano a prestazioni quasi nulle, con quasi nulla nel mezzo.
• Nel modello di popolazione una biforcazione sella-nodo implica che un solo robot in più può portare il sistema da alta a bassa produttività, e togliere robot lo riporta indietro solo a una dimensione dello sciame minore (isteresi).
• Il tempo di transitorio cresce in modo sovraesponenziale vicino allo stato critico (rallentamento critico), cosa che gli autori riconducono a una biforcazione a cuspide di codimensione 2 nello spazio dei parametri (N, k1); un sistema può quindi funzionare con «tempo preso in prestito» prima di collassare.
• Una semplice coda M/M/1 modificata riproduce già l'aumento lineare e il collasso a un tasso di arrivo critico, e le sue curve somigliano a quelle del modello di popolazione.

Risultati principali

• Magazzino (96 ripetizioni per tasso di arrivo): il throughput è cresciuto linearmente con il tasso di arrivo fino a circa 10⁴ AFLE all'ora, dopodiché alcune esecuzioni sono collassate per congestione con throughput quasi nullo mentre altre sono rimaste al massimo.
• Raggruppamento di oggetti (1000 esecuzioni per dimensione dello sciame, da 1 a 20 robot): prestazioni migliori intorno a 6 robot; da 10 robot in su i risultati si sono divisi in esecuzioni riuscite e non riuscite.
• Tassia emergente (800 esecuzioni per dimensione dello sciame, da 2 a 40 robot, dati da un lavoro precedente): velocità massima raggiunta intorno a 15 robot, dove è comparsa una seconda fase a bassa velocità.
• Coda M/M/1 modificata (tasso medio di arrivo da 0,4 a 0,9, 500 campioni ciascuno): collasso a un tasso medio di arrivo critico di circa 0,65.
• Modello di popolazione con i tassi predefiniti: il numero di robot solo raggiunge il picco a N = 31 e poi cala rapidamente; con k1 = 0,001 due biforcazioni sella-nodo delimitano un intervallo bistabile, e la Fig. 6 mostra lo spazio degli stati a N = 40, al suo interno.

Limiti

• Gli autori affermano che resta aperto quale modello descriva meglio le prestazioni a due fasi, e che la ricerca futura deve mostrare se l'effetto sia reale e rilevante nelle applicazioni industriali.
• Tutti e tre gli scenari sono simulazioni; il modello di magazzino è un mondo a griglia con traffico a senso unico e senza fisica, e le sezioni di rotaia di stoccaggio non sono modellate.
• I risultati sulla tassia emergente sono ripresi da una pubblicazione precedente invece di essere rieseguiti.
• Le costanti della coda sono descritte come arbitrarie e si afferma che entrambi i modelli colgono il comportamento in modo qualitativo; l'articolo non li adatta ai dati di simulazione.

Impatto sul settore

Vincitore dell'IEEE ICRA 2024 Best Paper Award on Multi-Robot Systems, con 14 citazioni. L'articolo rimanda al codice open source del suo simulatore di raggruppamento di oggetti e a un video; non si menziona il rilascio del simulatore di magazzino.

Abstract

Con un numero crescente di robot mobili che arrivano nelle applicazioni del mondo reale, più robot coesistono nello stesso spazio, interagiscono e possibilmente collaborano. Metodi per dotare tali sistemi di scalabilità rispetto alla dimensione del sistema sono noti, ad esempio, dalla robotica degli sciami. Strategie esemplificative sono il comportamento auto-organizzato, un approccio rigorosamente decentralizzato e la limitazione della comunicazione tra robot. Pur applicando tali strategie, qualsiasi sistema multi-robot si rompe al di sopra di una certa dimensione critica del sistema (ovvero, numero di robot), poiché troppi robot condividono una risorsa (ad es. spazio, canale di comunicazione). Forniamo ulteriori prove, basate su simulazioni, che a queste dimensioni critiche del sistema le prestazioni si separano in due fasi: prestazioni quasi ottimali e prestazioni minime. Ipotizziamo che, nelle applicazioni reali configurate per una dimensione ottimale del sistema, il sistema apparentemente ad alte prestazioni possa in realtà vivere di tempo preso in prestito, poiché si trova in un transitorio verso il collasso. Proponiamo due opzioni di modellazione (basate sulla teoria delle code e su un modello di popolazione) che possono aiutare a sostenere questo ragionamento.

Link

• 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
• Codice: https://github.com/avardy/cwaggle_lasso