マルチエージェント経路探索 (MAPF) は、2Dグリッドマップ上で複数のエージェントが衝突を避けながら各々の目標地点へ移動する経路を求める問題である。従来の評価手法は、人間が設計した特定のベンチマークマップに依存しており、アルゴリズムが限定的なシナリオに過学習したり、特定のマップ構造における性能の長所や短所を十分に特定できなかったりするという課題がある。
レイアウト最適化の知見を MAPF の評価に応用し、QD アルゴリズムを用いてアルゴリズムの性能差や弱点を引き出す多様なマップを自動生成する手法を確立した。単一アルゴリズムの困難なケースの特定だけでなく、2つのアルゴリズム間の性能差を最大化するマップを生成することで、既存のベンチマークでは困難だった公平かつ詳細な比較を可能にした。
連続的な探索領域に適した QD アルゴリズムである CMA-MAE を用い、NCA ジェネレータのパラメータを最適化することで多様なマップを生成する。NCA は畳み込みニューラルネットワークを用いて局所的なルールを表現し、複雑なマップ構造を生成する。生成されたマップは、空き領域の接続性と障害物数の制約を満たすよう、混合整数線形計画法 (MILP) ソルバーによって最小限の修正が加えられる。評価プロセスでは、生成されたマップ上で MAPF アルゴリズムを実行し、CPU 実行時間や正則化成功率 (RSR) を用いて、アルゴリズムの困難さやアルゴリズム間の性能差を最大化するようにアーカイブを更新する。
CBS、EECBS、PBS、LaCAM3、PIBT、LTF の 6 つのアルゴリズムを対象に、32×32 および 64×64 のマップサイズで検証を行った。評価指標には、CPU 実行時間、正則化成功率、障害物数、タイルパターンの KL ダイバージェンスを用いた。実験の結果、LaCAM3 は既存ベンチマークでは 99% の解決率を誇るが、長い廊下と狭い入り口を持つマップでは実行時間が不足することが判明した。また、PBS は特定のマップ構造において、単なる時間切れではなく解自体を見つけられない不完全性を示すことが確認された。アルゴリズム間の比較では、EECBS と PBS の優位性がマップの入り口構造によって入れ替わることや、障害物密度が 50% を超える環境では PIBT が LTF よりも平均で 5% から 10% 高い成功率を示すことが数値的に示された。
本フレームワークはモジュール構造であるため、目的関数や多様性指標をカスタマイズすることで、容易なマップの生成や複数アルゴリズムの順位付けへの拡張が可能である。今後の課題として、エージェント数、マップサイズ、開始・目標地点の構成を変化させた、より包括的な評価設定への拡張が挙げられる。
QD-MAPPERは、Quality Diversity (QD) アルゴリズムとNeural Cellular Automata (NCA) を組み合わせることで、多様なマップを自動生成し、マルチエージェント経路探索（MAPF）アルゴリズムを包括的に評価するフレームワークです。従来のMAPF評価は人間が設計した特定のマップセットに依存しており、アルゴリズムが限定的なシナリオに過学習する課題がありましたが、本手法はパターンの異なる多様なマップを生成することで、アルゴリズムの性能をより深く理解することを可能にします。このフレームワークを用いることで、探索ベース、優先度ベース、ルールベース、学習ベースといった異なる種類のMAPFアルゴリズム間において、実行時間や成功率の差異を検出し、公平な比較を行うことができます。実験を通じて、各アルゴリズムがどのようなマップパターンにおいて優れているか、あるいは実行時間や成功率にどのような違いがあるかを特定できるため、アルゴリズムの選択や設計における知見を提供します。
本研究では、多様なマップを生成することでマルチエージェント経路探索（MAPF）アルゴリズムの性能を評価するフレームワークであるQD-MAPPERを提案する。従来の人間が設計した固定的なベンチマークマップでは、アルゴリズムの長所と短所を十分に特定できないという課題がある。これに対し、提案手法はQuality Diversity（QD）アルゴリズムを用いて、目的関数と多様性指標を最適化することで、高品質かつ多様なマップを生成する。具体的には、畳み込みニューラルネットワークを用いて局所的なルールを表現するニューラルセルオートマトン（NCA）をレイアウト最適化に応用し、複雑な構造を生成する。6つの代表的なMAPFアルゴリズムを用いた評価では、既存のベンチマークでは解決可能とされていたアルゴリズムが時間切れとなるマップや、アルゴリズムが解を見つけられない不完全性を示すマップを特定するなど、新たな知見を得ている。また、本フレームワークには、単一のアルゴリズムを評価する構成や、2つのアルゴリズムを比較する構成といった具体的な実現方法が示されている。
マルチエージェント経路探索（MAPF）は、連結された2Dグリッドマップ上で、複数のエージェントが衝突を避けながら各々の開始地点から目標地点まで移動する経路を求める問題であり、全エージェントの移動時間の総和であるsum-of-costの最小化を目的とする。既存のMAPFアルゴリズムは、探索ベースのCBSやEECBS、優先度ベースのPBS、ルールベースのPIBTやLaCAM3、学習ベースのLTFといった複数のカテゴリに分類される。従来の評価では固定されたベンチマークマップが用いられてきたが、これらはマップのパターンやサイズが限定的であるため、長い廊下や狭い入り口といった特定の条件下におけるアルゴリズムの特性を十分に明らかにできない課題がある。本研究では、Quality Diversity（QD）アルゴリズムを用いて、多様な難易度を持つマップを自動生成することで、アルゴリズムの性能を詳細に評価する。具体的には、連続的な探索領域に特化したQDアルゴリズムであるCMA-MAEを採用し、Neural Cellular Automata（NCA）を介してマップ生成器を最適化することで、多様で規則的なパターンを持つマップの生成を行う。
QD-MAPPERは、Quality Diversity（QD）の枠組みを用いて、マルチエージェント経路探索（MAPF）アルゴリズムを多様なマップ上で自動評価する手法です。CMA-MAEを用いて、畳み込みニューラルネットワークを用いたNCAジェネレータのパラメータを最適化することで、多様なマップを生成します。NCAが生成したマップは、空き領域の接続性と障害物数の範囲を保証するために混合整数線形計画法（MILP）ソルバーで修正され、その際、元のマップのパターンを維持するようハミング距離が最小化されます。評価プロセスでは、生成されたマップ上で複数のMAPFインスタンスを実行し、特定のアルゴリズムのCPU実行時間や正則化成功率（RSR）などの指標に基づき、アルゴリズムの困難さや二つのアルゴリズム間の性能差を最大化するように学習が進みます。多様性の指標には、マップの全体的な難易度に関連する障害物数や、局所的なパターンの多様性を示すタイルパターンのKLダイバージェンスが採用されています。
QD-MAPPERを用いて、CBS、EECBS、PBS、LaCAM3、PIBT、LTFの各マルチエージェント経路探索（MAPF）アルゴリズムに対し、多様かつ困難なマップを自動生成する実験を行いました。実験では、マップサイズを32×32に固定し、障害物密度をマップサイズの30%から70%の範囲で変化させ、各アルゴリズムの特性に応じてエージェント数を設定しています。マップの特徴量として、3つの障害物に囲まれた1マスの空きスペースであるone-entry spaceや、2つの通路を隔てる1マスの空きスペースであるone-tile entryを定義し、計算コストや成功率に基づいて評価しました。解析の結果、CBSやEECBS、PBSなどのアルゴリズムは、長い通路やone-tile entry、one-entry spaceを多く含むマップにおいて、計算時間の増大や解の不在といった困難な状況に直面することが示されました。また、PIBTやLTFは、障害物密度が高まることや、特定の入り口パターンを持つマップにおいて成功率が低下する傾向が確認されました。さらに、マップサイズを64×64に拡張した場合でも、32×32の時と同様の分布で困難なマップを生成できることが示されています。
本研究では、あるアルゴリズムには容易だが別のアルゴリズムには困難なマップを生成するため、2つのアルゴリズム間の性能差を最大化する手法を用いて比較実験を行っています。EECBSとPBSの比較では、障害物が512個を超えるマップは両者にとって困難ですが、400個未満のマップでは、幅の広い長い廊下や入り口が一つしかない空間を持つマップにおいてEECBSが優位となり、一方で廊下の両端が開いているようなマップではPBSが優位となることが示されました。PIBTとLTFの比較では、障害物が50%未満のマップでは両者の成功率は同程度ですが、障害物が50%を超えるマップでは、入り口が一つしかない空間が多い場合にPIBTがLTFを平均で5%から10%上回る成功率を示します。200個のインスタンスを用いた検証の結果、特定のマップパターンにおいてPIBTがLTFを平均で14%上回るケースや、逆にLTFがPIBTを平均で20%上回るケースがあることが確認されました。これらの結果は、既存のベンチマークや人間が設計した倉庫マップを用いた先行研究の結論に対し、マップの構造によってアルゴリズムの優劣が異なることを示す、より包括的な比較を提供しています。
QD-MAPPERは、多様なマップを生成することでマルチエージェント経路探索（MAPF）アルゴリズムの性能を体系的に評価する、Quality Diversity（QD）アルゴリズムに基づくフレームワークである。単一アルゴリズムの評価においては、CPU実行時間の最大化や正則化成功率の最小化を目的関数とすることで、そのアルゴリズムが苦手とするマップを生成し、弱点を明らかにできる。実験の結果、PBSは長い廊下や入り口が限定的なマップにおいて、タイムアウトだけでなく解自体を返せない不完全性を示すことが判明した。また、LaCAM3も既存のベンチマークには少ない特定のパターンで苦戦し、PIBTとLTFの比較では、障害物密度が50%を超えるとPIBTが優位になる一方、密度が60%を超え複雑性が増すとLTFが優位になるという特性が示された。本手法は、インスタンス生成、アルゴリズム評価、QD最適化を分離したモジュール構造を持ち、目的関数や多様性指標をカスタマイズすることで、アルゴリズムにとって容易なマップの生成や、複数アルゴリズムの性能順位付けにも応用が可能である。