物流倉庫のような、エージェントに次々と新しい目標が割り当てられるLifelong MAPF問題を対象とする。従来のRolling-Horizon Collision Resolution (RHCR) 等の手法では、マップサイズやエージェント密度の増加に伴い、実行時間の指数関数的な増大、デッドロックの発生、および不要な経路再計算（rerouting）が課題となっていた。本研究は、有向グラフとしてのハイウェイ構造を導入することで、これらの問題を解決することを目指している。
One-shot MAPFで用いられてきたハイウェイの概念を、Lifelong MAPFの枠組みへと初めて拡張し、その有効性を明らかにした。単に移動を制限するだけでなく、デッドロックやreroutingを数学的に回避・抑制する特性を持つ2つのハイウェイ適用手法を提案している。これにより、計算効率の向上とスループットの維持、あるいは高密度環境下でのスループット向上という新たな知見を提供している。
ハイウェイを特定の方向性を持つ地点の列（Corridor）と定義し、以下の2手法を提案する。一つ目はStrict-limit Highwayであり、エッジの接続性をハイウェイの方向に限定したサブグラフ $\mathcal{G}_{\text{highway}}$ に置き換えることで、逆方向への移動を物理的に禁止する。二つ目はSoft-limit Highwayであり、ハイウェイの逆方向へ移動するエッジのコストを $\alpha$ 倍（$\alpha > 1$）に増大させることで、低レベルソルバーがハイウェイに沿うよう誘導する。高レベルソルバーにはPriority-Based Search (PBS) を、低レベルソルバーには最短距離ヒューリスティックを用いたA*を採用する。
倉庫環境を模したグリッドマップを用い、PBSとlocation-time A*を組み合わせた設定で評価を行った。エージェント密度を5%から20%、マップサイズを $3 \times 3$ から $15 \times 15$ ブロックまで変化させ、スループット、実行時間、生成ノード数を指標とした。実験の結果、Soft-limit Highwayにおいて逆行コストを増やすと実行時間が大幅に短縮され、マップサイズが拡大するにつれてスループットの低下幅が縮小することが示された。また、高密度環境ではハイウェイの導入によりrerouting率やアイドルステップ数が抑制され、ハイウェイなしの場合よりも高いスループットを達成した。
ハイウェイの導入は、エージェントの移動を制限するため、スループットにおいて一定のトレードオフが生じる可能性がある。しかし、マップサイズが大きくなるほど、ハイウェイに従うことによる余分な移動の影響は相対的に低下する。また、エージェント密度が高い場合には、ハイウェイによる方向の統一がデッドロックを減少させるため、むしろスループットが向上するという特性を持つ。今後の課題として、動的な障害物が存在する環境における挙動のさらなる検討が挙げられる。
本研究は、絶え間なくタスクが発生する物流倉庫のような環境における、Lifelong Multi-Agent Path Finding (lifelong MAPF) 問題を対象としている。既存手法では、マップサイズやエージェント密度の増加に伴い、実行時間の指数関数的な増大や、デッドロック、不要な経路再計算（rerouting）といった問題が発生する。これに対し、本論文では、エージェントに同一方向への移動を促すことで問題の複雑性を低減させる「ハイウェイ（highway）」の概念を、one-shot MAPFではなくlifelong MAPFの枠組みへと導入することを提案している。具体的には、ハイウェイの概念を組み込むための2つの手法を提示し、デッドロックや経路再計算を最小化する特性について議論している。実験の結果、ハイウェイの設定を用いることで、マップサイズが拡大しても実行時間が大幅に削減され、スループットの低下も緩やかになることが示された。さらに、エージェント密度が高まる状況においても、ハイウェイの活用によってデッドロックや不要な経路再計算の発生を著しく抑制できることが確認された。
Lifelong Multi-Agent Path Finding (MAPF) は、エージェントに次々と新しい目標が割り当てられる動的なシナリオを扱う問題であり、従来の one-shot MAPF 手法では計算効率やスループット（タイムステップあたりの完了タスク数）に課題がある。既存の Rolling-Horizon Collision Resolution (RHCR) は、問題を一連の windowed MAPF 問題に分割することで効率化を図っているが、デッドロックや再経路探索（rerouting）といった問題が発生する。本研究では、one-shot MAPF で用いられる highway の概念を導入し、エージェントに特定の方向への移動を強制する有向マップの活用や、highway の方向に逆らう移動に対してペナルティを与えるヒューリスティック値の計算を行うことで、対面衝突を効果的に回避する。実験の結果、障害物が 50% 以上存在する倉庫のようなマップにおいて、スループットの低下を 10% 未満に抑えつつ、実行時間を数十倍に加速できることが示された。さらに、エージェントの密度が高い環境では、highway の導入によってデッドロックや再経路探索の影響が大幅に軽減されるため、スループットがむしろ向上するという特性を持つ。
One-shot MAPFは、各エージェントに事前に与えられた単一の目標に対し、全エージェントの経路を一度に計画するNP困難な問題であり、評価指標には合計コスト（各エージェントの到着時刻の総和）やメイクスパンが用いられる。既存手法には、低レベルの経路計画と高レベルの衝突解決を組み合わせた探索ベースの手法があり、最適性と完全性を備えたConflict-Based Search（CBS）や、計算効率は高いが不完全かつ非最適なPriority-Based Search（PBS）などが存在する。一方、Lifelong MAPFは、タスクが実行中に逐次生成されるオンラインシナリオを扱い、評価指標はスループット（単位時間あたりの完了タスク数）となる。Lifelong MAPFの解決策として、全エージェントの再計画や新目標を持つエージェントのみの再計画があるが、RHCRのようにWindowed MAPFを導入して一定の時間ホライゾン内のみ衝突解決を行う手法も提案されている。しかし、Windowed MAPFを用いる手法は、デッドロックの発生や、エージェントが以前訪れた場所を再訪するような経路の修正（rerouting）という課題を抱えている。また、One-shot MAPFでは計算量削減のために移動方向を制限するHighwayの設定が利用されるが、Lifelong MAPFにおけるHighwayがデッドロックや経路の修正に与える影響については十分に議論されていない。
マルチエージェント経路計画（MAPF）問題は、マップを表す有向グラフとエージェントの集合 $\mathcal{A}$ として定式化される。各エージェント $a \in \mathcal{A}$ は、自身の開始地点から目標地点 $g_a$ へ到達することを目指し、離散的なタイムステップごとに隣接する場所への移動またはその場での待機を選択する。衝突（conflict）は、2つのエージェントが同一時刻に同じ場所に到達するか、あるいは同じエッジを通過する場合に発生するため、全ての $a \in \mathcal{A}$ に対して衝突のない経路 $\pi_a$ を共同で探索することが目的となる。本研究では、エージェントが事前にタスクを知ることなく、目標到達後に新たなタスクが割り当てられる「lifelong」かつ「online」なMAPFシナリオを想定している。この設定におけるソルバーの目標は、各エージェントの経路を継続的に計画し、タイムステップあたりの完了タスク数であるスループットを最大化することである。
本セクションでは、Lifelong Multi-Agent Path Finding (MAPF) における高速道路（Highway）の定義と、それを利用した2つの手法、Strict-limit HighwayおよびSoft-limit Highwayについて提案している。高速道路は、特定の方向性を持つ一連の地点の列（Corridor）として定義され、交差点（Intersection）はどのCorridorにも属さない。提案フレームワークはRHCRに基づき、高レベルソルバーにPBS、低レベルソルバーに最短距離ヒューリスティックを用いたA*を採用している。
Strict-limit Highwayは、エッジの接続性を高速道路の方向に限定する手法であり、移動可能なグラフを高速道路のサブグラフ $\mathcal{G}_{\text{highway}}$ に置き換えることで、逆方向への移動を物理的に禁止する。この設定では、ヒューリスティック値 $h(s)$ は高速道路の方向のみを考慮した最短経路距離として事前に計算される。一方、Soft-limit Highwayは、高速道路の逆方向へ移動するエッジのコストを $\alpha$ 倍（$\alpha > 1$）に増大させることで、低レベルソルバーが高速道路に沿った経路を選択するように誘導する手法である。このとき、ヒューリスティック値は、逆方向の移動を含む経路 $p$ に対して $h(s) = \min_{p} \sum_{e \in p} \text{cost}(e)$ となり、$\alpha$ が大きくなるほど高速道路の設定に近づくが、動的な障害物がある場合には逆方向への回避行動（Rerouting）も許容される。
Strict-limit Highwayには、窓関数型MAPFで発生しやすいデッドロックとReroutingを防ぐ数学的特性がある。デッドロックについて、Strict-limit環境下では、エッジに沿って移動する限り、エージェントの集合 $\mathcal{A}$ において $\sum_{a \in \mathcal{A}} h(s_a) > \sum_{a \in \mathcal{A}} h(s'_a)$ が常に成立するため、エージェントが待機するよりも移動する方が総コストが低くなり、デッドロックが回避される。また、Reroutingについても、高速道路上の移動において $h(s_{t+1}) < h(s_t)$ が保証されるため、エージェントが目標から遠ざかるような経路を割り当てられることがなく、経路の整合性が維持される。
本実験では、Lifelong Multi-Agent Path Finding (MAPF) において、高速道路（highway）の導入がスループット、実行時間、および生成ノード数に与える影響を、倉庫環境を模したグリッドマップを用いて評価している。実験設定では、PBSをLifelong MAPFソルバー、location-time A*を低レベルソルバーとして用い、エージェント密度を5%から20%まで変化させ、マップサイズを $3 \times 3$ から $15 \times 15$ ブロックまで拡大して検証している。ソフト制限高速道路（soft-limit highway）において、高速道路の進行方向と逆行するコスト $c$ を増加させると、エージェントの進行方向が統一されるため、生成される高レベルノード数が減少し、実行時間が大幅に短縮されることが示された。マップサイズが大きくなるにつれ、高速道路に従うことで発生する余分な移動ステップの割合が相対的に低下するため、スループットの低下幅が縮小し、高速道路なしのケースとの差が解消される傾向にある。また、エージェント密度が高まる環境では、高速道路の導入によってリルーティング率（rerouting rate）やアイドルステップ数（idle timesteps）が抑制され、デッドロックが減少することで、高速道路なしの場合よりも高いスループットを達成できることが確認された。
本研究では、従来の単発的なマルチエージェント経路探索（MAPF）で提案されていたハイウェイの概念を、実行時間とスループットのトレードオフが重要となる継続的な（lifelong）MAPFシナリオへと拡張し、その有効性を検討した。ハイウェイを継続的なMAPFのフレームワークと組み合わせることで、デッドロックや再ルーティングといった既存の課題を最小化する特性について議論を行っている。一連の実験評価の結果、ハイウェイの導入は実行時間を大幅に短縮できることが示された。また、マップのサイズやエージェントの密度が増大した場合においても、スループットの低下が徐々に緩やかになるという特性が確認された。