混雑した環境において、複数のエージェントが衝突を回避しながら目的地へ到達するMAPFを対象としています。実世界のロボットシステムでは、全期間の経路を事前に計算するのではなく、限られた時間内で次の行動を決定し、実行と計画を繰り返すリアルタイムな運用が求められます。しかし、計算時間を抑えるために探索範囲を制限する従来のウィンドウ化手法は、理論的な完全性を欠いており、エージェントが動けなくなるデッドロックや、同じ状態を繰り返すライブロックに陥るという困難がありました。
既存のリアルタイム手法や、完全性を実現しつつも計算コストが高いWinC-MAPFに対し、Real-Time LaCAMは計算効率と理論的な完全性の両立を実現しました。LaCAMの深さ優先探索（DFS）を増分的な形式で活用することで、デッドロックを防ぎつつ、ミリ秒単位の極めて短い計算時間でも動作する初の完全なリアルタイムMAPF手法を提供します。
毎ステップごとに探索をゼロからやり直すのではなく、過去の探索履歴を保持した「グローバルなDFS木」を反復的に構築します。探索中に計算時間の制限に達した際は、探索中の最新の構成から現在の構成までをバックトラックすることで、次の移動先を決定します。エージェントが移動するたびに、現在の構成が常に木の根となるよう親ポインタを入れ替えるリルーティングを行います。これにより、バックトラック時に必ず現在の構成に到達できることを保証します。また、以前に訪れた構成を再訪した際には、エージェントの行動に制約を追加することで、同じ構成を繰り返し探索して停滞することを防ぎます。
標準的なベンチマークを用い、Naive Real-Time LaCAM（毎ステップ探索をやり直す手法）、PIBT、および全期間を一度に計画する全ホライゾン版LaCAMと比較しました。各反復にミリ秒単位のカットオフ時間を設定した実験において、Real-Time LaCAMはカットオフ時間に関わらず、成功率および総実行時間の両面で全ホライゾン版LaCAMと一致する結果を示しました。一方で、カットオフ時間が極めて短い場合には、近視眼的な計画となるため、解の品質が10倍から100倍程度悪化することも確認されました。また、学習済みMAPFポリシーと組み合わせることで、単独のCS-PIBTよりも高い性能が得られることも示されました。
本手法は、制約を組み込める構成生成器であればどのような設定でも動作する汎用的なフレームワークです。しかし、カットオフ時間が極端に短い設定では、解の品質が低下するというトレードオフが存在します。今後の課題として、LaCAMの制約利用とWinC-MAPFのヒューリスティック更新を統合して解の質を維持しつつ高速化することや、Engineering LaCAM*へと拡張してリアルタイムにおける解の質をさらに向上させることが挙げられます。
従来のマルチエージェント経路計画（MAPF）手法の多くは、全期間の経路を事前に計画する必要があり、計算時間が膨大になるため実世界への適用が困難でした。本研究では、限られた時間内で計画と実行を繰り返すリアルタイム計画の枠組みにおいて、初めて完全性を証明可能な手法であるReal-Time LaCAMを提案しています。この手法は、LaCAMを増分的な形式で活用することで、デッドロックやライブロックを回避しながら、ミリ秒単位の制限時間内でも混雑した環境に対して反復的な計画を可能にします。実験の結果、Real-Time LaCAMは全期間を計画するLaCAMと同等の成功率を維持しつつ、単一ステップの学習済みMAPFポリシーとも併用できることが示されました。
マルチエージェント経路計画（MAPF）は、混雑した環境下で複数のエージェントが衝突を回避する経路を求める問題であり、倉庫自動化などの分野で重要となる。実世界の応用では限られた計算時間内で次の行動を決定するリアルタイムな計画が求められ、一定の期間のみを計画するウィンドウ化手法が一般的に用いられる。しかし、既存のウィンドウ化手法の多くは理論的な完全性を欠き、デッドロックやライブロックが発生する可能性があるほか、完全性を保証する最新のフレームワークも計算に数秒を要するため、実用的なリアルタイム性は確保できていない。本研究では、深さ優先探索に基づくLaCAMを逐次的に構築するReal-Time LaCAMを提案し、理論的な完全性を実現する。実験により、Real-Time LaCAMは各反復の打ち切り時間をミリ秒単位以下に抑えつつ、全行程を計画するLaCAMと同等の成功率と実行時間を達成できることを示す。さらに、本手法が学習ベースのMAPFポリシーと併用可能であることも示す。
マルチエージェント経路計画（MAPF）のリアルタイム計画では、全期間の経路を一度に求めるのではなく、各ステップで制限時間内に最適な部分経路を探索し、実行と計画を繰り返す。既存のウィンドウ型手法は固定の探索範囲を持つが、リアルタイム手法は時間制限に合わせて探索範囲を調整する。PIBTやLNSを用いた既存のリアルタイム・ウィンドウ型ソルバーは、理論的な完全性が欠如しており、デッドロックやライブロックが発生する可能性がある。完全性を実現するWinC-MAPFフレームワークも存在するが、1ステップの計画に数秒を要する場合がある。提案手法であるReal-Time LaCAMは、LaCAMの探索木を再利用し、以前に訪れた構成を再訪した際に制約を追加することで、PIBTのような高速な手法を用いながらもデッドロックを防ぎ、完全性を保証する。この手法は、単一エージェントの探索手法であるTime-Bounded A*をMAPFに拡張したものと解釈できる。
Real-Time LaCAMは、毎ステップごとにLaCAMの深さ優先探索（DFS）をゼロからやり直すのではなく、過去の探索履歴を保持した「グローバルなDFS木」を反復的に構築・実行する手法である。各反復において、探索は前回の続きから開始され、計算時間の制限に達した際に、探索中の最新の構成から現在の構成までをバックトラックすることで、次の移動先を決定する。探索が進むたびに、現在の構成が常に木の根となるように親ポインタを入れ替える「リルーティング」を行うことで、バックトラック時に必ず現在の構成に到達できることを保証している。この手法は、探索済みの構成を記憶し続けるため、毎ステップ再計算を行うナイーブな手法とは異なり、異なる反復間で同じ構成を繰り返し探索して停滞することを防ぐことができる。理論的には、リルーティングは探索構成や制約に影響を与えないため、フルホライゾン版のLaCAMと同様の完全性を持ち、全反復の合計計算時間もフルホライゾン版とほぼ同等である。実験の結果、Real-Time LaCAMは、タイムアウト時間を短く設定した場合においても、ナイーブな手法と比較して高い成功率を示すことが確認されている。
標準的なベンチマークのサブセットを用い、提案手法であるReal-Time LaCAMを、毎反復ゼロから再計画を行うNaive Real-Time LaCAM、PIBT、および全ホライゾンを対象とするLaCAMと比較した。実験では、各反復にミリ秒単位のカットオフ時間を設け、累積の計画タイムアウトを60秒に設定して、計画と実行を交互に行う手法と、一度のみ計画を行う手法を評価した。結果として、Real-Time LaCAMはカットオフ時間に関わらず、全ホライゾンLaCAMと同一の深さ優先探索木を構築するため、成功率や実行時間の面では全ホライゾン版と完全に一致することが確認された。一方で、カットオフ時間が極めて短い場合、特定のマップにおいて近視眼的な計画となることで、解の品質が10倍から100倍程度悪化することが示された。また、学習済みMAPFポリシーの予測結果をPIBTのバックワード・ダイクストラ・ヒューリスティックの代わりに用いることで、Real-Time LaCAMを衝突回避のポストプロセスとして統合でき、既存のCS-PIBTよりも性能を向上させることが示された。
Real-Time LaCAMは、制約を組み込める構成生成器であればどのような設定でも動作し、制約のあるエージェントを特定の場所に固定することで、未制約のエージェントのみの構成生成問題へと簡略化できる。本手法は、任意のMAPFプランナーをウィンドウ化された計画において完全性を持つものへと変換するフレームワークと見なすことができ、最適ソルバーやヒューリスティックの更新、エージェントのグループ分割を必要とするWinC-MAPFとは異なり、制約の適用のみで動作する。制約はどのエージェントが動くかを明示的に指示するため、ヒューリスティックによるコスト評価よりも迅速に新しい構成を探索できる可能性がある。将来的な課題として、LaCAMの制約利用とWinC-MAPFのヒューリスティック更新を統合し、解の質を維持しつつ高速化を図ることや、Engineering LaCAM*へと拡張してリアルタイムにおける解の質を向上させることが挙げられる。Real-Time LaCAMは、完全性を保証する初のリアルタイムMAPF手法であり、既存手法がデッドロックやライブロックに陥るようなミリ秒単位の極めて短い反復時間制限下においても、高い成功率を示す。