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）に従い論文全文に基づいています。図は著者のクレジットを付けて掲載しています。
要約
3 つのマルチロボットシステムのシミュレーションでは、臨界スワーム規模で性能がほぼ最適な試行とほぼゼロの試行に分かれる。個体群モデルはこれを分岐と長い過渡状態に結びつける。
重要な理由
ロボットのフリートやスワームをピークのスループットに合わせて調整する運用者は、知らないうちに破綻の瀬戸際で運用しているかもしれず、長い過渡状態のため、そうしたシステムは崩壊する前のしばらくの間は健全に見えることがある。モデルはヒステリシスも予測するため、一部の頑健なスケーラビリティ手法のように運用中にロボットを追加・削除すると、性能が急に跳ぶことがある。
課題
スワームの性能は通常、スワーム密度に対する平均として報告され、それは上昇して臨界システム規模でピークに達し、その後下降する。この平均は、臨界規模の近くで一部の試行はほぼ最適に動作し、他の試行は渋滞に陥って崩壊するという二峰性の結果を隠しうる。そのため、平均性能のピークに合わせて調整されたシステムは破綻の近くにある可能性がある。
提案手法
著者らは 3 つのシステム（3000 台を超えるレール吊り下げ式の AFLE 保管ロボットからなる倉庫、lasso 法によるスワームの物体クラスタリング、光ビーコンへ向かう創発的走性（emergent taxis））をシミュレーションし、平均ではなく、スワーム規模に対する性能の分布全体をプロットする。次にこの効果を 2 通りにモデル化する。サービス時間が待ち行列長に依存する M/M/1 待ち行列と、常微分方程式として記述し非線形力学の手法で解析する 3 状態の個体群モデル（solo、grupo、fermo）である。
主な知見
- 臨界システム規模の近くでは結果が二峰性になる。試行は最大性能付近で動作するか、ほぼゼロの性能へ崩壊するかのどちらかで、その中間はほとんどない。
- 個体群モデルではサドルノード分岐により、ロボットを 1 台追加するだけでシステムが高い生産性から低い生産性へ切り替わりうる。ロボットを減らしても、元に戻るのはより小さなスワーム規模になってからである（ヒステリシス）。
- 臨界状態の近くでは過渡時間が指数関数を超えて増大し（臨界減速）、著者らはこれを (N, k1) パラメータ空間における余次元 2 のカスプ分岐に帰している。そのためシステムは破綻する前に「借りた時間」の上で動作しうる。
- 単純な修正版 M/M/1 待ち行列でも、線形の増加と臨界到着率での破綻がすでに再現され、その曲線は個体群モデルの曲線に似ている。
主な結果
- 倉庫（到着率ごとに 96 回の反復）：スループットは毎時約 10⁴ 個の AFLE まで到着率に比例して上昇し、その後は一部の試行が渋滞に陥ってスループットがほぼゼロになる一方、他の試行は最大のままだった。
- 物体クラスタリング（スワーム規模ごとに 1000 回の試行、ロボット 1 から 20 台）：最良の性能は約 6 台。10 台以上では結果が成功した試行と失敗した試行に分かれた。
- 創発的走性（スワーム規模ごとに 800 回の試行、ロボット 2 から 40 台、データは以前の研究から）：約 15 台で最高速度に達し、そこで 2 つ目の低速の相が現れた。
- 修正版 M/M/1 待ち行列（平均到着率 0.4 から 0.9、それぞれ 500 サンプル）：約 0.65 の臨界平均到着率で破綻した。
- デフォルトのレートを用いた個体群モデル：solo のロボット数は N = 31 でピークに達した後、急速に減少する。k1 = 0.001 では 2 つのサドルノード分岐が双安定な範囲を区切り、図 6 はその内側の N = 40 での状態空間を示している。
制限事項
- 著者らは、どのモデルが 2 相の性能を最もよく記述するかは未解決であり、この効果が産業応用で実在し意味をもつかどうかは今後の研究で示す必要があると述べている。
- 3 つのシナリオはすべてシミュレーションである。倉庫モデルは一方通行で物理のないグリッドワールドで、保管レールの区間はモデル化されていない。
- 創発的走性の結果は、新たに実行したものではなく以前の論文から再利用したものである。
- 待ち行列の定数は任意のものと説明され、両モデルとも挙動を定性的に捉えるだけとされている。論文はそれらをシミュレーションデータにフィッティングしていない。
分野への影響
IEEE ICRA 2024 Best Paper Award on Multi-Robot Systems を受賞し、被引用数は 14。論文は物体クラスタリングのシミュレータのオープンソースコードと動画へリンクしている。倉庫シミュレータの公開については触れていない。
概要
実世界の応用に到来する移動ロボットの数が増えるにつれ、より多くのロボットが同じ空間に共存し、相互作用し、場合によっては協調する。こうしたシステムにシステム規模のスケーラビリティを与える方法は、例えば群ロボット工学から知られている。戦略の例としては、自己組織的な振る舞い、厳密な分散型アプローチ、ロボット間通信の制限がある。こうした戦略を適用しても、あまりに多くのロボットが資源（例えば空間や通信チャネル）を共有するため、どのマルチロボットシステムもある臨界システム規模（すなわちロボット数）を超えると破綻する。我々はシミュレーションに基づき、これらの臨界システム規模においてシステム性能がほぼ最適な性能と最小の性能という 2 つの相に分かれるという追加の証拠を示す。最適なシステム規模に設定された実世界の応用では、高性能と思われるシステムが実は破綻へ向かう過渡状態にあり、借りた時間の上で生きているにすぎないのではないかと我々は推測する。この推論を裏付けるのに役立つかもしれない 2 つのモデル化の選択肢（待ち行列理論に基づくものと個体群モデルに基づくもの）を示す。
リンク
- 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