MAPFでは、複数のエージェントがグラフ上の開始頂点からそれぞれの目標頂点へ移動し、同時刻の頂点衝突や、隣接頂点間で互いの位置を交換するスワップ衝突を避ける必要がある。時間は離散化され、各エージェントは待機または隣接頂点への移動を一ステップごとに実行する。完全性や最適性を保証する手法は大規模・高密度な問題で計算負荷が高く、一方で高速な手法は最適性や完全性を犠牲にすることがある。本論文は、このような高密度MAPFを、厳密最適化ではなく多項式時間のルールベース方式で扱う。
中心的な貢献は、現在位置から目標へ向かう連結頂点列をコリドーとして作り、そこに進む対象エージェントのために他のエージェントを退避させるMACGAである。さらに、ルールベースのPIBTをMACGAの計画に統合したMACGA+PIBTを提案し、実行時間と解品質の改善を狙う。両手法は多項式時間で動作し、提示された理論的性質として、各エージェントが最終的に目標へ到達するリーチャビリティを持つ。ただし、これは全エージェントが同時に目標にいることや、有限時間内の全体解決を保証するものではなく、論文自身も手法を不完全と位置づけている。
MACGAはエージェントに順序を付け、各ステップで各エージェントに一つ以上の行動列からなるアクティブプランを割り当て、その先頭行動を実行する。あるエージェントを処理するとき、現在位置から目標方向へコリドーを生成し、コリドー上で衝突やデッドロックを起こし得る他エージェントを、退避可能な頂点や経路を探索して外へ移動させる。その後、対象エージェントにコリドーを通るアクティブプランを与え、順序を更新することで、各エージェントが順番に先頭となる機会を持つ。コリドーの構成には、グラフの連結性を分けるseparating vertex（SV）と、それ以外の頂点に関する性質が使われる。MACGA+PIBTでは、PIBTが選んだ非SVへの移動をサイズ2の自明なコリドーとして扱い、その他の場合には通常のMACGA計画を用いる。
評価では、Prioritized Planning（PrP）、LNS2、PIBT、LaCAM、LaCAM*とMACGAおよびMACGA+PIBTを比較した。実験対象はMAPFベンチマークのempty-32-32、random-32-32-10、random-32-32-20、room-32-32-4、maze-32-32-2、maze-32-32-4の6地図で、エージェント数は100から700まで変化させた。各地図・エージェント数・アルゴリズムの組合せについて20個のランダムインスタンスを実行し、各インスタンスに30秒の制限を設けた。主な指標は制限時間内に解けたインスタンスの割合である成功率、実行時間、メイクスパンだった。すべての実装はPythonで、Apple M1チップと8GB RAMを備えたMacBook Air上で動かされた。
成功率では、MACGA系が全体として多くの問題を解き、特にroomやmazeのような狭い空間でベースラインとの差が大きかった。maze-32-32-2では、450エージェントまでのインスタンスの大部分を提案手法が解いた一方、比較対象は一つも解けなかったと報告されている。MACGA+PIBTはほぼすべての地図でMACGA単体より高い成功率を示し、MACGA単体より大幅に高速だった。トレードオフとして、MACGAの解は多くの場合ベースラインより高いコストを持つが、MACGA+PIBTのコストは多数の場合にベースラインに近い。
MAPFはロボット、倉庫、デジタルエンターテインメントなどに現れる基本問題であり、複数経路の衝突回避を同時に扱う。既存研究には完全かつ最適な探索型手法だけでなく、Prioritized Planning、PIBT、LNS2、LaCAM、LaCAM*のように規模拡張性を重視する手法もある。論文は、CBSやLaCAM系のような重い計算を必要とする方法が大規模問題で苦戦し得ることを動機としている。
入力は、無向グラフ、エージェント数、各エージェントの開始頂点と目標頂点から構成される。解は各エージェントの行動列の集合であり、同時刻の同一頂点占有と、エージェント同士のスワップを含む衝突がない必要がある。対象は全員が最終的に目標へ到達する古典的MAPFであるが、提案手法はサブオプティマルかつ不完全である。
コリドーは連結した頂点列で、対象エージェントを目標へ近づける一時的な移動領域として使われる。Separating vertexは、除去するとグラフの連結成分数が増える頂点であり、コリドーの構造や退避判断に関係する。理論部分は、条件付きの退避可能性、MACGAのリーチャビリティ、多項式時間性を論じている。ただし、提示された抜粋では一部の計算量式や定理の完全な前提・証明は欠落しているため、具体的な次数やすべての適用条件は確定できない。
6種類の32×32規模のベンチマーク地図を用い、エージェント数を100から700まで変えた。各条件で20個のランダムインスタンスを用い、30秒の実行時間制限を課した。比較対象はPrP、LNS2、PIBT、LaCAM、LaCAM*であり、PrPとLNS2はSIPPSを用いて実装された。実装言語やハードウェアが既報研究と異なるため、論文は公開論文の数値との直接比較に注意を促している。
MACGAとMACGA+PIBTは、評価された多くの条件でベースラインより高い成功率を示した。狭い通路を含むroom-32-32-4とmaze-32-32-2で相対的な優位性が特に大きく、maze-32-32-2では450エージェントまでの大部分を解いた。MACGA+PIBTはMACGAよりほぼ一貫して高速で、メイクスパンも多くの場合ベースラインに近かった。MACGA単体はベースラインより大きなメイクスパンを返す場合が多かった。
論文は、コリドー生成とエージェント退避に基づく二つのルールベースMAPF手法を提示した。両手法は多項式時間で動作し、提示された条件の下で各エージェントがいつか目標へ到達する性質を持つ。実験結果は、高密度かつ狭い地図での成功率と実行可能性における利点を支持する。著者は将来課題として、ライフロングMAPFと連続空間のマルチエージェント経路計画への適用を挙げている。
MACGAは最適性を保証せず、全体の有限時間内解決や同時到達も保証しない。グローバルな実行時間については、提示された抜粋で保証がないと明記されている。実験は6地図、Python実装、単一のApple M1環境、30秒制限に基づくため、他の実装言語やハードウェアへの一般化は確立されていない。抜粋だけでは、失敗した個別インスタンスの構造的原因や、完全な計算量の式も確定できない。
本研究の重要性は、厳密解を求める探索ではなく、混雑した狭い空間で移動を継続させる構造的な規則を設計した点にある。コリドー内のエージェントを単に優先順位付けするだけでなく、先に退避させることで、ボトルネックにおけるデッドロックを避けようとする。PIBTとの統合は、解決率、速度、メイクスパンの実用的なバランスを改善する方向を示している。
高密度MAPF、狭い通路や迷路状地図、リアルタイム性を重視するルールベース計画に関心がある研究者に適している。最適性証明、完全性、または厳密なコスト比較を主目的とする読者は、提案手法の不完全性と解品質のトレードオフを踏まえて読むべきである。