BRaPは、倉庫の格子状保管領域にある割当済みブロックを、指定された目標頂点の集合へ移動し、最終的に割当済みブロックを完了状態にする問題である。入力は、隣接関係を持つグラフ状のグリッド、割当済みブロック、目標を持たない未割当ブロック、空き頂点、障害物、目標頂点であり、出力は全割当済みブロックを目標へ移動させる衝突のない計画である。計画には割当済みブロックの移動だけでなく、経路を空けるための未割当ブロックの移動も含まれる。頂点の同時占有、同一辺の同時利用、直前に別のブロックがいた頂点への移動を避ける必要がある。ブロック数が増えると可能な配置と行動の組合せが指数的に増え、深く埋もれたブロックの取り出しが困難になる。
本研究は、密集倉庫におけるブロック再配置を、状態、行動、衝突制約、完了条件を明示したグラフ探索問題として正式に定義する。BRaPとスライディングパズル、Rush Hour、ブロック移動問題、Sokoban、駐車場再配置、MAPFなどとの構造的な類似点と相違点を整理する。構成空間探索、PDDLによる計画、優先度付き構成空間探索、BR-LaCAM、経路阻害を抑えるヒューリスティック手法という五つの解法を、同じ問題設定に適用する基盤を提示する。未割当ブロック、追従衝突、複数ブロックの並列移動を扱う点で、通常のMAPF手法をそのまま適用する場合との差異を明確にした。
構成空間探索では、時刻、割当済みブロックの位置、空き頂点、完了済みブロックを状態として表し、各行動によって状態を遷移させる。基本形では一時刻に一つの行動だけを許し、ダイクストラ法やA探索によって、初期状態から割当済みブロックがなくなる完了状態までの低コスト経路を探索する。この定式化をPDDLでも表現し、グリッドの頂点、ブロックの位置、移動条件、完了条件を記号的な問題として計画器に与える。優先度付き探索では、目標への近さに基づいてブロックの順序を定め、先に計画したブロックを制約として扱いながら、各時刻に複数ブロックを並列に動かす。BR-LaCAMは高レベルで構成を探索し、低レベルで衝突しない移動の組合せを列挙することで到達可能な構成を調べ、初期解を得た後もより低コストの解を探索する。ヒューリスティック手法は、各ブロックについて他のブロックへの阻害が少ない目標までの経路を生成し、高レベル探索、構成生成、低レベル制約を組み合わせて探索量を抑える。
評価には、4×10、6×10、8×10、10×10、20×20、40×40、80×80のグリッドを用いた13,860件のテストケースを用いた。割当済みブロック数は少なくとも1で、通常はグリッド頂点数の12.5パーセントまで、空き頂点数は最大で25パーセントまでとした。目標は境界頂点を用いる条件と、選択制約の異なる二種類のランダム目標条件を設定し、障害物はグリッド長の5分の1に相当する正方形として右下に配置した。五手法について、成功率、複合行動コスト比、計画全体の完了時間比、最初の解を得るまでの時間を比較した。各ケースの制限時間は10秒で、評価はAMD EPYC 7R13を搭載した単一マシン上で行い、PDDLの実行にはFast Downwardを使用した。
グリッドが大きくなるほど、また割当済みブロックが増えるほど、探索空間の増大によって失敗率が上がる。目標の選択が厳しい条件では、同じグリッド規模でも解を見つけにくくなる。基本の構成空間探索は一時刻一行動に制限されるため分岐を抑えられる一方、複数ブロックの同時移動による計画時間短縮を十分に表現できない。既存のMAPFソルバの多くが追従衝突を無視するため、BRaPに適用するには追加の制約処理が必要である。今後は、異なる終端状態、同時行動数の制限、追加目的関数、運用上の優先度、目標選択と行動選好の改善を扱う必要がある。
大規模なロボット倉庫では、保管密度を高めるためにブロックを格子状に配置し、ロボットがブロックを持ち上げて移動させる。注文対象のブロックが他のブロックの下や奥にある場合、周囲のブロックを一時的に移動して搬出経路を確保しなければならない。この状況は、複数の移動体の衝突回避、空間の一時的な解放、目標への搬送を同時に要求するため、通常の単一エージェント経路探索より複雑である。
障害物を含むグラフ上で、割当済みブロックを目標頂点へ移動させ、必要に応じて未割当ブロックを退避させる衝突のない計画を求める。目的関数には、割当済みブロックの移動数、未割当ブロックの移動数、各行動コストの合計、計画全体が完了するまでの時間などを設定できる。完了条件は割当済みブロック集合を空にすることであり、ブロック数が増えると実行可能な配置と行動の組合せが急増するため、解の品質と大規模事例へのスケーラビリティの両立が課題になる。
BRaPでは、割当済みブロックと未割当ブロックについて、移動、待機、完了の行動とそれぞれのコストを設定できる。衝突は、同じ頂点を同時に使う場合、同じ辺を同時に使う場合、前時刻に別のブロックがいた頂点へ移動する場合に分類される。基本の構成空間探索は一時刻一行動であるのに対し、優先度付き探索はブロックごとに一行動を許して並列性を導入する。BR-LaCAMは高レベル探索と低レベルの移動組合せ探索を組み合わせ、有限な探索空間を網羅することで、解が存在するBRaPに対する完全性が主張されている。初期解のコストを上限として探索を続けるため、実行可能解の発見後に解を改善する anytime 性も持つ。
実験では、七種類のグリッドサイズ、異なる割当済みブロック数、空き頂点数、三種類の目標生成条件を組み合わせた。右下に固定した正方形障害物を含む各パラメータ条件から、ランダムに10ケースを生成した。五つの提案手法を、成功率、複合コスト、計画完了時間、初期解到達時間で比較した。成功率が20パーセント未満の条件では、複合コスト比と完了時間比を報告していない。実行は単一のAMD EPYC 7R13マシン上で行い、1ケースあたり10秒を上限とした。
BR-LaCAMの成功率は、4×10から80×80までのグリッドを含む評価全体で99パーセント、ヒューリスティック手法では93パーセントだった。全条件の集計では、優先度付き探索、構成空間探索、PDDLの成功率はそれぞれ48パーセント、39パーセント、37パーセントで、BR-LaCAMとヒューリスティック手法を下回った。BR-LaCAMとヒューリスティック手法は、テストケースの半数超で1ミリ秒以内に初期解を発見し、BR-LaCAMは90パーセント超のケースで1秒以内に初期解を得た。解が得られたケースでは、この二手法が複合コストと計画完了時間の両方で概して良好だった。複合コスト比は、多くのケースで最良手法に対しておおむね1から10の範囲に分布した。
本研究は、密集倉庫で深く埋もれたブロックを取り出す問題を、未割当ブロックと複数の衝突制約を含むBRaPとして定式化した。13,860件の評価から、BR-LaCAMとヒューリスティック手法が、他の三手法より大規模事例で高い成功率と短い初期解探索時間を示した。これらの結果は、BRaPを研究・比較するための基盤を提供し、今後はBR-LaCAMの解品質とスケーラビリティを改善することが有望な方向であることを示す。
本文で確認できる限界として、グリッドの大型化、割当済みブロック数の増加、厳しい目標選択に伴う成功率低下がある。基本の構成空間探索は一時刻一行動に制限され、待機行動も禁止されるため、実システムの並列動作を完全には表現しない。実験では障害物の形状と位置、目標生成法、計算機環境、10秒の時間制限が限定されており、動的障害物、通信遅延、ロボット性能差、実運用上の優先度は検証されていない。取得した本文では、実機での実証や、すべての条件に対する厳密な最適性の網羅的比較は確認できない。
本研究の重要性は、倉庫自動化で生じる、目的ブロックが他のブロックに埋もれている状況を、MAPFと記号計画の双方から扱える問題として整理した点にある。目標を持たないブロックが通路確保を担う設定と追従衝突の扱いにより、通常のMAPFでは表しにくい倉庫特有の制約を明示している。多数の合成テストケースで五手法を比較したため、高密度なブロック再配置研究における成功率、解品質、初期解速度の基準として利用できると解釈できる。
高密度倉庫のロボット再配置、未割当エージェントを含むMAPF、記号計画とPDDL、スライディングパズル型の組合せ探索に関心を持つ研究者に適している。複数ロボットの衝突回避だけでなく、通路を空ける補助ブロックの計画まで扱いたい場合に特に有用である。BR-LaCAMやヒューリスティック探索を大規模グリッドで評価する際の初期ベースラインとしても利用できるが、実機性能、動的障害物、現実的な同時行動制約を重視する読者は、本文の評価範囲を超える追加検証が必要である。