タスクが継続的に流入するLifelong Multi-Agent Path Finding（LMAPF）において、目的地を持つ「割り当て済みエージェント」と、進路確保のために移動する目的地を持たない「未割り当てエージェント」が混在するLMAPFUA問題を扱う。入力は、グラフ、エージェント集合、各エージェントの開始地点、タスクのストリーム、および同時に実行可能な最大タスク数である。従来のLMAPFでは全エージェントを常にタスクに割り当てることが一般的であったが、タスク流入率が低い場合に未割り当てエージェントをどのように活用し、スループットを向上させるかが課題であった。
未割り当てエージェントの存在を許容するLMAPFUAの汎用的なフレームワークを提案した。MAPFUAに対応したLaCAMの変種であるLaCAMUAを導入し、さらに、少なくとも1つのエージェントが目標に到達した時点で探索を打ち切るCFETという新しい終了条件を導入した。これにより、スループットを維持したまま計算時間を大幅に削減できることを示した。また、エージェント総数と同時実行タスク数の組み合わせがスループットに与える影響を体系的に調査し、意図的に未割り当てエージェントを増やすことが有効であることを明らかにした。
LaCAMUAの低レベル探索では、未割り当てエージェントの目的地をグラフ内の全頂点と見なし、隣接頂点への移動が割り当て済みエージェントの助けになる場合にのみ移動を選択する。LMAPFUAフレームワークでは、タスク完了時にエージェントを未割り当て状態に戻し、新規タスク発生時に未割り当てエージェントへ割り当てることで、常に一定数のタスクを進行させる。エージェントの割り当てには、ランダムな選択と、タスク地点に最も近いエージェントを選択するClosest手法を用いる。CFETは、最初の目標到達時に探索を停止し、即座に次回のタスク割り当てと再探索を行うことで、計算コストを抑えつつ最新の状況に基づいた経路計画を実現する。
32×32のグリッド、16×16のグリッド、Maze、Warehouseなどの異なるドメインを用いて検証を行った。評価指標はスループットとし、全エージェントを割り当て済みとする構成（AAA）と比較した。32×32のグリッドでは、エージェント総数N=600、同時タスク数C=400の構成が最も高いスループットを記録した。CFETは、従来のRHCRと比較して、1ステップあたりの計算時間が最大5倍高速であった。複雑なマップ（MazeやWarehouse）では、未割り当てエージェントを活用することで、AAA構成と比較してスループットが大幅に向上することが確認された。
エージェント総数を増やすことは、タスクに近いエージェントを割り当てやすくする利点がある一方で、環境の密度を高めて衝突を増やし、経路を長くするというトレードオフが存在する。本研究の限界として、特定の環境において割り当て済みエージェントと未割り当てエージェントの最適な数を自動的に決定する手法は確立されていない。今後の課題は、機械学習を用いた最適なエージェント構成の学習、LaCAMUAやCFETのさらなる改良、およびより複雑なタスクやタスク供給メカニズムへの拡張である。
本論文は、目標を持つ「割り当て済みエージェント」と、目標を持たず割り当て済みエージェントの進路を確保するために移動する「未割り当てエージェント」の2種類が存在する、実用的なマルチエージェント経路探索の変種であるMAPFUAを扱っています。特に、新しいタスクが継続的に発生するLifelong（生涯型）の設定において、スループットを最大化することを目的としています。著者らは、MAPFUAに対応したLaCAMの新しい変種と、LMAPFUAのための汎用的なフレームワークを提案しています。研究では、高いスループットを実現するために、利用可能なエージェントの総数と、そのうち何数を割り当て済みとするかの最適なバランスに焦点を当てています。実験の結果、割り当て済みのエージェントの一部を、将来のタスクに対してより有利な位置に移動できる未割り当てエージェントへと転換させることで、通常はより高いスループットが達成されることが示されています。
マルチエージェント経路計画（MAPF）において、タスクが継続的に発生するLifelong MAPF（LMAPF）では、完了したタスクの総数であるスループットの最大化が目的となります。本研究では、タスクの流入率が低い場合に一部のエージェントが目標を持たない「未割り当てエージェント」として存在する、Lifelong MAPF with Unassigned Agents（LMAPFUA）という設定を扱います。提案するフレームワークでは、同時に実行するタスク数を固定し、タスク完了時にエージェントを未割り当てに戻し、新規タスク発生時に未割り当てエージェントへ割り当てることで、LaCAMの新しい変種を用いて未割り当てエージェントの移動を制御します。また、最初のエージェントが目標に到達した時点で探索を停止し、即座に次回のタスク割り当てと再探索を行う新しい終了条件を導入することで、スループットを維持したまま実行時間を大幅に削減できることを示します。さらに、タスクの流入率を意図的に下げて未割り当てエージェントを増やすことが、将来のタスクへの対応力を高めスループット向上に寄与する場合があることを明らかにし、使用するエージェント数や割り当てタスク数の最適化に関する体系的な調査を行います。
MAPFUAは、グラフG=(V, E)において、特定の目的地を持つ「割り当て済みエージェント」と、目的地を持たない「未割り当てエージェント」が混在するマルチエージェント経路計画問題である。解決策は、割り当て済みエージェントが各々の目的地を通過しつつ、全エージェントの経路が衝突しないように構成される。コスト関数には、割り当て済みエージェントが目的地に到達した時刻の総和であるSST（Sum of Service Time）や、移動した未割り当てエージェントの数、全エージェントの総移動回数などが存在する。本研究では、LaCAMアルゴリズムをMAPFUAに適用したLaCAMUAを用いる。LaCAMは、各エージェントの位置の集合である構成空間を深さ優先探索する高レベル探索と、次の衝突のない構成を選択する低レベル探索の二段階で構成される。LaCAMUAの低レベル探索では、未割り当てエージェントに対してグラフ内のすべての頂点を目的地候補として扱う。具体的には、未割り当てエージェントはまず待機を選択するが、隣接頂点への移動が一つ以上の割り当て済みエージェントの移動を助ける場合には、その移動を選択する。
LMAPFUAは、継続的にタスクが発生するLifelong MAPFを拡張し、未割り当てのエージェントが存在する状況を扱うフレームワークである。この設定では、グラフ、エージェント集合、各エージェントの開始地点、タスクのストリーム、および同時に割り当て可能なタスク数Cを入力とする。アルゴリズムは、割り当てられたエージェントがタスクを完了して未割り当て状態になると、未割り当てのエージェントに新しいタスクを割り当て、その都度パス探索を実行することで、常にC個のタスクが進行している状態を維持する。エージェントの割り当てには、ランダムに選ぶ手法と、タスク地点に最も近いエージェントを選ぶClosest手法の2種類が検討されている。パス探索には、少なくとも1つのエージェントが目標に到達した時点で探索を打ち切るCFET（Conflict Free Early Termination）というLaCAMの新しいバリアントが提案されており、従来のRolling Horizon Collision Resolution（RHCR）を用いた手法と比較して、スループットを維持しつつ最大5倍の高速化を実現している。タスクの種類として、目標地点への到達（AT）、目標地点での一定時間の待機を伴う到着（AW）、および集荷と配送（PD）の3つが定義されており、それぞれに合わせたアルゴリズムの拡張がなされている。
本研究では、Lifelong Multi-Agent Path Finding (LMAPF) において、割り当て済みエージェントと未割り当てエージェントを混在させる手法（LMAPFUA）の有効性を、様々なドメインを用いて検証しました。32×32の空のグリッドを用いた実験では、全エージェントを割り当て済みとする構成と比較して、同時にタスクを実行するエージェント数（C）と、未割り当てのエージェント数を適切に分離する混合構成の方が高いスループットを達成できることが示されました。エージェントの総数（N）を増やすことは、新しいタスクに対してより近い位置にいるエージェントを割り当てることを可能にしますが、一方で環境の密度が高まり衝突が増加して経路が長くなるというトレードオフが生じます。そのため、スループットを最大化するには最適なNとCの組み合わせが存在し、例えば32×32のグリッドでは、N=600、C=400の構成が最も高いスループットを実現しました。この改善効果は、目標に到着するだけのATタスクで最も顕著であり、待機を伴うAWタスクや配送を伴うPDタスクでも確認されました。また、MazeやWarehouseなどの複雑なマップでは、未割り当てエージェントによる割り当ての最適化が経路長を短縮する効果がより強く働き、全エージェントを割り当て済みとする構成に対するスループットの向上率がさらに高まることが示されました。
本研究では、割り当てられていないエージェントが存在する生涯マルチエージェント経路探索（LMAPFUA）のための汎用的なフレームワークを提案し、LaCAMUAの新しいバリアントおよびLMAPFアルゴリズムのための新しい停止条件を導入した。実験を通じて、総エージェント数を制限することや、未割り当てのエージェントを追加することがスループットに与える影響を調査し、これらの手法が有効であることを示した。今後の課題として、与えられた環境において割り当て済みエージェントと未割り当てエージェントの最適な数を決定する手法の確立が挙げられる。また、提案したLaCAMUAの低レベル処理やCFETの停止条件といったアルゴリズムの改良に関するさらなる研究や、タスクの割り当て関数およびタスク供給メカニズムを拡張した設定への適用も検討されている。