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

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

Licenças

Acesso aberto
Artigo: CC BY 4.0

Tudo o que segue se baseia no artigo completo sob a licença CC BY 4.0; sua figura é mostrada com crédito aos autores.

Em resumo

Simulações de três sistemas multirrobô mostram o desempenho se dividindo em execuções quase ótimas e quase nulas a partir de um tamanho crítico do enxame; um modelo de população liga isso a bifurcações e transientes longos.

Por que importa

Operadores que ajustam frotas ou enxames de robôs para a vazão máxima podem, sem saber, estar operando-os à beira de um colapso, e transientes longos podem fazer um sistema assim parecer saudável por algum tempo antes de colapsar. O modelo também prevê histerese, de modo que adicionar ou remover robôs durante a operação, como fazem alguns métodos de escalabilidade robusta, pode causar saltos bruscos de desempenho.

Problema

O desempenho de enxames costuma ser relatado como uma média em função da densidade do enxame, que sobe, atinge um pico em um tamanho crítico do sistema e depois cai. Essa média pode esconder um resultado bimodal no qual, perto do tamanho crítico, algumas execuções têm desempenho quase ótimo e outras colapsam em congestionamento, de modo que um sistema ajustado para o pico de desempenho médio pode estar perto do colapso.

Solução proposta

Os autores simulam três sistemas (um armazém de robôs de armazenamento AFLE suspensos em trilhos com mais de 3000 unidades, o agrupamento de objetos por enxame com o método lasso e a taxia emergente em direção a um farol luminoso) e traçam a distribuição completa do desempenho em função do tamanho do enxame, em vez da média. Em seguida modelam o efeito de duas formas: uma fila M/M/1 cujo tempo de serviço depende do comprimento da fila, e um modelo de população de três estados (solo, grupo, fermo) escrito como equações diferenciais ordinárias e analisado com ferramentas de dinâmica não linear.

Principais ideias

Perto do tamanho crítico do sistema, os resultados são bimodais: as execuções ou operam perto do desempenho máximo ou colapsam para um desempenho quase nulo, com quase nada no meio.
No modelo de população, uma bifurcação sela-nó significa que um único robô a mais pode levar o sistema de alta para baixa produtividade, e remover robôs só o traz de volta com um tamanho de enxame menor (histerese).
O tempo transiente cresce de forma superexponencial perto do estado crítico (desaceleração crítica), o que os autores atribuem a uma bifurcação cúspide de codimensão 2 no espaço de parâmetros (N, k1); um sistema pode, portanto, funcionar em “tempo emprestado” antes de colapsar.
Uma simples fila M/M/1 modificada já reproduz o aumento linear e o colapso a uma taxa de chegada crítica, e suas curvas se parecem com as do modelo de população.

Principais resultados

Armazém (96 repetições por taxa de chegada): a vazão cresceu linearmente com a taxa de chegada até cerca de 10⁴ AFLEs por hora, depois do que algumas execuções colapsaram em congestionamento com vazão quase nula enquanto outras permaneceram no máximo.
Agrupamento de objetos (1000 execuções por tamanho de enxame, de 1 a 20 robôs): melhor desempenho em torno de 6 robôs; a partir de 10 robôs os resultados se dividiram em execuções bem-sucedidas e malsucedidas.
Taxia emergente (800 execuções por tamanho de enxame, de 2 a 40 robôs, dados de trabalho anterior): velocidade máxima atingida em torno de 15 robôs, onde surgiu uma segunda fase, de baixa velocidade.
Fila M/M/1 modificada (taxa média de chegada de 0,4 a 0,9, 500 amostras cada): colapso a uma taxa média de chegada crítica de cerca de 0,65.
Modelo de população com as taxas padrão: o número de robôs solo atinge o pico em N = 31 e depois cai rapidamente; com k1 = 0,001, duas bifurcações sela-nó delimitam uma faixa biestável, e a Fig. 6 mostra o espaço de estados em N = 40, dentro dela.

Limitações

Os autores afirmam que continua em aberto qual modelo descreve melhor o desempenho em duas fases, e que pesquisas futuras precisam mostrar se o efeito é real e relevante em aplicações industriais.
Os três cenários são simulações; o modelo de armazém é um mundo em grade com tráfego de mão única e sem física, e os trechos de trilho de armazenamento não são modelados.
Os resultados de taxia emergente são reaproveitados de uma publicação anterior, em vez de executados novamente.
As constantes da fila são descritas como arbitrárias e diz-se que ambos os modelos capturam o comportamento qualitativamente; o artigo não os ajusta aos dados de simulação.

Impacto na área

Vencedor do IEEE ICRA 2024 Best Paper Award on Multi-Robot Systems, com 14 citações. O artigo traz link para o código aberto do seu simulador de agrupamento de objetos e para um vídeo; não menciona a liberação do simulador de armazém.

Resumo

Com um número crescente de robôs móveis chegando a aplicações do mundo real, mais robôs coexistem no mesmo espaço, interagem e possivelmente colaboram. Métodos para dotar esses sistemas de escalabilidade com o tamanho do sistema são conhecidos, por exemplo, da robótica de enxame. Exemplos de estratégias são o comportamento auto-organizado, uma abordagem estritamente descentralizada e a limitação da comunicação entre robôs. Mesmo com a aplicação dessas estratégias, qualquer sistema multirrobô entra em colapso acima de um certo tamanho crítico do sistema (ou seja, número de robôs), porque robôs demais compartilham um recurso (por exemplo, espaço, canal de comunicação). Fornecemos evidências adicionais, baseadas em simulações, de que nesses tamanhos críticos do sistema o desempenho se separa em duas fases: desempenho quase ótimo e desempenho mínimo. Especulamos que, em aplicações do mundo real configuradas para um tamanho de sistema ótimo, o sistema supostamente de alto desempenho pode na verdade estar vivendo de tempo emprestado, pois se encontra em um transiente rumo ao colapso. Apresentamos duas opções de modelagem (baseadas na teoria das filas e em um modelo de população) que podem ajudar a sustentar esse raciocínio.

Open Source Robotics