グラフ上の複数のエージェントが衝突を避けながら各々の目標地点へ移動するマルチエージェント経路探索（MAPF）を対象とする。既存のLaCAMは、構成生成器であるPIBTが狭い通路などでライブロックを引き起こし、探索コストが膨大になる課題がある。また、従来のAnytime手法は最適性に収束するものの、スケーラビリティに欠け、大規模な問題で初期解の導出に失敗しやすいという困難がある。
既存のLaCAMに対し、遷移コストの累積を解のコストとして扱うことで、計算資源が許す限り解の質を向上させ、最終的に最適解へと収束する性質を持つLaCAM*を導入した。さらに、PIBTにスワップ操作を組み込むことで、エージェント間の位置入れ替えを可能にし、構成生成の効率を改善した。
LaCAM*は、目標構成を発見した後も探索を継続し、既知の構成に再到達した際にはダイクストラ法を用いて累積コストと親ノードを更新することで、最短経路を維持する。探索の効率化のため、目標までの推定コストが現在のノードの推定コストを上回る場合にノードを破棄する枝刈りを行う。改良された構成生成器では、2段階のシミュレーションを用いてスワップの必要性と実行可能性を判定する。スワップが必要な場合は、エージェントの移動候補の順序を反転させて一時的に目標から遠ざかる動きをさせ、エージェント間の位置入れ替えを誘発する。
13,900個のベンチマークインスタンスを用いた実験において、標準的なデスクトップPCを使用し、最大1,000エージェントを含む問題の99%を10秒以内に解いた。エージェント数が2、4、6の場合、従来のPIBTを用いたLaCAMの探索反復回数がそれぞれ23,907回、287,440回、287,440回であったのに対し、改良型PIBTを用いた場合はそれぞれ8回、8回、8回へと減少した。小規模な複雑なインスタンスや高密度なシナリオにおいても、既存手法を上回るスケーラビリティを示した。
改良された構成生成器には、パターン検出器による実行時間のオーバーヘッドが存在する。今後の課題として、より最適に近い初期解を出力できる構成生成器の開発や、LaCAM*の収束速度の向上、およびマルチロボット運動計画などの派生問題への応用が挙げられる。
本研究は、遅延的な後続ノード生成を用いることで探索コストを大幅に削減する、マルチエージェント経路探索（MAPF）のためのアルゴリズムであるLaCAMを拡張するものである。第一の提案として、解のコストが遷移コストの累積である場合に、最終的に最適解へと収束するAnytime版のLaCAM*を導入している。第二の提案として、初期解をより迅速に取得するために後続ノードの生成プロセスを改善している。標準的なデスクトップPCを用いた実験では、LaCAM*は最大1,000エージェントを含むMAPFベンチマークのインスタンスの99%を、最適解への収束性を保証しつつ10秒以内に非最適解として解くことが示された。
マルチエージェント経路探索（MAPF）において、解の完全性や最適性と、計算速度やスケーラビリティの間のトレードオフを解消するため、既存のLaCAMアルゴリズムを拡張したLaCAM*を提案する。LaCAM*は、遷移コストの累積を解のコストとして扱うことで、最終的に最適解に収束するAnytimeアルゴリズムとしての性質を持ち、計算資源が許す限り解の質を向上させることが可能である。さらに、初期解を迅速に得るために、後続状態の生成プロセスにおいてPIBTアルゴリズムの調整を行う改良を加えている。13,900個のベンチマークインスタンスを用いた実験では、標準的なデスクトップPCを用いて、10秒以内に99.0%のインスタンスに対して劣最適解を算出することに成功した。この結果は、既存の主要なアルゴリズムと比較して、解の発見率と計算速度の両面で高い性能を示している。
マルチエージェント経路探索（MAPF）は、グラフ上の複数のエージェントが衝突を避けながら各々の目標地点へ移動する問題であり、本稿では全エージェントの現在位置の集合である構成、および構成間の接続性と衝突（頂点衝突およびエッジ衝突）を定義している。最適化指標には、移動コストの総和である燃料消費量や、目標に到達した後に目標に留まらないコストを数えるsum-of-lossなどが用いられる。提案手法の基盤となるLaCAMは、エージェント数に対して指数関数的に増大する構成の分岐数問題を解決するため、構成生成器を利用するグラフ探索アルゴリズムである。LaCAMは、各探索ノードに制約ツリーを持たせ、低レベルの探索によって制約を段階的に発展させることで、高レベルの探索において効率的に接続された構成を生成する。構成生成器として用いられるPIBTは、優先権継承（priority inheritance）という仕組みを持つ再帰的なアルゴリズムであり、あるエージェントが移動先を決定する際に、その地点を占有する可能性がある他のエージェントの移動先を事前に決定しようと試みることで、衝突を回避しながら構成を生成する。
LaCAM*は、目標構成が見つかった後も探索を継続し、解の品質を継続的に向上させるAnytimeアルゴリズムである。既存手法との主な違いは、目標構成が見つかった際に即座に終了せず、既知の構成に再到達した際に親ノードの関係や累積コストを必要に応じて書き換える点にある。各探索ノードは、開始地点からの累積コストを示すg値、親ノード、および隣接する構成の集合を保持する。既知の構成に到達した際は、ダイクストラ法を用いてg値と親ノードを更新することで、最短経路を維持する。探索の効率化のため、目標構成が見つかった後は、目標までの推定コストの合計が探索中のノードの推定コストを上回る場合に、そのノードを破棄する枝刈りを行う。これにより、探索を中断した時点での解を返しつつ、最終的には最適な解を導出することが可能である。
LaCAMの性能は構成生成器に大きく依存するが、従来のPIBTは狭い通路などのシナリオにおいて、エージェントが目標地点を周期的に行き来するだけのライブロック状態を引き起こし、LaCAMの探索コストを増大させる課題があった。本研究では、次数が3以上の頂点を利用して2つのエージェントの位置を入れ替えるスワップ操作をPIBTに組み込んだ改良版を提案している。この改良版では、スワップが必要かつ可能である場合にエージェントの移動候補の順序を反転させ、エージェントをあえて目標から遠ざけることでスワップを誘発する。具体的には、エージェント間の移動をシミュレーションする2段階の検証プロセスにより、スワップの必要性と実行可能性を判定している。実験結果として、エージェント数が2、4、6の場合において、従来のPIBTを用いたLaCAMの探索反復回数がそれぞれ23,907回、287,440回と膨大であったのに対し、提案手法を用いることでそれぞれ8回へと削減されることが示された。
本評価では、提案手法であるLaCAM*の性能を複数の観点から検証しています。改善された構成ジェネレータを用いることで、従来のPIBTと比較して探索イテレーション数が劇的に減少し、大規模なインスタンスにおける計算時間の短縮に寄与しますが、パターン検出器による実行時間のオーバーヘッドも確認されました。また、冗長な探索ノードを破棄する手法は、ジェネレータの種類に関わらず探索の負荷を大幅に削減し、特に改善された構成ジェネレータと組み合わせた際に高い効果を発揮します。小規模で複雑なインスタンスにおいて、LaCAM*は初期解として（準）最適解を即座に発見し、既存のベースライン手法を上回る性能を示しました。MAPFベンチマークを用いた大規模な評価では、多くのマップにおいて10秒以内に他のアルゴリズムを凌駕する解を導出し、極めて高密度なシナリオにおいても高いスケーラビリティを実証しています。一方で、エージェント数が多い大規模なインスタンスでは、既知の構成間に新たな接続を見つけることが困難になるため、解の精緻化の収束速度が低下する傾向があります。
本研究は、マルチエージェント経路探索（MAPF）における解の実行可能性、解の質、および計算コストのトレードオフを解消するため、既存手法であるLaCAMに対し、最終的に最適解へ収束するLaCAM*と、効果的な構成生成器という2つの拡張を提案した。既存のAnytime MAPFアルゴリズムは最適性に収束するものの、スケーラビリティに欠け、初期解の導出に失敗することが多いという課題がある。提案手法は、探索木構造の書き換えに着想を得たアプローチや、PIBTにスワップ操作を組み込む手法を取り入れている。今後の展望として、より最適に近い初期解を出力できる構成生成器の開発や、LaCAM*の収束速度の向上、さらにはマルチロボット運動計画などのMAPFの派生問題や、他のグラフ経路探索領域への応用が挙げられる。