ロボティクス · 倉庫のロボット群(Goods-to-Person方式)

ロボットを減らし、処理量を増やす

数百台の倉庫ロボットの走行を、ブラウザ上でリアルタイムに計画します。ロボットを増やすと処理量が落ち始める台数を見つけてください。

ライブで試す

01

概要

Goods-to-Person方式の倉庫ロボット向けの走行プランナーで、ブラウザ上で動作します。グリッド上を動く最大400台の模擬ロボットに、新しいタスクが絶えず割り当てられます。保管棚(ポッド)を取りに行き、16か所のピックステーションのいずれかへ運び、ピッキングが終わるのを待って、次のポッドを取りに行く、という流れです。構造上、衝突は起こらず、乱数シードを固定した4,775回の試行でデッドロックは発生しませんでした。処理量が伸びなくなるまでロボットを追加したら、通路を一方通行に塗り分けてみてください。プランナーはこれを強制ではなく重みとして扱います。曲線の頂点がどう動くかを見てください。

私たちのフロアモデルでは、このプランナーと平均6秒のピック時間で、処理量は毎時約5,134回のポッド提示で頭打ちになります。頂点は平らで、196台から235台のどこでも最良値の0.5%以内に収まり、平滑化曲線のピークは214台です。それを超えると、ロボットを増やすほど処理量は減り、その減り方も加速します。頂点を過ぎた直後はロボットが増えるごとに毎時約1回、250台付近では約4回、400台近くでは約7回ずつ減ります。400台では最良時より20.5%少なくなり、移動中のロボットの48%が、8秒前より目的地に近づいていません。

通路を規則ではなく推奨として一方通行に塗り分けると、同じフロアの処理量は191台で毎時6,439回のポッド提示に達します。ロボットを23台減らして、処理量は25.4%増えます。比較の基準は一車線の通路での双方向通行で、実際のレイアウトでは避けられる構成なので、改善が出るのは想定どおりです。興味深いのは、その効果がどこで止まるかです。ピッキングがポッド一つあたり24秒まで遅くなると、ステーションが上限を決めるようになり、塗り分けによる処理量の変化は増減いずれの方向にも最大2.5%にとどまります。

これらの数値は、このプランナーを使ったグリッドモデルでの結果です。ロボットは全台が同じ刻みで、毎秒1 mのセルを一つずつ進みます。前のロボットにぴったり続いて動くことができ、加速や旋回にかかる時間はありません。保管ブロックは通り抜けられない塊として扱い(ロボットが棚の下をくぐることはありません)、ポッドの返却は次の取り出しに含め、ステーションには待機レーンがありません。最良の台数でのフロアの占有率は約40%で、実際のロボット群の運用よりはるかに高密度です。これらの数値は、この「ぴったり続く」動きを前提にしています。車間を空ける版のプランナー(あるロボットがセルを離れるのと同じ秒に、別のロボットがそのセルに入ることを禁止)では、試した中で最良の台数は80台・毎時約1,880回で、160台までに全体が膠着しました(各点で乱数シードを固定した10回の試行)。実際のロボット群はもっと早く渋滞し、別のプランナーなら頂点の位置も変わります。

02

開発内容

  • PIBT(priority inheritance with backtracking、Okumuraら)に基づく、タスクが途切れず続くlifelong型のマルチロボット・プランナー。論文をもとに実装しました。ブラウザのWeb Worker内で動作し、このページの主な数値を支えるすべてのシミュレーションも、同じプランナーのコードで実行しています。
  • ソフトな一方通行:塗り分けた方向は、無向グリッド上の重みになります。逆走のコストは1ステップではなく3ステップなので、迂回のほうが長くなる場合や、別のロボットがその場所を必要とする場合には、ロボットは逆走もします。マップエディタは、セルの封鎖・開放を問わず、どのループにも属さない通路が生じる編集をすべて拒否します。これはPIBTの到達可能性の証明に必要な条件で、グラフの橋(ブリッジ)を検出する処理で確認しています。
  • ランダムな保留を伴う同期実行。毎秒、全ロボットが動く前に、計画された移動の1%をランダムに保留し、保留されたロボットの後ろに並ぶロボットも一緒に保留します。そのため、ロボットが占有中のセルへ動かされることはありません。独立したチェッカーが全ステップを検証します。
  • ピックステーションでのピック時間は、ポッドごとにランダムに決まります(ガンマ分布)。ライブビューでは、平均を3秒、6秒、12秒、24秒から切り替えられます。
  • 乱数シードを固定した一時間の試行4,740回によるスイープ。メインフロアで20台から400台まで、確認用により大きなフロアでも実行しました。すべての点に95%信頼帯を、頂点にはブートストラップ区間を付けています。
03

技術スタック

JavaScript(ES modules)をWeb Workerで実行 · three.js · スイープにNode.jsのworker threads · 統計処理にPythonとNumPy

04

数値

数値測定方法
毎時5,134回

スループット曲線の頂点です。条件は双方向通路、平均ピック時間6 s。ピックステーションにポッドが一つ届くと提示一回と数え、グリッドの一ステップを一秒とみなします。20台から400台で乱数シードを固定した一時間の試行1,400回に当てはめた平滑化曲線(LOESS)の最大値です(95%区間は5,130〜5,139)。

196〜235台

平らな頂点です。この範囲のどの台数でも、最良値の0.5%以内に収まります。平滑化曲線のピークは214台(ブートストラップ区間213〜216)で、平滑化の幅を変えると、この点は212〜216の間で動きます。

−1 → −7(ロボットあたり)

ロボットを増やすごとに失われる処理量を、当てはめた曲線から求めたものです(95%ブートストラップ区間付き)。

  • 214 → 235台:毎時−1.2(−1.4〜−1.0)
  • 235 → 260台:毎時−3.7(−4.0〜−3.5)
  • 260 → 300台:毎時−5.7(−6.1〜−5.4)
  • 300 → 400台:毎時−7.1(−7.3〜−6.8)
−20.5%

同じ当てはめ曲線上での、400台時の処理量(毎時4,080回)の頂点に対する差です。

+25.4%

通路を一方通行に塗り分けたことによる頂点での改善で、191台で毎時6,439回です。同じフロアと設定で、乱数シードを固定した別の1,400回の試行で測定しました。95%ブートストラップ区間は25.3%〜25.5%です。

2.5%以内

ピック時間24 sでは、どの台数でも、塗り分けありとなしのフロアの差は2.5%以内に収まります(各点で乱数シードを固定した10回の試行)。16か所のステーションが、処理量の上限を毎時2,400回に抑えます。

35% → 48%

移動中のロボットのうち、8 s前より目的地に近づいていないものの割合です。214台と400台で測定しました(双方向通路、それぞれ乱数シードを固定した一時間の試行10回)。映像とライブビューで灰色のタイルとして表示されるロボットです。

衝突 0件

乱数シードを固定した4,775回の試行(シミュレーション上の2,120万ステップ、計画された移動の0〜5%をランダムに保留)で、独立したチェッカーは、どのステップでもセルの共有、位置の入れ替わり、飛び越しを一件も検出しませんでした。プランナーと実行ルールにより、これらは構造上起こりません。

4,775回の試行でデッドロック 0件

観測結果であり、証明ではありません。10分間のウォームアップ後、ピッキングが一度も完了しない5分間が生じた試行はありませんでした。ピック時間6 sでは、移動中のロボットが111 sを超えて停止したことはありません。ピック時間24 sでの最長は316 sで、混雑したステーションの順番を待っていたロボットでした。4,775回の試行には、400台でシミュレーション時間10時間ずつの試行35回が含まれます。

0.11 ms

400台でのステップあたりの平均計画時間です(スイープ中、Apple M1 ProのノートPC上のNode.js)。同じコードは、同じノートPCのデスクトップ版Chromeでステップあたり0.13〜0.4 msでした。

05

静止画

06

ライブで試す

ブラウザ上で動くインタラクティブビューです。開くまでは何も読み込みません。

ライブで試す ダウンロード 0.9 MB

同じような課題をお持ちですか?

計算したいこと、シミュレーションしたいこと、判断したいことをお聞かせください。私たちならどのように取り組むかをお伝えします。

相談する ロボティクス