ロボット倉庫やドローン群の運用を想定し、各計画期間に許容される計算予算B（探索ノードの展開数）と、エージェントが次に実行すべきステップ数w（実行ウィンドウ）が制限された環境下での、リアルタイム多エージェント経路計画（RT-MAPF）を対象とする。従来のウィンドウ計画法では、予算内に解が見つからない場合に単に計算を停止するのみであり、予算の有無や配分を明示的に考慮できていないという困難があった。入力としてエージェントの現在位置と目的地、グラフ構造を受け取り、衝突のない長さwの経路の接頭辞を出力する必要がある。
既存手法が計算予算を単なる打ち切り条件として扱っていたのに対し、予算をエージェント間の配分対象として明示的に扱う予算認識型RT-MAPFのフレームワークを提案した。最新のMAPF-LNS2アルゴリズムに対し、衝突数や制御理論、マルチアームドバンディット（MAB）の概念を取り入れた複数の予算配分方策（BAP）を導入した点が新規である。単一の方策が全ての環境で万能ではないことを明らかにし、設定ごとに最適な方策を選択するオラクル的なアプローチの有効性を提示した。
MAPF-LNS2をベースとし、選択されたエージェントの近傍集合に対してどれだけの計算予算を割り当てるかを決定する予算配分方策（BAP）を用いる。具体的な方策として、近傍の衝突数に比例して予算を割り当てるConflictProportion、衝突の少ないエージェントを優先して予算を割り当てるReverseConflictProportion、衝突数の変化量に基づきPID制御の概念を用いて予算を割り当てる方策がある。さらに、MABを用いて、各方策による衝突削減の成否に応じて方策の重みを更新し、オンラインで最適な方策を選択する仕組みを構築している。
Room、Random、Mazeの3種類のグリッドマップを用い、実行ウィンドウとエージェントあたりの予算の組み合わせを変えて評価した。比較対象は、全エージェントが単一の共有予算プールから予算を消費するShared、および高速な初期解生成を行うPIBTである。評価指標には成功率とAUCを用いた。実験の結果、RandomマップではMABが、RoomやMazeではConflictProportionが最も高い成功率を示した。また、最適な方策を選択するSingle Policy Oracle（SPO）は、ベースラインを上回る成功率を得た。
単一の予算配分方策が全てのパラメータ設定や環境において常に優れているわけではないというトレードオフが存在する。今後の課題として、実行中にエージェントへの予算配分を動的に調整するためのオンライン学習メカニズムの組み込みや、目標が動的に変化するライフロングMAPF設定への適用が挙げられる。
本研究は、ロボット倉庫やドローン群などの実世界での運用を想定し、限られた計画時間（計画予算）と一定の実行ステップ（実行ウィンドウ）の中で、エージェントが衝突を避けつつ目的地へ到達するリアルタイム多エージェント経路計画（RT-MAPF）を扱う。既存手法は、計画予算の大きさを明示的に考慮せず、各計画期間においてウィンドウ化されたMAPFアルゴリズムを繰り返し呼び出すのみであったが、本論文では最新のMAPFアルゴリズムであるMAPF-LNS2に対し、計画予算をどのように配分するかという異なる方策を調査している。実験の結果、全エージェントが単一の共有予算プールから計算資源を消費するベースライン手法は、困難なシナリオにおいて効果的ではないことが示された。一方で、エージェント間で計画予算を適切に分配する方策は、より少ない時間でより多くの問題インスタンスを解決できる。なお、単一の方策がすべてのパラメータ設定において常に優れているわけではないため、各設定に対して最適な方策を選択するオラクル的なアプローチを提案している。例えばランダムマップの実験では、ベースラインが最も高い成功率を達成できた構成が44パーセントであったのに対し、このオラクル的なアプローチはすべての構成において最高の成功率を達成した。
マルチエージェント経路計画（MAPF）において、限られた計画予算内でエージェントが次に実行すべき一連の動作を決定しなければならない、リアルタイムMAPF（RT-MAPF）という問題を扱う。従来のウィンドウ計画法は予算内に解を返せない可能性があり、既存の失敗回避策も予算の有無を考慮せず計算を停止するのみであった。本研究では、利用可能な予算を明示的に考慮する予算認識型RT-MAPFのフレームワークを提案し、MAPF-LNS2アルゴリズムをベースに構築している。このフレームワークでは、予算配分方策（BAP）を用いて、選択されたエージェントの近傍集合に対してどれだけの計画予算を割り当てるかを決定し、予算が尽きた場合はその近傍の計画を維持する。提案するBAPには、衝突数に応じて予算を増減させるもの、PID制御に着想を得たもの、およびマルチアームドバンディット（MAB）法に基づくものがある。実験の結果、単一のBAPが全てのケースで最適となるわけではないが、設定に応じて最適な方策を選択することで、ベースラインと比較して問題解決率を大幅に向上させることが確認された。
マルチエージェント経路探索（MAPF）は、グラフ上の各エージェントに、頂点衝突や入れ替わり衝突のない経路を割り当てる問題であり、全エージェントの移動コストの総和であるSOCや、全エージェントが目標に到達するまでの時間であるMakespanの最小化を目的とする。本研究では、リアルタイム性に優れた非最適解アルゴリズムとして、優先度継承とバックトラッキングを用いるPIBTや、近傍探索を用いて衝突解消と解の改善を行うMAPF-LNS2に焦点を当てる。MAPF-LNS2は、特定の近傍エージェント群を繰り返し選択して経路を再計画する手法であり、単一エージェントの経路計算にはSIPPやその拡張であるSIPPSが用いられる。また、目標が動的に変化するLifelong MAPFに対しては、実行ウィンドウと計画ホライゾンを設定して計画と実行を交互に行うRolling Horizon Collision Resolution（RHCR）という枠組みが一般的である。さらに、計算資源である計画予算が制限された状況下での探索として、局所的な先読み、ヒューリスティック関数の更新、行動の実行を繰り返すリアルタイム・ヒューリスティック探索（RTHS）の概念が示されており、これらをMAPFに適用したBMAA*やWinC-MAPFといった手法が存在する。
本研究が扱うリアルタイム多エージェント経路探索（RT-MAPF）は、古典的なMAPFに、各計画期間に許容される計算予算Bと、各エージェントが次の計画期間までに実行すべきステップ数wを加えた問題として定義される。RT-MAPFアルゴリズムは、各計画期間の開始時に、すべてのエージェントに対して長さwの経路を割り当てる解の接頭辞を出力する必要があり、その経路は頂点衝突やスワップ衝突を含んではならない。本研究では、計算予算Bを各計画期間内に展開可能な単一エージェント探索ノードの最大数として定義している。既存手法として、計画期間を短く設定して予算内に収める方法や、予算を使い果たすまで計画期間を段階的に伸ばす方法があるが、これらは衝突の発生や、予算不足により有効な計画が見つからない計画失敗を招く可能性がある。これに対し、計画に失敗した際に部分的な解から衝突のない経路を合成する「失敗ポリシー」を用いる枠組みが提案されており、衝突するエージェントのみをその場に留め、他のエージェントは移動を継続させるIStayなどの手法が、実行中の計画と改善を重視するPIEフレームワークにおいて有効であることが示されている。
既存の研究であるMoragらの手法とPIEは、計画が失敗した際に部分解を返すプランナーを必要とするが、いずれも計算予算を単なる打ち切り条件として扱うのみで、予算を直接的に考慮していない。Moragらの手法はPrPを応用しており、PIEではまず高速で劣最適な解を求めるLaCAM*を実行して初期解を見つけ、その後にMAPF-LNSを用いて解を改善する。PIEにおいて初期計画フェーズで失敗した場合は、それまでにLaCAM*によって探索された中で最も優れたノードを選択し、その後の計画フェーズで失敗した場合は、LaCAM*によって得られた初期解を部分解として返す。本セクションでは、これら既存手法に対し、MAPF-LNSを拡張して有用な部分解を返すための、計算予算を意識した新しい手法を提案する。
MAPF-LNS2において、特定の近傍に計算予算を過剰に投入することで他のエージェントの計画を阻害する問題を回避するため、複数の予算配分方策（BAP）を提案している。ConflictProportionは、選択された近傍に含まれるエージェントの衝突数に比例して予算を割り当てるが、探索に必要な最小ノード数を下限値として設定することで、予算不足による計画失敗を防いでいる。ReverseConflictProportionは、衝突の少ないエージェントに優先的に予算を割り当てて経路を早期に確定させることで、問題全体の複雑さを軽減することを目指している。また、PID方策は、衝突数の変化量や近傍が選択された回数に基づき、残余予算の割合ではなく絶対値として予算を割り当てる。さらに、Multi-Armed Bandit（MAB）フレームワークを用いることで、各方策の重みを経路の衝突削減の成否に応じて更新し、状況に応じて最適な予算配分方策をオンラインで選択する仕組みを導入している。
本実験では、MAPF-LNS2における複数の予算配分ポリシー（Shared, PID, CPB, RCPB, MAB）と、高速な初期解生成を行うPIBTを比較評価しています。Room、Random、Mazeの3種類のグリッドマップを用い、実行ウィンドウとエージェントあたりの予算の組み合わせを変えて、成功率と解の品質を示すAUC（曲線下の面積）を指標として検証を行いました。実験の結果、単一のポリシーが常に優れているわけではなく、RoomやMazeではCPB、RandomではMABが最も高い成功率を示すなど、環境やパラメータに依存することが示されました。各パラメータ構成において最も成功率の高いポリシーを選択するSingle Policy Oracle（SPO）は、成功率とAUCの両面でベースラインを上回る結果を得ています。ただし、SPOは成功率の最大化を目的としているため、予算が実行ウィンドウに対して極端に少ない場合など、特定の条件下では解の品質（AUC）においてベースラインに劣るケースも確認されました。アブレーション解析の結果、ポリシーの重要度は環境に依存するものの、PIDはSPOの性能維持に大きく寄与し、RCPBは寄与が低い傾向にあることが明らかになりました。
本研究では、各計画期間が固定された短い時間予算内で終了し、予算終了後はエージェントが事前に定義された一連の移動を実行しなければならないリアルタイムMAPF（RT-MAPF）問題を扱っています。既存のMAPFアルゴリズムを単に予算内で停止させるのではなく、エージェント間で計画予算を適切に配分することの重要性を指摘し、最先端のMAPF-LNS2アルゴリズムに対して予算を分配する複数の手法を提案しました。具体的には、エージェントの近傍に割り当てる予算を算出するConflictProportion、ReverseConflictProportion、およびPIDという手法に加え、動的な方策適応のためのマルチアームドバンディット機構を導入しました。実験の結果、最適な方策はシナリオによって異なるため、最適な方策を選択するアルゴリズムの実装が重要であることを示し、賢明な予算配分方策を用いることでエージェントをより迅速に目標へ移動させられることを確認しました。今後の展望として、実行中に異なるエージェントへの予算配分を調整するためのオンライン学習メカニズムの組み込みや、ライフロングMAPF設定への適用が挙げられています。