ロボティクス · 倉庫のロボット群(Goods-to-Person方式)
ロボットを減らし、処理量を増やす
数百台の倉庫ロボットの走行を、ブラウザ上でリアルタイムに計画します。ロボットを増やすと処理量が落ち始める台数を見つけてください。
概要
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回の試行)。実際のロボット群はもっと早く渋滞し、別のプランナーなら頂点の位置も変わります。
開発内容
- PIBT(priority inheritance with backtracking、Okumuraら)に基づく、タスクが途切れず続くlifelong型のマルチロボット・プランナー。論文をもとに実装しました。ブラウザのWeb Worker内で動作し、このページの主な数値を支えるすべてのシミュレーションも、同じプランナーのコードで実行しています。
- ソフトな一方通行:塗り分けた方向は、無向グリッド上の重みになります。逆走のコストは1ステップではなく3ステップなので、迂回のほうが長くなる場合や、別のロボットがその場所を必要とする場合には、ロボットは逆走もします。マップエディタは、セルの封鎖・開放を問わず、どのループにも属さない通路が生じる編集をすべて拒否します。これはPIBTの到達可能性の証明に必要な条件で、グラフの橋(ブリッジ)を検出する処理で確認しています。
- ランダムな保留を伴う同期実行。毎秒、全ロボットが動く前に、計画された移動の1%をランダムに保留し、保留されたロボットの後ろに並ぶロボットも一緒に保留します。そのため、ロボットが占有中のセルへ動かされることはありません。独立したチェッカーが全ステップを検証します。
- ピックステーションでのピック時間は、ポッドごとにランダムに決まります(ガンマ分布)。ライブビューでは、平均を3秒、6秒、12秒、24秒から切り替えられます。
- 乱数シードを固定した一時間の試行4,740回によるスイープ。メインフロアで20台から400台まで、確認用により大きなフロアでも実行しました。すべての点に95%信頼帯を、頂点にはブートストラップ区間を付けています。
技術スタック
JavaScript(ES modules)をWeb Workerで実行 · three.js · スイープにNode.jsのworker threads · 統計処理にPythonとNumPy
数値
| 数値 | 測定方法 |
|---|---|
| 毎時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%ブートストラップ区間付き)。
|
| −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でした。 |
静止画
ライブで試す
ブラウザ上で動くインタラクティブビューです。開くまでは何も読み込みません。