複数のエージェントが衝突を避けながら、全エージェントの移動コストの総和を最小化する経路を求めるマルチエージェント経路探索（MAPF）問題を対象とする。CBSは、高レベルでの制約ツリー探索と低レベルでの経路再計画を繰り返すが、ツリーを拡張する際にどの衝突を優先的に解決するかという衝突選択の戦略が、探索木のサイズや実行時間に影響を与える。従来の衝突分類に基づく手法では、探索効率を十分に高めることが困難であった。
既存のヒューリスティック手法に対し、高精度だが計算コストが高いオラクルの決定を教師あり学習によって模倣する、データ駆動型のランキング関数を導入した点が新規である。混合整数線形計画法（MILP）の変数選択の知見を応用し、衝突を特徴づける問題固有の詳細な情報を活用することで、従来のMILP向け機械学習手法よりも高度な衝突選択を実現している。
まず、衝突解決後の子ノードにおける「コストと推定コストの和」の最小値をスコアとし、この値の下限を最大化する衝突を選択するオラクルを定義する。次に、衝突の種類、エージェントや頂点の統計量、重み付き依存グラフ（WDG）の性質などを含む67次元の特徴量を用いて、オラクルのランキングに基づき上位20%の衝突に正解ラベルを付与したデータセットを作成する。最後に、サポートベクターマシンを用いて、正解の順序が逆転するペアの割合を最小化するように線形ランキング関数を学習し、この関数を用いて衝突の優先順位を決定する。
Warehouse、Room、Maze、Random、City、Gameの6種類のマップを用い、WDGヒューリスティックを用いたCBSH2を比較対象として評価した。評価指標には成功率、実行時間、制約ツリーのノード数、およびPAR10スコアを用いた。同一マップで学習する手法（ML-S）と未知のマップで学習する手法（ML-O）の両方において、共通して解けるインスタンスに対し、CBSH2と比較して実行時間で10.3%から68.2%（Cityマップの改善率を含む）、制約ツリーのサイズで11.6%から68.2%の改善を達成した。
提案手法は、学習時と同じグラフだけでなく、未知のグラフやエージェント数が異なる環境に対しても汎化できることが示されている。一方で、同一マップで学習するML-Sは、未知のマップで学習するML-Oよりも実行時間において優れた結果を示す傾向がある。今後の課題として、学習対象となるより優れたオラクルの発見や、対称性の打破といった最新の技術を機械学習による衝突選択の枠組みに統合することが挙げられる。
マルチエージェント経路探索における最先端アルゴリズムであるConflict-Based Search（CBS）は、衝突を検出し、問題を2つの部分問題に分割することで解決を試みる手法である。従来手法では、衝突を3つのクラスに分類し、優先度の高いクラスから順に解決対象を選択していたが、本研究では探索木のサイズをより小さくするために、最適な衝突を選択するためのオラクルを提案している。このオラクルは計算に時間を要するという課題があるため、オラクルの決定を模倣し、線形ランキング関数を用いて迅速かつ正確に衝突を選択する機械学習フレームワークを導入している。ベンチマークマップを用いた実験の結果、提案するML-guided CBSは、既存の最先端のCBSソルバーと比較して、成功率、探索木のサイズ、および実行時間のすべてにおいて改善を示した。
マルチエージェント経路探索（MAPF）において、総コストやメイクスパンを最小化する衝突のない経路を求める問題はNP困難であるが、Conflict-Based Search（CBS）は最適解を得るための主要なアルゴリズムの一つである。CBSは、高レベルでの制約ツリー（CT）に対する最良優先探索と、低レベルでの制約を考慮した経路再計画からなる二段階の探索構造を持ち、CTのノードを拡張する際にどの衝突を解消するかという衝突選択の戦略が、CTのサイズや実行時間に大きな影響を与える。本研究では、各衝突に対して1ステップ先読みのヒューリスティックを計算する、高精度だが計算コストの高い新しい衝突選択オラクルを提案する。このオラクルの計算負荷を軽減するため、混合整数線形計画法（MILP）の分岐における変数選択の知見を応用し、オラクルの決定を模倣するランキング関数を教師あり学習によって構築するデータ駆動型のフレームワークを提案する。この手法は、衝突を特徴づける問題固有の情報を活用することで、従来のMILP向け機械学習手法よりも詳細な情報を扱える点が特徴である。学習済みのランキング関数を用いることで、未知のインスタンスやグラフに対しても、探索時間とCTサイズの双方を削減しつつ高い成功率を実現する。
無向で重みのないグラフにおいて、複数のエージェントに対して衝突のない経路集合を求めるマルチエージェント経路探索（MAPF）問題を定義している。各エージェントには開始頂点と目標頂点が割り当てられ、時間は離散的なステップとして扱われ、各ステップでエージェントは隣接頂点への移動またはその場での待機を選択できる。エージェントのコストは、目標頂点に到達して移動が停止するまでのタイムステップ数として定義される。衝突には、特定の時刻に2つのエージェントが同じ頂点を占有する頂点衝突と、2つのエージェントが隣接する頂点間を逆方向に移動する際に発生するエッジ衝突の2種類が存在する。本研究の目的は、全エージェントのコストの総和を最小化する、衝突のない経路集合を見つけることである。
Conflict-Based Search (CBS)は、高レベルの衝突ツリー（CT）探索と、低レベルの個別経路再計画からなる2段階のアルゴリズムです。各CTノードは、制約集合、制約を満たす各エージェントの最小コスト経路の集合、経路の総コスト、および経路間で発生する衝突の集合を保持します。衝突が発生した際、CBSは衝突するエージェントのいずれかに頂点制約またはエッジ制約を課した2つの子ノードを生成して探索を進めることで、完全性と最適性を保証します。関連手法として、ICBSは多値決定グラフ（MDD）を用いて衝突をカーディナル、セミカーディナル、ノンカーディナルの3種類に分類し、コストの増加が見込めるカーディナル衝突を優先することで効率化を図っています。また、CBSHやCBSH2は、衝突グラフや重み付きペアワイズ依存グラフを用いて、高レベル探索の指針となる下限コストをより厳密に推定するヒューリスティックを用います。提案手法は、これら既存のヒューリスティックの知見をラベルや特徴量として活用し、オフライン学習によって未知のインスタンスに対しても効率的な衝突選択戦略を適用できる機械学習モデルを構築するものです。
衝突選択オラクルとは、Conflict-Based Search（CBS）において、現在の制約木ノードに含まれる衝突集合に対し、各衝突のスコアに基づいて解決すべき優先順位を決定するランキング関数である。本研究では3つのオラクルを定義しており、一つ目のO0はMDDを用いて衝突を基数、半基数、非基数の順にランク付けし、同点の場合は最小の時間ステップを優先する。二つ目のO1は、衝突を解決して生成される2つの子ノードについて、それぞれのノードのコストとWDGヒューリスティックによる推定コストの和の、より小さい方の値をスコアとする。O1はスコアが大きい順にランク付けを行うことで、解のコストの下限を最大限に高めることを目的としている。三つ目のO2は、衝突解決後の子ノードに含まれる衝突数のうち、より少ない方の値をスコアとし、この値が小さい順にランク付けすることで、次世代の衝突数を最小化することを目指す。実験の結果、全体としてO1が最も優れた性能を示したため、本研究ではO1を模倣するランキング関数の学習に焦点を当てている。提案手法であるML-Sは、O1を用いたCBSH2よりも制約木のサイズは大きくなるものの、実行時間においては最も優れた結果を得ている。
本手法は、Conflict-Based Search (CBS) において解決すべき衝突を決定するためのランキング関数を学習するフレームワークである。プロセスは、オラクルによる衝突の順位付けから特徴量とラベルを取得するデータ収集、ペアワイズ損失を最小化するように線形ランキング関数を学習するモデル学習、そして学習済み関数をCBSの探索プロセスに組み込むML誘導探索の3段階で構成される。ラベル付けには、オラクルのスコアにおいて上位20%に含まれる衝突に1、それ以外に0を割り当てるバイナリ手法を採用しており、これにより低スコアの衝突の正確な順位付けという不要なタスクを避け、高ランクの衝突の識別に集中させている。特徴量は、衝突の種類、エージェントや頂点の統計量、MDD（Multi-Dimensional Disjunctive）やWDG（Weighted Dependency Graph）の性質など、計67次元のベクトルで構成される。モデルの学習には、正解ラベルの順序が逆転しているペアの割合を最小化するサポートベクターマシンを用いたアプローチが用いられる。実験では、学習時と同じグラフおよび未知のグラフの両方で評価が行われ、CBSH2+O0と比較して、探索ノード数や実行時間の面で優れた性能を示すことが示されている。
本研究では、Conflict-Based Search (CBS) における衝突選択の効率化を目的とした、機械学習に基づく2つの手法、ML-SおよびML-Oの有効性を検証しています。実験では、Warehouse、Room、Maze、Random、City、Gameの6種類の異なるマップを用い、WDGヒューリスティックを用いたCBSH2を比較対象として、成功率、実行時間、衝突ツリー（CT）のノード数、およびPAR10スコアを評価しました。ML-Sは同一マップのデータを用いて学習し、ML-Oは他のマップのデータを用いて学習する手法であり、実験の結果、ML-SとML-Oはほぼ全てのマップとエージェント数の設定においてCBSH2を上回る性能を示しました。全手法が共通して解けたインスタンスにおいて、ML-SおよびML-OはCBSH2と比較して、実行時間で10.3%から64.4%、CTサイズで13.0%から68.2%の改善を達成しました。ML-Oは学習時に未知のマップを使用しているにもかかわらず、ML-Sに匹敵する、あるいは一部のマップではML-Sを上回る高い汎用性を示しました。学習されたランキング関数の特徴量分析からは、重み付き依存グラフ（WDG）におけるエージェント間のエッジの重み、衝突のタイプ、および解決済みの衝突数などが重要な指標として特定されました。
本研究では、Conflict-Based Search (CBS) における衝突選択を最適化するための、初の機械学習フレームワークを提案した。この手法は、子ノードにおいて最適コストの最小下界を最も厳しく制約する衝突を選択する、理想的な選択器であるオラクルの決定を模倣することを目的としている。実験の結果、学習されたランキング関数は、固定されたグラフだけでなく未知のグラフにおいても、エージェント数の変化に対して汎化できることが示された。今後の展望として、学習の対象となるより優れたオラクルの発見や、対称性の打破などの最新技術を、提案した機械学習による衝突選択の枠組みに統合することが挙げられる。