2次元グリッド上の作業空間において、複数のエージェントが静止障害物および移動可能な障害物（箱）を避けながら、各々の目的地へ到達する経路を求める問題を対象とする。エージェントは移動や待機のほかに、隣接する箱を押し出すアクションが可能である。エージェント数や箱の数に応じて状態空間が指数関数的に増大することに加え、あるエージェントが動かした箱が後続のエージェントの経路を遮断するといった、エージェント間での複雑な結合が生じる点が困難である。
従来のマルチエージェント経路探索手法を、移動可能な障害物を扱うM-PAMOへ適応・融合させた点に新規性がある。具体的には、高レベル探索で箱の動きを扱うCBS-MOH、低レベル探索に時空間での単一エージェント計画アルゴリズムであるST-PAMO*を組み込んだCBS-MOL、および優先順位に基づき箱を扱うPP-PAMO*を提案した。
CBS-MOHは、高レベル探索でエージェント同士、エージェントと箱、箱同士、および箱と環境の衝突を検出し、低レベルでは箱を無視して単一エージェントの経路を計算する。CBS-MOLは、低レベルのプランナーとしてエージェントと箱の状態を時空間グラフ上で扱うST-PAMO*を用い、高レベルから与えられた制約を満たす経路を探索する。衝突解決においては、原因となるエージェントに対し、特定の頂点の占有禁止や、箱を押し出す動作の禁止といった制約を課す。PP-PAMO*は、エージェントに固定の優先順位を割り当て、高優先度エージェントの経路を妨げないように箱を扱う。
最大20のエージェントと数百の箱を含むグリッドマップを用い、静止障害物の有無や箱の密度を変化させて評価した。比較手法はCBS-MOH、CBS-MOL、およびPP-PAMO*である。評価指標として成功率、実行時間、経路コスト、生成ノード数を用いた。結果として、箱の密度が増すと両CBS手法の成功率は低下するが、低レベルで箱を考慮するCBS-MOLの方が高い成功率を示す傾向がある。また、エージェント数が多い場合は、計算が高速なCBS-MOHの方が制限時間内の反復回数を稼げるため成功率が高くなるが、解に到達した際の生成ノード数はCBS-MOLの方が少ない。また、PP-PAMO*はCBS手法と比較して成功率が低く、実行時間も長い傾向にある。
CBS-MOHは低レベルで箱を考慮しないため、経路コストが大きくなる場合がある。CBS-MOLは、低レベル探索時に他エージェントによる箱の移動を事前に把握できないため、完備性や最適性が失われるケースがある。また、ST-PAMO*において高優先度エージェントの経路を妨げないかを確認する処理が計算コストを増大させる。今後の課題として、CBSベースの手法では押し出された箱の情報を低レベル探索へより詳細に伝達する戦略や、制約の統合による性能向上が挙げられる。PP-PAMO*については、優先順位の動的な決定や、経路チェック回数の削減による高速化が検討課題である。
本研究は、複数のエージェントが静止障害物および移動可能な障害物の間を、衝突を避けながら始点から終点へ移動する経路を求める、移動可能障害物のあるマルチエージェント経路探索（M-PAMO）を対象としている。移動可能な障害物の存在により、エージェントと障害物の両方を含む状態空間がエージェント数や障害物数に対して指数関数的に増大し、エージェント同士が空間的・時間的に密接に結合するという課題が生じる。本論文では、マルチエージェント経路探索で用いられるConflict-Based Search（CBS）や優先度付き計画法（PP）、および単一エージェント向けのPAMO*を、M-PAMOに適応・融合させる試みを行っている。最大20のエージェントと数百の移動可能な障害物を用いた比較実験を通じて、各アプローチの長所と短所を明らかにしている。
本研究では、エージェントが動かせる障害物（オブジェクト）が存在する環境下での複数エージェント経路計画問題であるM-PAMOを扱う。この問題は、エージェントとオブジェクトの両方の数に応じて状態空間が指数関数的に増大し、あるエージェントが移動させたオブジェクトが後続のエージェントの経路を遮断するといった、空間的・時間的な強い結合が生じる点が大きな課題である。本論文では、既存のMAPF手法であるConflict-Based Search (CBS) と優先度付き計画法 (PP) をM-PAMOへ拡張した3つの手法を提案する。具体的には、高レベル探索においてオブジェクトとの衝突を新たな制約として扱うCBS-MOH、低レベル探索に時空間での単一エージェント計画アルゴリズムであるST-PAMO*を組み込んだCBS-MOL、およびエージェントに優先順位を割り当て、高優先度エージェントの経路を妨げないようにオブジェクトを扱うPP-PAMO*である。最大20のエージェントと数百のオブジェクトを含む様々なマップを用いた実験により、CBS-MOHおよびCBS-MOLはM-PAMOにおいて最適解を保証しないことが示されている。
本研究が扱う移動可能障害物のあるマルチエージェント経路計画問題（M-PAMO）は、2次元のグリッド状グラフで構成される作業空間において、複数のエージェントが各々の目的地へ到達する経路を求めるものである。作業空間の各セルは、エージェントが移動可能な自由空間、移動不能な静止障害物、およびエージェントによって動かせる箱（移動可能障害物）のいずれかに分類される。エージェントは、その場での待機、上下左右への移動、または隣接する箱を押し出す「プッシュ」というアクションが可能であり、これらはいずれも1単位の時間ステップを消費する。箱をプッシュする条件は、エージェントが箱に隣接して移動を行うこと、かつ、移動先のセルが自由空間であり、かつ他のエージェントや箱によって占有されていないことである。衝突には、エージェント同士や箱同士が同じ位置を同時に占有する頂点衝突、反対方向から同じエッジを通過するエッジ衝突、およびエージェントと箱が同じ位置やエッジを同時に占有するエージェント・箱衝突が含まれる。本問題の目的は、これらすべての衝突を回避しつつ、全エージェントの経路コスト、すなわち目的地への到着時刻の総和を最小化することである。
本セクションでは、移動可能な障害物が存在するマルチエージェント経路計画（M-PAMO）を解くための、Conflict-Based Search（CBS）を拡張した2つの手法、CBS-MOHとCBS-MOLが提案されている。CBS-MOHは、高レベルの探索においてエージェントの経路に基づきボックスの動きをシミュレーションして衝突を検出し、低レベルのプランナーではボックスを無視して単一エージェントの最短経路を計算する。一方、CBS-MOLは、低レベルのプランナーとして、エージェントとボックスの両方の状態を時空間グラフ上で扱うST-PAMO*を用い、ボックスの初期位置を考慮しながら高レベルから与えられた制約を満たす経路を探索する。衝突解決においては、エージェント同士（AA）、エージェントとボックス（AB）、ボックス同士（BB）の衝突、およびボックスがマップ外や静止障害物に押し出されるボックス押し出しルール（BPR）の違反に対し、ボックス自体ではなく、それらを引き起こすエージェントに対して特定の頂点の占有禁止や特定の押し動作の禁止といった制約を課す。実験的な分析により、CBS-MOHはボックスの動きを考慮しないため最適性を欠く場合があり、CBS-MOLは低レベルで他エージェントによるボックスの移動を把握できないため、完備性や最適性が失われるケースがあることが示されている。
動かせる障害物（ボックス）が存在するマルチエージェント経路計画において、CBS-MOH、CBS-MOL、およびPP-PAMO*の性能を、静的障害物がないマップと10%の静的障害物があるランダムマップを用いて評価しました。ボックスの密度を変化させた実験では、ボックスが増えるほど相互作用が複雑になるため、CBS-MOHとCBS-MOLの成功率は共に低下しますが、低レベル探索においてボックスを考慮するCBS-MOLの方が一般に高い成功率を示します。エージェント数を増やした実験では、エージェント数が多い場合にCBS-MOHがCBS-MOLを上回る成功率を記録しており、これは低レベル探索でボックスを無視するCBS-MOHの方が計算が高速であるため、制限時間内に多くの衝突解決の反復処理を行えることに起因します。一方で、両手法が共通して解けたインスタンスにおける生成ノード数を比較すると、CBS-MOLの方が少ないノード数で解に到達しており、低レベル探索でのボックス考慮が反復回数の削減に寄与していることが示されています。優先度付き計画であるPP-PAMO*と比較すると、CBS系の手法は成功率と実行時間の両面で優れていますが、経路コストに関しては、低レベル探索でボックスを考慮するCBS-MOLやPP-PAMO*の方が、ボックスを無視するCBS-MOHよりも小さなコストを実現する傾向があります。
本研究では、移動可能な障害物が存在する環境下でのマルチエージェント経路計画問題であるM-PAMOを定式化し、既存のCBS（Conflict-Based Search）およびPP（Prioritized Planning）を基盤とした3つの手法を提案して、様々なマップにおける性能比較を行いました。エージェントと箱の複雑な相互作用がエージェント間の結合を強めるため、計算上の困難が生じ、既存のCBSやPPの手法に大きな負荷がかかることが示されました。今後の展望として、CBSベースの手法については、押し出された箱の情報を低レベルの探索へさらに伝達することや、エージェントや箱に対して異なる制約を付与する戦略を組み合わせて制約を統合することで、性能向上を図ることが挙げられます。また、PP-PAMO*については、優先順位を固定ではなく動的に決定することや、影響のない計画経路のチェック回数を減らすことで探索を高速化することが検討課題として示されています。