本論文は、異なる原理に基づく2つのアプローチ、すなわちMulti-Agent Path-Finding (MAPF) とMulti-Agent Reinforcement Learning (MARL) を、MAPD問題という共通の枠組みで評価することを目的としている。MAPFは衝突のない経路を計算する手法であり、単発のsingle-shot設定から、タスクを継続するlifelong設定へと拡張される。一方、MARLは環境の観測に基づき累積報酬を最大化する方策を学習する手法であり、部分観測マルコフ決定過程 $\langle \mathcal{A}, \mathcal{S}, \Omega, \mathbf{a}, \mathbf{o}, \mathcal{P}, r_i \rangle$ として定式化される。従来、これら2つの領域では、MAPFではflow timesやmakespans、MARLではreturnといった異なる評価指標が用いられてきたが、本研究ではこれらを統合的に比較する。
本研究の主な貢献は、これまで評価指標や研究領域が乖離していたMAPFベースの手法とMARLベースの手法を、シミュレーションによる倉庫自動化環境を用いて直接比較した点にある。具体的には、中央集権的なCBSのlifelong版と、最先端のSEACをベンチマークとして用いている。実験を通じて、エージェント密度や数に応じた各手法の適性を明らかにし、低密度環境ではCBS、高密度・多エージェント環境ではSEACが適しているという設計指針を提示した。また、今後の研究として、MAPFの解をMARLの学習に利用する模倣学習の可能性や、非均質なエージェント設定への拡張の必要性を議論している。
比較対象となる手法として、まずMAPF側ではConflict-Based Search (CBS) を用いる。CBSは、高レベルでの制約ツリー（CT）に対する最良優先探索と、低レベルでの制約遵守型経路再計画を行う二段階の集中型アルゴリズムである。CTの各ノードは、制約集合、最小コスト経路、解の総コスト、および衝突集合を保持する。次にMARL側では、Shared Experience Actor-Critic (SEAC) を用いる。SEACは、エージェント間で経験を共有し、重要度サンプリングを用いてオフポリシーデータとして扱う手法である。実験環境はRWAREをベースに、アイテムの回収・配送プロセスと報酬設計（回収・配送成功時に報酬を付与）を最適化したロボット倉庫シミュレーションを用いている。
実験では、環境サイズ（small, medium, large）とエージェント数を変化させ、5つの指標（mean flow time, mean makespan, mean episodic cumulative reward, mean number of successfully delivered items, mean episodic time）で性能を測定した。lifelong CBSはエージェント数2, 5, 8の条件下で評価し、SEACは5, 10, 15の条件下で評価した。結果、CBSはエージェント数が少ない場合にflow timeや配送アイテム数でSEACを上回るが、10エージェント以上では再計画の頻度と計算コストの急増によりスケーラビリティの限界が見られた。対照的に、SEACは学習済みポリシーによる推論のみを行うため、実行時間は環境密度に依存せず安定しており、高密度な環境下でもCBSより多くのアイテムを配送できることが確認された。
本研究の限界として、現在のlifelong CBSの実装が、目標変更のたびに再計画を行うため効率性に欠ける点が挙げられる。これを解決するために、ICBSやCBSHといった改良版、あるいは最新のMAPFソルバーの導入が必要である。また、本研究は全エージェントが均質な設定を前提としているが、現実的なシナリオではエージェントごとに能力や目標が異なる非均質な設定が求められる。今後の展望として、lifelong MAPFの解をエキスパートのデモンストレーションとして利用し、MARLのサンプル効率を向上させる手法や、SePS (Selective Parameter Sharing) アルゴリズムを用いた非均質なエージェントへの拡張が示唆されている。
本研究では、異なる原理に基づくマルチエージェント・ピックアップ＆デリバリー（MAPD）問題への2つの最先端手法、すなわちマルチエージェント経路探索（MAPF）に基づく Conflict-based Search (CBS) と、マルチエージェント強化学習（MARL）に基づく Shared Experience Actor-Critic (SEAC) を調査している。従来、これら2つのアルゴリズムは異なる研究領域において全く異なる評価指標を用いて性能が測定されてきたが、本論文ではこれらを包括的に比較することを目的としている。具体的には、シミュレーションによる倉庫自動化環境を用いて、これら2つの手法のベンチマーク評価を行う。
Multi-Agent Pickup and Delivery (MAPD) 問題は、エージェントがリクエストキューからアイテムを回収し、指定された目的地へ配送するタスクを衝突回避しながら実行する問題であり、倉庫自動化などの産業応用において重要である。MAPDへのアプローチは主に、エージェントの現在位置と環境情報を基に衝突のない経路を計算する Multi-Agent Path-Finding (MAPF) と、環境の観測に基づき累積報酬を最大化する方策を学習する Multi-Agent Reinforcement Learning (MARL) の2種類に大別される。従来の MAPF がゴール到達で終了する single-shot な設定であるのに対し、MAPD は配送完了後に次のタスクへ移行する lifelong な設定を扱う点が大きな違いである。評価指標においても、MAPF 側では成功率、flow times（全エージェントの到着時刻の総和）、makespans（全エージェントの到着時刻の最大値）が用いられる一方、MARL 側では学習および評価の return が用いられるという乖離が存在する。本論文では、これら性質の異なる手法を包括的に比較するため、中央集権的な single-shot MAPF ソルバーである Conflict-Based Search (CBS) の lifelong 版と、最先端の MARL ソルバーである Shared Experience Actor-Critic (SEAC) との比較を行う。
本セクションでは、MAPF、Lifelong MAPF、およびMARLの定式化が述べられている。Single-shot MAPFは、重みなし無向グラフとエージェントの集合で定義され、各エージェントは開始頂点から目標頂点へ、隣接頂点への移動または待機（共にコスト1）を通じて移動する。この際、時刻 $t$ において複数のエージェントが同一頂点に存在することを頂点衝突 $v_i(t) = v_j(t)$、時刻 $t$ と $t+1$ の間にエージェントが同一の辺を逆方向に通過することを辺衝突 $e_i(t, t+1) = e_j(t, t+1)$ と定義し、全エージェントのコストの総和を最小化する衝突のない経路集合を求める。Lifelong MAPF（MAPD問題の基礎）は、単発のMAPFを内側ループで繰り返し解く問題であり、全エージェントの逐次再計画、荷物のピックアップ/デリバリー時のみの再計画、あるいはオフラインでの組合せ最適化問題への帰着という3つのアプローチが存在する。一方、MARLは衝突のない経路を事前に計算するのではなく、環境の状態に基づき各時刻の行動を決定する方策を学習する手法であり、部分観測マルコフ決定過程（Markov game） $\langle \mathcal{A}, \mathcal{S}, \Omega, \mathbf{a}, \mathbf{o}, \mathcal{P}, r_i \rangle$ として定式化される。MARLの目的は、各エージェントの割引報酬の総和 $\sum_{t=0}^{T} \gamma^t r_i(t)$ を最大化する最適結合方策 $\boldsymbol{\pi}^*$ を見つけることであり、文脈に応じて行動空間や観測空間が同一であるといった制約が課される場合もある。
MAPF問題に対する強力な手法として、Conflict-Based Search (CBS) は、高レベルでの制約ツリー（CT）に対する最良優先探索と、低レベルでの制約を遵守した経路再計画を行う二段階の集中型アルゴリズムである。CTの各ノードは、頂点またはエッジの制約集合、制約下での各エージェントの最小コスト経路からなる解、解の総コスト、および経路間の衝突集合を保持し、衝突が存在する場合に制約を追加してツリーを分岐させることで解決を図る。CBSの改良版には、衝突の選択を優先するICBSや、許容的なヒューリスティックを用いて高レベル探索を加速するCBSHが存在する。一方、MARLアルゴリズムでは、期待報酬 $J(\theta) = \mathbb{E}_{\tau \sim \pi_\theta} [R(\tau)]$ を最大化する方策勾配法（REINFORCE等）が用いられるが、分散を抑えるために価値関数 $V_\phi(s)$ を用いるActor-Critic法が一般的である。さらに、エージェント間で経験を共有し、重要度サンプリングを用いてオフポリシーデータとして扱うSEACや、学習時に全エージェントの情報を利用し実行時には分散実行を行うCentralized Training with Decentralized Execution (CTDE) パラダイムに基づくMADDPG、Q-MIX、COMAなどの手法が、MAPD問題の解決に活用されている。
本実験では、RWAREをベースに、アイテムの回収・配送プロセスや報酬設計（回収時および配送成功時に報酬を付与）を最適化したロボット倉庫環境を用いて、MAPFベースのlifelong CBSとMARLベースのSEACを比較評価している。実験設定として、環境サイズ（small, medium, large）とエージェント数（lifelong CBSは2, 5, 8、SEACは5, 10, 15）を変化させ、mean flow time、mean makespan、mean episodic cumulative reward、mean number of successfully delivered items、mean episodic timeの5指標で性能を測定した。結果として、lifelong CBSはエージェント数が少ない環境では最短経路を計画するため、SEACよりもflow time、makespan、配送アイテム数において優れた性能を示すが、エージェント数の増加に伴い再計画（replanning）の頻度と計算コストが急増し、10エージェント以上ではスケーラビリティの限界に直面する。対照的に、SEACは学習済みポリシーに基づく推論のみを行うため、テスト時の実行時間は環境の密度に依存せず安定しており、高密度な環境下でもCBSより多くのアイテムを配送できる高いスケーラビリティを持つ。ただし、SEACには学習に多大な時間を要するという限界があり、低密度環境ではlifelong CBS、高密度・多エージェント環境ではSEACが適していることが示された。
本セクションでは、現在の実装における課題と今後の研究方向性が議論されている。著者らは、エージェントの目標地点が変更されるたびに再計画を行う lifelong CBS の実装が効率性に欠けることを指摘し、Section 3 で述べた CBS の改良版や、Wu et al. (2021) 等の最新の MAPF ソルバーの活用が必要であるとしている。今後の重要な研究方向として、lifelong MAPF の解をエキスパートのデモンストレーションとして利用し、MAPD 問題を解くための MARL アルゴリズムのサンプル効率を向上させる手法（模倣学習や逆強化学習）が挙げられている。また、本研究では全エージェントが任意のアイテムを扱える均質な設定を仮定しているが、より現実的なシナリオとして、エージェントごとに能力や目標が異なる非均質な設定への拡張が示唆されている。具体的には、能力や目標に基づく教師なしクラスタリングを用いてパラメータ共有を行う SePS (Selective Parameter Sharing) アルゴリズムが挙げられており、より複雑な MAPD 問題において lifelong MAPF ベースの解と SePS がどのように比較されるかが今後の課題である。