本研究は、共有環境内で複数のエージェントが衝突を避けつつ、全エージェントの移動時間の総和（SOC）を最小化するマルチエージェント経路探索（MAPF）を対象としている。ユーザーが指定した最適解の倍率（劣最適性係数）の範囲内で解を保証する「境界付きサブオプティマル」な設定において、既存のEECBSアルゴリズムは、各エージェントの経路閾値を動的に拡張する手法を用いる。しかし、この拡張が過剰になると、全体のSOCが許容範囲を超えてしまい、特定の経路集合での衝突解決ではなく、異なる経路集合間での探索の切り替えが頻発して効率が低下するという困難がある。
従来のGreedy-Based Flex Distribution（GFD）が、利用可能なフレックスをすべて使い切ることで全体のコストを急増させていたのに対し、衝突数や制約による遅延を考慮してフレックスを制御する手法を導入した。具体的には、衝突数に比例して分配するConflict-Based Flex Distribution（CFD）、予測遅延を優先配分するDelay-Based Flex Distribution（DFD）、およびこれらを階層的に組み合わせたMixed-Strategy Flex Distribution（MFD）という3つの新しいメカニズムを提案している。これにより、EECBSの完全性と境界付きサブオプティマリティを維持したまま、解の質と探索成功率の向上を実現した。
提案手法であるMFDは、まず制約による経路コストの増加を予測するDFDを用いて、頂点やエッジの制約、あるいは廊下やターゲットでの衝突パターンに基づいた推定遅延を優先的に割り当てる。その後、残りのフレックスをCFDを用いて、エージェントが関与する衝突数の比率に応じて分配する。MFDは、これらの分配によって全体のSOCが境界を超える場合には、CFDへの切り替えや、最小のSOLBを持つノードを用いた再計算を行うことで、フレックスの過剰な利用を抑制する。さらに、混雑した環境向けに、FOCALリストのノードを優先展開しつつ、OPENリストの展開によって下界の精度を高めるよう再設計されたFocal-A*探索を併用する。
6種類のMAPFベンチマークグラフを用い、成功率とグローバルな劣最適度を指標として、既存のEECBSおよびEECBS-GFDと比較評価を行った。実験の結果、EECBS-MFDはEECBS-GFDよりも高い成功率を達成し、かつEECBSと比較した際のグローバルな劣最適度の増大割合が53%と、GFDの56%を下回る結果を示した。また、エージェント数が増加しても、探索木の深さとノード展開数の比率を高く維持できることが確認された。
提案手法は、衝突数と劣最適度の間で優れたトレードオフを実現している。しかし、混雑した迷路グラフを用いた実験では、再設計したFocal-A*探索を併用しない限り、混雑環境における最適なフレックス配分を決定することには依然として課題が残ることが示されている。今後の課題として、制約に対するより正確な遅延の推定手法や、混雑した環境に特化したメカニズムの検討が挙げられる。
本研究は、各エージェントの移動時間を最小化する経路集合を求めるマルチエージェント経路探索（MAPF）において、解の総コストが最適解の指定された倍率を超えないように制御する境界付きサブオプティマルな問題を対象としている。既存の主要なアルゴリズムであるEECBSは、経路の閾値を調整するFlex Distributionを用いて探索を高速化しているが、閾値を増やすことで総コストが境界を超え、衝突解決の効率が低下するという課題があった。これに対し、本論文では衝突数に比例して柔軟性を分配するConflict-Based Flex Distributionと、制約を満たすために必要な追加の遅延時間を推定して分配するDelay-Based Flex Distributionを提案している。さらに、これらを階層的な枠組みで組み合わせたMixed-Strategy Flex Distributionを導入することで、EECBSの完全性と境界付きサブオプティマリティを維持している。実験の結果、提案手法は従来の貪欲なFlex Distributionよりも優れた性能を示し、混雑した環境向けに再設計したFocal-A*探索によってさらなる効率向上を実現している。
マルチエージェント経路探索（MAPF）において、全エージェントの移動時間の総和であるSOCを最小化する最適解の算出はNP困難であるため、ユーザーが指定した劣最適性係数の範囲内で解を保証する有界劣最適アルゴリズムが用いられる。既存の代表的な手法であるEECBSは、各エージェントの経路が個別に劣最適性の範囲内に収まることを要求するが、これでは経路全体のSOCが範囲内であっても、個々の経路が範囲を超えると探索から除外されてしまう。この制約を緩和するために、他のエージェントの経路コストと下限値の差分であるフレックスを特定の経路の閾値に割り当てる手法があるが、フレックスをすべて割り当てるとSOCが許容範囲を超えて探索が非効率になる問題や、下限値の過小評価によって本来見つかるべき解を見落とす問題が存在する。本研究では、SOCの増大を抑えるためにフレックスのすべてを使用しない新しい分配メカニズムと、混雑した環境下でエージェントの経路探索時に下限値を高めるよう設計されたFocal-A*の再設計を提案する。実験の結果、提案手法は120秒の実行時間制限内において、従来のEECBSと比較して成功率を向上させることが示された。
マルチエージェント経路探索（MAPF）は、無向グラフ上の複数のエージェントに対し、衝突のない経路集合を求める問題であり、全エージェントの経路コストの総和（SOC）を最小化する最適解、またはユーザー指定の係数wを用いたw倍以内のSOCに収まる限定劣最適解を求める。既存手法であるEECBSは、高レベルで制約木（CT）を構築し、低レベルのFocal Searchを用いて各エージェントの経路を探索する2段階のアルゴリズムである。低レベルの探索では、各エージェントの経路が個別に限定劣最適であることを保証する閾値を用いて探索を行う。これに対し、Greedy-Based Flex Distribution（GFD）は、CTノードにおける各エージェントの経路が個別に限定劣最適である必要はないという性質を利用する。GFDは、他のエージェントが持つコストの余裕分を閾値に加算することで、探索時の閾値を動的に拡張する手法である。GFDを用いることで、各CTノードにおけるSOCが限定劣最適性の範囲内に収まることが保証され、EECBSの完全性と限定劣最適性を維持したまま探索を行う。
既存のGFD（Greedy Flex Distribution）は、エージェントが経路探索時に許容される柔軟性をすべて使い切ることで、CTノードのSOC（Suboptimality Over Cost）を急増させ、グローバルな劣最適性の境界を超えてしまう課題があります。これにより、EECBSは本来探索すべき枝ではなく、SOCが低い別の枝を探索し続けることになり、探索効率が低下します。提案手法であるCFD（Conflict-Based Flex Distribution）は、エージェントが直面する衝突数に応じて柔軟性を分数的に分配することで、この問題を解決します。具体的には、あるエージェントが経路探索を行う際、そのエージェントが関与する衝突数と、CTノード内の全エージェント間の総衝突数の比率に基づいて、許容される柔軟性を割り当てます。この手法により、フォーカルサーチ中に制約を明示的に追加する代わりに柔軟性を活用して衝突を暗黙的に解消しつつ、将来の衝突解消のために柔軟性を温存することが可能になります。ただし、柔軟性の最大許容値が負になる場合は、CTノードの劣最適性を保証するためにGFDへと切り替えます。実験の結果、この分配手法はEECBSの探索効率を効果的に向上させることが示されています。
Delay-Based Flex Distribution (DFD)は、制約を満たすための経路再計画によって生じる経路コストの増加、すなわち遅延を予測し、許容される柔軟性（flex）を事前に配分することで探索を高速化する手法である。DFDでは、制約による推定遅延を優先的に割り当てた後、残りの柔軟性をCFD（Conflict-Based Flex Distribution）の比率に従って各エージェントに分配する。具体的な遅延の推定にはルールベースの戦略を用い、頂点やエッジの制約に対しては待機アクションによる遅延を1と仮定する。また、対称性推論に基づく廊下衝突に対しては、エージェントが廊下の出口に到達する時刻に基づいた遅延を割り当て、目標衝突に対しては、一方の制約では遅延を0、もう一方の制約では目標到達時刻を遅らせるための遅延を割り当てる。この手法を組み込んだEECBSは、分配される柔軟性の合計が最大許容値を超えないよう制御されているため、完全性と有界劣最適性が維持される。
Mixed-Strategy Flex Distribution (MFD)は、一部のエージェントが過剰に柔軟性（flex）を利用することで全体の解の質（SOC）が悪化することを防ぐための手法である。MFDは、まずDFDを用いて柔軟性の閾値を計算し、その値と他エージェントのSOCの合計がグローバルな劣最適性の境界内に収まるかを確認する。境界を超える場合はCFDに切り替えて柔軟性をゼロに設定し、再度境界条件を検証する。それでも条件を満たさない場合は、リスト内で最小のSOLBを持つCTノードを用いて柔軟性を再計算し、計算された柔軟性が正であり、かつ新たなSOCがグローバルな劣最適性の範囲内に収まる場合にのみ、その柔軟性を適用する。これら全ての条件を満たさない場合は柔軟性をゼロとして配布する。このメカニズムにより、柔軟性の過剰な利用を抑制しつつ、EECBSアルゴリズムの完全性と境界付き劣最適性を維持している。
混雑したグラフにおいてGFDが下界の改善に苦戦するという課題に対し、本研究ではFocal-A*（FA*）探索を簡略化して再設計している。提案手法では、まずFOCALリストにあるノードを優先的に展開して経路を見つけ、次にOPENリストにあるノードを展開することで、最適経路が見つかるか、あるいは現在のノードの推定コストがステップ1で見つかった経路のコストを上回るまで下界の改善を試みる。従来のFA*は展開回数が閾値を超えると最適経路を返すが、提案手法はFOCALリストに基づいた経路を返しつつ、OPENリストの展開によって得られた、少なくともFOCAL探索による下界と同等以上の値を持つ下界を併せて返す。この設計により、探索木を共有したまま、優先順位の異なるノード展開を通じて、計算の複雑さやハイパーパラメータの調整を抑えつつ下界の精度を向上させている。
MAPFベンチマークの6種類のグラフを用い、提案手法であるEECBS-MFDの性能を、既存のEECBSおよび貪欲な柔軟性配分を行うEECBS-GFDと比較して評価しています。評価指標として、解の発見効率を示す成功率と、解の質を示すグローバルな劣最適度を用いています。実験の結果、EECBS-MFDはEECBS-GFDよりも高い成功率を達成し、かつEECBSと比較してグローバルな劣最適度が増大する割合が53%と、EECBS-GFDの56%よりも低いことから、解の質と効率のバランスに優れていることが示されました。また、探索の集中度を示す指標として、探索木（CT）の深さとノード展開数の比率を定義して評価したところ、エージェント数が増加してもEECBS-MFDは高い比率を維持し、効率的な探索が可能であることが確認されました。ケーススタディでは、EECBS-GFDが過剰な柔軟性配分によりグローバルな劣最適度を増大させやすいのに対し、EECBS-MFDは柔軟性の配分を抑制することで、衝突数と劣最適度の間でより優れたトレードオフを実現し、制限時間内に解を見つけることに成功しています。一方で、混雑した迷路グラフを用いた実験では、FA*探索を併用しない限り、混雑環境における最適な柔軟性配分手法については依然として課題が残ることが示されました。
本研究では、エージェントに柔軟性を割り当てる際に貪欲な手法を用いると、衝突回避コストが最適値を超えて増加してしまう課題に対処している。この問題に対し、衝突ベースの柔軟性配分、遅延ベースの柔軟性配分、およびこれらを組み合わせた混合戦略という3つの新しい配分メカニズムを提案した。また、混雑したマルチエージェント経路探索のインスタンスにおいて、既存手法であるEECBSの探索速度を向上させるためにFA*探索を導入している。実験の結果、提案手法は最先端のEECBSよりも効率的であることが示された。