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

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

라이선스

• 오픈 액세스
• 논문: CC BY 4.0

아래 내용은 모두 논문의 라이선스(CC BY 4.0)에 따라 논문 전문을 바탕으로 하며, 그림에는 저자를 표기했습니다.

요약

세 가지 다중 로봇 시스템의 시뮬레이션은 임계 군집 크기에서 성능이 거의 최적인 실행과 거의 0인 실행으로 갈라짐을 보여 준다. 개체군 모델은 이를 분기와 긴 과도 상태에 연결한다.

중요한 이유

최대 처리량을 위해 로봇 플릿이나 군집을 조정하는 운영자는 자신도 모르게 붕괴 직전의 경계에서 이를 운영하고 있을 수 있으며, 긴 과도 상태 때문에 그런 시스템이 붕괴하기 전 한동안 건강해 보일 수 있다. 모델은 또한 히스테리시스를 예측하므로, 일부 강건 확장성 방법이 하듯 운영 중에 로봇을 추가하거나 제거하면 성능이 갑자기 뛸 수 있다.

문제

군집 성능은 보통 군집 밀도에 대한 평균으로 보고되며, 이 평균은 증가하다가 임계 시스템 규모에서 정점을 찍은 뒤 감소한다. 이 평균은 쌍봉형 결과를 가릴 수 있다. 임계 규모 근처에서 일부 실행은 거의 최적으로 작동하고 다른 실행은 혼잡 상태로 붕괴하므로, 최대 평균 성능에 맞춰 조정된 시스템은 붕괴에 가까이 놓여 있을 수 있다.

제안 방법

저자들은 세 가지 시스템(3000대가 넘는 레일 현수식 AFLE 저장 로봇의 창고, lasso 방법을 사용한 군집 물체 군집화, 빛 비콘을 향한 창발적 주성)을 시뮬레이션하고, 평균 대신 군집 크기에 따른 성능의 전체 분포를 그린다. 이어서 이 효과를 두 가지 방식으로 모델링한다. 서비스 시간이 대기열 길이에 의존하는 M/M/1 대기열, 그리고 상미분 방정식으로 쓰고 비선형 동역학 도구로 분석한 3상태 개체군 모델(solo, grupo, fermo)이다.

핵심 통찰

• 임계 시스템 규모 근처에서 결과는 쌍봉형이다. 실행은 최대 성능 근처에서 작동하거나 거의 0인 성능으로 붕괴하며, 그 사이는 거의 없다.
• 개체군 모델에서 안장-마디 분기는 로봇 한 대를 추가하는 것만으로 시스템이 높은 생산성에서 낮은 생산성으로 전환될 수 있음을 뜻하며, 로봇을 제거해도 더 작은 군집 크기에서야 다시 돌아간다(히스테리시스).
• 과도 시간은 임계 상태 근처에서 지수보다 빠르게 증가하며(임계 감속), 저자들은 이를 (N, k1) 매개변수 공간의 여차원 2 첨점 분기로 추적한다. 따라서 시스템은 붕괴하기 전까지 '빌린 시간' 위에서 작동할 수 있다.
• 단순한 수정 M/M/1 대기열만으로도 선형 증가와 임계 도착률에서의 붕괴가 재현되며, 그 곡선은 개체군 모델의 곡선과 닮았다.

주요 결과

• 창고(도착률당 96회 반복): 처리량은 시간당 약 10⁴ AFLE까지 도착률에 따라 선형으로 증가했으며, 그 이후 일부 실행은 처리량이 거의 0인 혼잡 상태로 붕괴한 반면 다른 실행은 최대에 머물렀다.
• 물체 군집화(군집 크기당 1000회 실행, 로봇 1~20대): 최고 성능은 로봇 6대 부근이었고, 로봇 10대부터는 결과가 성공한 실행과 실패한 실행으로 갈라졌다.
• 창발적 주성(군집 크기당 800회 실행, 로봇 2~40대, 이전 연구의 데이터): 최대 속도는 로봇 15대 부근에서 도달했으며, 그 지점에서 두 번째 저속 위상이 나타났다.
• 수정 M/M/1 대기열(평균 도착률 0.4~0.9, 각 500개 샘플): 붕괴는 약 0.65의 임계 평균 도착률에서 일어났다.
• 기본 비율을 쓴 개체군 모델: solo 로봇 수는 N = 31에서 정점을 찍은 뒤 빠르게 감소한다. k1 = 0.001일 때 두 개의 안장-마디 분기가 쌍안정 범위의 경계를 이루며, Fig. 6은 그 범위 안의 N = 40에서의 상태 공간을 보여 준다.

한계

• 저자들은 어떤 모델이 두 위상 성능을 가장 잘 설명하는지는 아직 열려 있으며, 이 효과가 실제로 존재하고 산업 응용에서 의미가 있는지는 향후 연구가 보여 주어야 한다고 말한다.
• 세 시나리오 모두 시뮬레이션이다. 창고 모델은 일방통행이 있고 물리가 없는 그리드 세계이며, 저장 레일 구간은 모델링되지 않는다.
• 창발적 주성 결과는 새로 실행한 것이 아니라 이전 출판물에서 재사용한 것이다.
• 대기열 상수는 임의적이라고 기술되며, 두 모델 모두 행동을 정성적으로 포착한다고 한다. 논문은 이를 시뮬레이션 데이터에 맞추지 않는다.

분야에 미친 영향

IEEE ICRA 2024 Best Paper Award on Multi-Robot Systems 수상작이며 인용 수는 14회다. 논문은 물체 군집화 시뮬레이터의 오픈 소스 코드와 영상을 링크한다. 창고 시뮬레이터의 공개는 언급되지 않는다.

초록

실제 응용에 투입되는 이동 로봇의 수가 늘어남에 따라, 더 많은 로봇이 같은 공간에 공존하고 상호작용하며 경우에 따라 협력한다. 이러한 시스템에 시스템 규모 확장성을 제공하는 방법은 예를 들어 군집 로봇공학에서 알려져 있다. 예시 전략으로는 자기 조직화 행동, 엄격한 분산 접근법, 로봇 간 통신 제한이 있다. 이러한 전략을 적용하더라도, 너무 많은 로봇이 자원(예: 공간, 통신 채널)을 공유하게 되므로 모든 다중 로봇 시스템은 특정 임계 시스템 규모(즉, 로봇 수)를 넘으면 무너진다. 우리는 시뮬레이션에 기반해, 이러한 임계 시스템 규모에서 시스템 성능이 거의 최적 성능과 최소 성능이라는 두 위상으로 갈라진다는 추가 증거를 제시한다. 우리는 최적 시스템 규모에 맞춰 구성된 실제 응용에서, 고성능으로 여겨지는 시스템이 붕괴로 향하는 과도 상태에 있기 때문에 실제로는 빌린 시간 위에서 살고 있을 수 있다고 추측한다. 우리는 이러한 추론을 뒷받침하는 데 도움이 될 수 있는 두 가지 모델링 선택지(대기행렬 이론과 개체군 모델에 기반한)를 제시한다.

링크

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