マルチエージェントAMRフリート協調はここ数年、倉庫自動化の議論でますます取り上げられるようになってきましたが、その理由は複雑ではありません。倉庫内のAMRが数台から数十台に増えると、問題は1台の機械がどう動くかではなく、グループ全体がどうやって自分自身と衝突しないか、ということになるからです。

まず実際に何が起きるかから始めましょう。典型的な中規模のEC倉庫を例に取ります。最初のAMRは6台で、見事に稼働します。ピッキング生産性は目に見えて上がります。気をよくした経営陣はフリートを20台、さらに40台へと拡大します。ところがフリートが40台に達した年、倉庫に奇妙な光景が現れ始めます。メイン通路の交差点で、数台のロボットが鼻先を突き合わせて止まり、誰かが手動で介入するまで誰も動きません。そしてピッキングの波が来ると、十数台のロボットが狭い通路を待つ列を作り、空走率は下がるどころか上がっていきます。ロボットは増えたのに、こなす仕事はほとんど増えず、交通渋滞だけが何より先に身につきます。この光景の背後にあるのが、マルチエージェントAMRフリート協調の中心的な問題です。1台のロボットは自分自身の最適な経路を追求しますが、フリート全体にはシステム全体が絡まらないことが求められるのです。

マルチエージェントAMRフリート協調:集中型か分散型か

学術的にはこの種の問題をマルチエージェント経路探索、略してMAPFと呼び、数十年にわたって研究されてきましたが、単一の標準的な答えは生まれていません。実際には、スケジューリングのアーキテクチャは集中型と分散型の二つの陣営に分かれ、それぞれに代償があります。

集中型スケジューリングとは、1つの頭脳がすべてを決める方式です。中央サーバーがすべてのAMRの位置、タスク、道路ネットワークの状態を保持し、各車両の経路とタイミングをまとめて計算します。利点は全体像が見えることです。全体として最適またはそれに近い計画を立てられ、衝突は発生する前に解決されます。代償は計算量とリアルタイムの応答性です。フリートが大きくなるにつれて組み合わせの空間は爆発し、1つの全体最適計画を計算するのに、移動そのものより長い時間がかかることもあります。そして中央サーバーがダウンすれば、フリート全体も一緒に止まります。単一障害点のリスクは現実のものです。

分散型スケジューリングは逆のやり方です。各AMRが自分で判断し、近くの車両と機械間通信で通行権や待ち行列を交渉します。利点は局所的な障害への耐性、容易な拡張——ロボットを1台追加してもスケジューラーを作り直す必要がないこと——そして速いリアルタイム応答です。代償は、局所最適の合計が全体最適にならないことです。各車両は自分の近所しか見えず、数台のロボットが互いに礼儀正しく譲り合いながら、決して解けないループに入ることがあります。学術的にはライブロックと呼ばれます。倉庫の現場では「ロボットのダンス」と呼ばれています。

アーキテクチャ 意思決定 強み 代償
集中型 1台のサーバーが全台を計画 全体最適、衝突を事前に排除 計算負荷が重い、単一障害点のリスク
分散型 各車両が局所的に交渉 障害に強い、拡張が容易、応答が速い 局所最適、ライブロックの可能性

実際の倉庫がどちらか一方の極端に走ることはめったにありません。一般的なアプローチは階層化です。中央スケジューリングがタスク割り当てと大まかな経路を担当し、局所的な回避と譲り合いはリアルタイムで車両に任せます。粗い粒度では集中型、細かい粒度では分散型——それぞれがコストの半分を担います。この階層化された妥協こそ、今日ほとんどのAMRベンダーが実際に提供しているものです。

デッドロックと通行権:マルチエージェントAMRフリート協調の交通ルール

アーキテクチャが決まれば、次は道路のルールです。デッドロックはどうやって起きるのでしょうか。典型的な場面は、1台ずつしか通れない狭い通路に、両端から2台のAMRが入り、真ん中で出会うことです。どちらも前に進めず、どちらも後退する指示を持たず、あらかじめ設計されたルールがなければ、人が介入するまでそこに留まります。さらに厄介なのがリングデッドロックです。ループ状の通路に4台のロボットがいて、それぞれが1区画を占め、それぞれが前のロボットが動くのを待ち、ループ上の何も動けなくなります。

デッドロックの防止は、1台のロボットのためのより賢いアルゴリズムにかかっているのではありません。あらかじめ合意された交通ルールのセットにかかっています。第一に、一方通行レーンです。主要通路を一方通行にし、狭い通路は一方向からのみ入れるようにすれば、衝突の原因の半分は始まる前に消えます。第二に、優先クラスです。積載車両は空車より優先され、幹線レーン上の車両は側道から合流する車両より優先されます。優先順位は交差点で交渉するのではなく、スケジューリングルールに書き込まれます。第三に、予約です。重要な区間に入る前に、車両はスケジューラーに時間枠を予約し、時間枠が重なれば、通路の中で数分間凍りつくのではなく、入口で数秒待ちます。第四に、ゾーニングです。倉庫をスケジューリングゾーンに分け、ゾーンをまたぐタスクは境界点で引き渡し、1台の車両が倉庫全体を横切って連鎖的な衝突を引き起こさないようにします。

これらのルールはハイテクには聞こえませんが、まさにそれこそがフリートスケジューリングで最も価値のある部分である理由です。ここに直観に反する判断があります。AMRフリートにおいて、スループットに通常最も重要なのはロボットがどれだけ速く走るかではなく、譲り合いのルールがどれだけ明確に書かれているかです。1台の車両の速度を10パーセント上げても、節約した時間は交差点での待ち時間で完全に失われることがあります。通行権のルールを整えれば、フリート全体のスループットは上がります。速度は1台の車両の指標です。フローはフリートの指標です。この二つはしばしば対立し、スケジューリングはその対立を防ぐために存在します。

タスク割り当て:この注文を誰が引き受けるかはアルゴリズムが決める

経路の先には、スケジューリングが答えなければならないもう一つの問いがあります。新しいタスクが届いたとき、どの車両がそれを受け取るのか。最も単純な答えは最寄り割り当てです。最も近い空き車両が仕事を引き受けます。理屈は直観的で、実装も簡単です。欠点は、忙しいゾーンの近くの車両が常に最も忙しく、遠くの車両は暇なままになることです。作業負荷とバッテリーの消耗は不均一になり、車両の状態は時間とともにばらつき、メンテナンスコストもそれに続きます。

より丁寧なアプローチはオークション方式の割り当てです。スケジューラーがタスクを公示し、各車両が位置、バッテリー残量、現在の仕事に基づいて「コスト」を入札します。最も低い入札が勝ちます。この発想はオークション理論に由来し、学術文献でも広く議論されています。実際に稼働している導入例もあります。利点は、距離、バッテリー、タスクの種類がすべて1つの数値に折り込まれるため、フリートの負荷が自ら均衡することです。代償は通信と計算のオーバーヘッドです。タスクの流れが激しいと、オークション自体が負担になります。そのため多くのシステムは、波の合間やタスクが溜まったときにのみオークションを行い、それ以外の時間は重み付き最寄りルールを簡略化して使います。

具体例を挙げましょう。20台のフリートがピーク時に1時間あたり120件の搬送タスクに直面するとします。最寄り割り当てでは、人気の保管ゾーンに最も近い6台がタスクの半分を引き受け、バッテリーを急速に消耗し、シフトの途中で充電のために離脱しなければならず、実効フリートは15台か16台に縮みます。バッテリー重み付き割り当てでは、タスクが20台全体に分散し、1台あたりの負荷が下がり、充電ローテーションを波の合間にずらすことができるため、同じ20台でより高い実効稼働率を実現できます。これらの数字は、割り当てルールがフリートの実効規模にどう影響するかを示すための計算例です。実際の倉庫では、その倉庫自身のタスク分布と道路ネットワークに合わせて計算し直す必要があります。

マルチエージェントAMRフリート協調の行方

糸をまとめると、方向はかなり明確です。第一に、ハイブリッドアーキテクチャが主流になります。タスクと全体像は集中制御、回避と細部は分散制御で、どちらか一方が支配するのではなく、明確なインターフェースが二つの層を分けます。第二に、スケジューリングアルゴリズムはシミュレーションにより依存するようになります。新しいルールを本番に投入する前に、デジタルツインで何千もの波を実行し、デッドロックと混雑のシナリオを事前に明らかにしてから、実際の倉庫に展開します。第三に、タスク割り当ては「誰が最も近いか」から「誰が最も適しているか」へと移り、バッテリー残量、タスクの種類、メンテナンスサイクルがすべてコスト関数に反映されます。

しかし最後に一つ、忘れてはならない注意があります。スケジューリングアルゴリズムがどれだけ高度になっても、倉庫自体のレイアウトに取って代わることはできません。通路幅、保管ゾーンの配置、波のリズム——物理的な設計が最初から間違っていれば、たとえ最高のアルゴリズムでも、悪い道路ネットワークに継ぎ当てをしているにすぎません。アルゴリズムはロボットのグループが争うのを防ぐことはできます。しかし設計を誤った道路を広げることはできません。まず道路を正しく作り、それからフリートをどう走らせるかを話しましょう。この順序は、しばらく変わりそうにありません。

Dr. Chen(サプライチェーン研究者)著 英語版からの翻訳。内容に相違がある場合は英語版を優先します。