無向かつ重みなしのグラフ上で、複数のエージェントが衝突を避けながら各々の始点から終点へ移動する経路を求めるマルチエージェント経路計画（MAPF）を対象とする。目的は全エージェントの遅延の総和であるフロータイムを最小化することである。従来のAnytime MAPF手法であるMAPF-LNSは、複数の固定的な破壊ヒューリスティックから適応的に選択する仕組みを持つが、有望なヒューリスティックを特定するための探索に多大な時間を要し、かつヒューリスティック自体が非適応的であるため性能のボトルネックを解消できないという課題がある。
複数のヒューリスティックを探索・選択するプロセスを排除し、単一の適応的な破壊ヒューリスティックを用いることでMAPF-LNSの手続きを簡略化した。マルチアームバンディットの考え方を導入し、解の改善の成否に基づく二値報酬を用いて、探索中にシードエージェントの選択を最適化できるオンライン学習を実現した。これにより、従来の固定的なルールや、事前の学習データ・特徴量エンジニアリングを必要とする機械学習ベースの手法との差分を示している。
ADDRESSは、遅延が最も大きい上位K個のエージェントのみを対象とする制限付きトンプソンサンプリングを用いて、近傍生成の種となるシードエージェントを選択する。各エージェントをアームと見なし、解の改善に成功した回数と失敗した回数をベータ分布のパラメータとして保持することで、エージェントごとの改善期待値を推定する。選択されたシードエージェントの経路に基づき、ランダムウォークを用いて近傍となるエージェント群を特定し、経路の破壊と再計画を行う。新しい解のコストが改善された場合は成功、改善されなかった場合は失敗としてパラメータを更新し、継続的に学習を行う。
MAPFベンチマークセットの5種類のマップを用い、最大1000エージェント規模の大規模シナリオで評価を行った。比較対象はMAPF-LNS、MAPF-LNS2、BALANCE、およびLaCAM*である。評価指標として遅延の総和およびAUC（解の品質への到達速度）を用いた結果、大規模シナリオにおいて従来のMAPF-LNSや他の最先端手法と比較して、経路コストを少なくとも50%改善した。
Randomマップのような小規模なシナリオにおいては、エージェントのソートやトンプソンサンプリングに伴う計算オーバーヘッドが利点を上回り、既存手法に劣るというトレードオフが存在する。今後の課題として、エージェントの抽象化を行うことや、コスト寄与度に基づいて近傍を生成できるTSP、MILP、VRPといった他の問題クラスへの適用が挙げられる。
本研究では、大規模なマルチエージェント経路計画（MAPF）において、Large Neighborhood Search（LNS）を用いた既存手法の性能限界を改善する、ADDRESSという新しい単一破壊ヒューリスティック手法を提案している。従来のMAPF-LNSは複数の破壊ヒューリスティックを適応的に選択する仕組みを持つが、有望なヒューリスティックを特定するための探索に多大な時間を要する点や、ヒューリスティック自体が固定的なため性能のボトルネックを解消できないという課題があった。ADDRESSは、経路の遅延が最も大きいエージェントの集合に対して制限付きトムソンサンプリングを適用することで、適応的な近傍生成のためのシードエージェントを選択する。MAPFベンチマークの複数のマップを用いた評価実験では、最大1000エージェント規模の大規模シナリオにおいて、従来のMAPF-LNSや他の最先端手法と比較して、経路コストを少なくとも50%改善している。
マルチエージェント経路探索（MAPF）において、総移動時間や完了時間の最小化を目指す最適解の算出はNP困難であり、大規模な問題へのスケーラビリティが課題となっている。既存のAnytime MAPF手法であるMAPF-LNSは、限られた時間内で高品質な解を得るために、複数の固定的な破壊ヒューリスティックから適応的に選択する仕組みを用いるが、有望なヒューリスティックを特定するために多大な探索時間を要するというボトルネックがある。本研究では、単一の適応的な破壊ヒューリスティックを用いる手法であるADDRESSを提案する。ADDRESSは、遅延が最も大きいエージェントの集合に対して制限付きトンプソンサンプリングを適用することで、近傍生成の種となるエージェントを選択する。MAPFベンチマークを用いた評価実験では、最大1000エージェント規模の大規模シナリオにおいて、従来のMAPF-LNSや他の最先端手法と比較してコストを少なくとも50%改善した。
MAPFは、無向かつ重みなしのグラフ上で、複数のエージェントが衝突を避けながら各々の始点から終点へ移動する経路を求める問題である。経路の遅延は、その経路の長さと最短経路の長さとの差として定義され、全エージェントの遅延の総和であるフロータイムを最小化することが目的となる。Anytime MAPFでは、与えられた時間予算内で解の質を逐次向上させることが求められ、最終的な解の質に到達する速さの指標としてAUCが用いられる。現在の主流手法であるMAPF-LNSは、優先度付き計画法を用いて初期解を得た後、近傍の経路を破壊して再計画するプロセスを繰り返すことで解を改善する。既存のLNSでは、エージェントのランダム選択、遅延の大きいエージェントを中心とするエージェントベース、および次数が2より大きい頂点周辺を対象とするマップベースの3種類の破壊ヒューリスティックが用いられるが、これらはルールやランダム性の度合いが固定されている。また、本研究の背景として、未知の報酬分布を持つ選択肢から期待報酬を最大化するマルチアームバンディット問題が挙げられ、探索と活用を両立させるThompson Samplingやepsilon-Greedyといったアルゴリズムが検討対象となる。
近年、マルチアームバンディット（MAB）は、巡回セールスマン問題や混合整数線形計画法などの最適化アルゴリズムにおける破壊ヒューリスティックの選択に利用されており、多くの場合、複数の重み付け項を持つ複雑な報酬関数を用いて学習が行われます。既存のMAPF-LNS手法であるBALANCEは、二段階のトンプソンサンプリングを用いて近傍サイズと破壊ヒューリスティックの両方を適応させますが、提案手法は単一の適応的な破壊ヒューリスティックを用いることで、MAPF-LNSの手続きを簡略化しています。この提案手法は、最も遅延しているエージェントの集合からシードとなるエージェントを選択するために、単純な二値報酬を用いた制限付きトンプソンサンプリングを活用しており、TSPやVRPなどの他の問題クラスへの適用も可能です。また、機械学習を用いた既存のMAPF-LNS手法は、事前に学習されたモデルを用いて固定的な近傍を選択するため、探索中の適応ができず、事前のデータ収集や特徴量エンジニアリングを必要とします。これに対し、提案手法はMABによるオンライン学習に焦点を当てており、解の品質が改善したか否かを示す二値の報酬信号に基づいて、探索中に即座に破壊ヒューリスティックを調整できます。
ADDRESSは、マルチエージェント経路探索（MAPF）における大規模な問題に対し、適応的な破壊・修復手法を用いるLNS（Large Neighborhood Search）の改良版である。従来の、遅延が最大のエージェントを貪欲に選択する手法は、全エージェントを探索する必要があり大規模シナリオでボトルネックとなるが、ADDRESSではマルチアームバンディット（MAB）の考えを導入してこれを解決している。具体的には、各エージェントをアームと見なし、解の改善に成功した回数と失敗した回数をベータ分布のパラメータとして保持することで、エージェントごとの改善期待値を推定する。探索の効率化のため、遅延が大きい上位K個のエージェントのみを対象とする制限付きトンプソンサンプリングを採用しており、これらの中からサンプリング値が最大となるエージェントをシードとして選択する。選択されたシードエージェントの経路に基づき、ランダムウォークを用いて近傍となるエージェント群を特定し、破壊・修復操作を行う。このプロセスにおいて、新しい解のコストが改善された場合は成功としてパラメータを更新し、改善されなかった場合は失敗として更新することで、継続的に最適なシード選択を学習する。
提案手法であるADDRESSを、異なる構造と規模を持つ5種類のマップを用いて評価した。ADDRESSは、多腕バンディットアルゴリズムとしてThompson Samplingまたはepsilon-Greedyを用い、LNS（Large Neighborhood Search）の近傍生成に最適なシードエージェントを選択する手法である。実験の結果、WarehouseやCityのような大規模なシナリオにおいて、ADDRESSはMAPF-LNS、MAPF-LNS2、BALANCE、LaCAM*といった既存手法と比較して、遅延の総和を大幅に削減できることが示された。ADDRESSは、効果の低い破壊ヒューリスティックの探索や全エージェントの走査を回避してシードエージェントの選択を直接最適化するため、計算資源を効率的に活用できる。一方で、Randomマップのような小規模なシナリオでは、エージェントのソートやThompson Samplingによる計算負荷が利点を上回り、既存手法に劣るという結果が得られた。また、ADDRESSをMAPF-LNSの破壊ヒューリスティックの一つとして組み込んだ場合でも、他の静的なヒューリスティックより迅速に優先的に選択されるほど高い有効性を示している。
本研究では、MAPF-LNSの単一破壊ヒューリスティック変種としてADDRESSを提案した。ADDRESSは、最も遅延が大きいエージェントの集合に対して制限付きトンプソンサンプリングを適用することで、適応的なLNS近傍生成のためのシードエージェントを選択し、複数の静的な破壊ヒューリスティックを探索する時間的コストを削減する。最大1,000エージェント規模の大規模シナリオにおける実験の結果、ADDRESSはMAPF-LNS、MAPF-LNS2、BALANCE、LaCAM*といった既存のAnytime MAPFアルゴリズムを大幅に上回る性能を示した。トンプソンサンプリングと遅延に基づくランキングを組み合わせることで、時間の経過とともに経路が短縮されたエージェントを効率的にフィルタリングし、有望な候補に集中して学習することが可能となる。また、epsilon-Greedyを用いた手法も既存手法を上回る性能を示しており、他の多腕バンディットアルゴリズムの適用可能性が示されている。今後の課題として、エージェントの抽象化や、コスト寄与度に基づいて近傍を生成できるTSP、MILP、VRPといった他の問題クラスへの適用が挙げられる。