現代の倉庫における自動化では、複数のエージェントがアイテムを回収し、指定された目的地へ配送するマルチエージェント・ピックアップ・アンド・デリバリー（MAPD）問題の解決が求められる。対象となる環境は、複数のワークステーションと中央の保管エリア、およびそれらを結ぶ通路から構成される。エージェントは、狭い通路での衝突を回避しながら、無向グラフ $G = (V, E)$ 上の開始頂点 $s_i$ から目標頂点 $f_i$ までの経路を計画する必要がある。従来の課題として、エージェント数や環境規模の増大に伴い、衝突のない経路の組み合わせが爆発的に増加し、計算コストが極めて高くなる点が挙げられる。
本研究の新規性は、MAPD問題に対して、代表的なMAPF手法であるConflict-Based Search（CBS）と、MARL手法であるShared Experience Actor-Critic（SEAC）を適用し、環境規模やエージェント数の変化に応じた性能差を明らかにした点にある。特に、単発の解決を目指すsingle-shot形式と、継続的な運用を想定したlifelong形式の両面から比較検討を行っている。これにより、動的な環境下において、再計画に多大な時間を要する従来の探索ベースの手法に対し、学習済みの方策を用いるMARLフレームワークが持つ優位性を提示している。
提案手法として、2つの異なる戦略を比較している。一つはMAPFに基づくConflict-Based Search（CBS）であり、エッジ衝突や頂点衝突を制約として扱い、衝突のない経路を構築する。もう一つはMARLに基づくShared Experience Actor-Critic（SEAC）であり、エージェントが環境の完全な観測に基づき、累積報酬を最大化するように方策を学習する。SEACでは、各タイムステップ $t$ における環境状態から、エージェントが次にとるべき最適な行動を即座に決定する。Lifelong形式の設定では、配送完了後にエージェントが即座に次の目標へ移動するプロセスを、Single-shot問題を連続的に解くループとして定義している。
評価は、中規模および大規模な環境サイズにおいて、エージェント数を変化させて実施された。比較手法として、MAPFのCBSとMARLのSEACを用いている。評価指標には、平均メイクスパン（mean makespan）と平均フロータイム（mean flow time）が用いられた。実験の結果、エージェント数が少ない場合には、再計画の計算コストが低いlifelong形式のCBSが有効であった。しかし、エージェント数が増大すると、CBSは収束の可能性が低下し、解に到達するまでに非常に長い時間を要する。一方で、SEACは環境状態から行動を即座に決定できるため、エージェント数が多い環境においても効率的に機能することが示された。
本研究の限界として、エージェントはあらゆるアイテムを扱える均質な存在として想定されており、個別の能力差は考慮されていない。また、CBSのような探索ベースの手法は、エージェント数の増加に伴う計算量の爆発というトレードオフが存在する。今後の課題として、より複雑な動的環境への対応や、エージェントの多様性を考慮した設計が挙げられる。
本研究では、倉庫内でのピックアップおよび配送タスクを解決するために、マルチエージェント経路探索（MAPF）とマルチエージェント強化学習（MARL）の2つのアプローチを比較検討している。問題設定は、エージェントが要求されたアイテムを回収し、指定された目的地へ配送するものであり、配送完了を最終目標とするシングルショット形式と、配送後に新たなアイテムを回収し続けるライフロング形式の2種類が定義されている。MAPFアプローチでは衝突のない経路を構築することを目指すが、MARLアプローチでは環境の状態とエージェントの位置に基づき、意思決定の方策を学習する。実験の結果、エージェント数が少ない場合には、再計画の計算コストが低いライフロング形式のConflict-Based Search（CBS）が有効であるが、エージェント数が増大すると再計画に多大な時間を要する。一方で、MARLに基づくShared Experience Actor-Critic（SEAC）は、時刻 $t$ における環境状態から最適な行動を即座に決定できるため、エージェント数が多い環境においてより効率的な選択肢となることが示されている。なお、本研究の対象は、あらゆるアイテムを扱える均質なエージェントを想定している。
現代の倉庫におけるピッキングおよび配送タスクの自動化では、中央の広大な保管エリアから各ワークステーションへアイテムを運搬するマルチエージェントの経路計画が重要となる。保管エリアの占有により通路が狭窄化し、一度に一台のロボットしか通行できない制約が生じるため、衝突を回避しつつアイテムの損傷を防ぐための効率的な経路探索が求められる。エージェントは目標ノードへ向かう過程で、障害物や他のエージェントを回避しながら、倉庫内の適切な経路を形成する必要がある。本研究の対象となる環境は、複数のワークステーションと、中央の保管エリアから各ステーションへアイテムを配送するために通路を移動する複数のエージェントで構成される。
マルチエージェント・ピックアップ・アンド・デリバリー問題は、単発の解決を目指す single-shot MAPF と、継続的な運用を想定した lifelong MAPF の両面からアプローチされるが、後者の戦略の内部ループには single-shot MAPF の解が含まれる。エージェント数や環境規模が増大するにつれ、要求されたアイテムを目的地へ運ぶためにエージェントが辿り得る衝突のない経路の組み合わせは爆発的に増加する。このような複雑な環境下において、マルチエージェント強化学習（MARL）は、結合された観測状態と結合された行動空間を考慮して出発地から目的地へと到達する能力を持つため、有効な手法として期待される。
マルチエージェント・ピックアップ・アンド・デリバリー（MAPD）問題は、倉庫内で複数のエージェントが同時に、各リクエストの開始ノードから目標ノードまで衝突を回避しながら移動する経路を計画することを目的とする。この問題は、無向グラフを基盤とした有向グラフ $G = (V, E)$ 上のマルチエージェント経路探索（MAPF）として定式化され、$k$ 個のエージェント $a \in \{1, 2, \dots, k\}$ のそれぞれに対して、開始頂点 $s_i \in V$ と目標頂点 $f_i \in V$ が与えられる。グラフにおける経路 $p$ は、隣接する頂点間のエッジが集合 $E$ に含まれる頂点の列 $p = v_1 v_2 \dots v_m$ として定義される。2つの経路 $p_1$ と $p_2$ が衝突を回避するためには、すべての時刻において同一の頂点を占有しないこと、およびエッジの逆方向移動（エッジの衝突）が発生しないことの2条件を満たす必要がある。
本研究では、マルチエージェント経路探索（MAPF）に基づく手法とマルチエージェント強化学習（MARL）に基づく手法の2種類を、環境サイズやエージェント数の違いに応じて比較検討している。具体的には、MAPFの代表的な手法である衝突ベース探索（Conflict-based Search）と、MARLのShared Experience Actor-Criticアプローチを、マルチエージェント集荷配送問題（MAPD）に対して適用して評価している。実験の結果、各タイムステップ $t$ において環境状態が変化する動的な状況下では、MARLフレームワークの方が容易に対応できることが示された。また、エージェント数が増加するにつれて、衝突ベース探索は収束の可能性が低下し、解に到達するまでに非常に長い時間を要する傾向がある一方、Shared Experienceアプローチはこのような条件下でも有効に機能する。評価指標には、中規模および大規模な環境サイズにおいて、平均メイクスパン（mean makespan）と平均フロータイム（mean flow time）が用いられている。
本論文の構成は、まず第2節で研究の理解に不可欠な背景知識となる概念を整理し、第3節において既存研究の比較レビューを行う。第4節では、マルチエージェントによるピックアップおよびデリバリー問題（MAPD）に対して採用された2つの異なる戦略とその動作プロセスについて詳細に記述する。第5節では、これら2つの戦略を複数の評価指標に基づいて評価し、得られた結果を比較検討する。最後に第6節において、本研究の結論を述べるとともに、現時点での課題と今後の展望について提示する。
本セクションは、以降の章で展開される議論を理解するために必要となる基礎概念および予備知識を網羅している。具体的には、倉庫内におけるピックアップおよびデリバリータスクの自動化を実現するための基盤となる、マルチエージェント経路探索（MAPF）およびマルチエージェント強化学習（MARL）に関する背景知識が提供される。ただし、提示された範囲内では、具体的なアルゴリズムの定義や数式、実験設定に関する詳細な記述は含まれていない。
エージェント $a$ は、環境 $\mathcal{E}$ において、各ステップで与えられる報酬とペナルティに基づき、出発地点から目標地点へ到達することを学習する。この環境は完全に観測可能（completely observable）であり、現在の環境状態に基づいて次にとるべき行動が決定される。エージェントは、学習の終了時における累積報酬を最大化するように方策（policy）を学習する。
マルチエージェント強化学習（MARL）は、共通の環境内で複数のエージェントが相互作用する際の、結合された行動や結合された観測を扱う枠組みである。エージェント間の相互作用と振る舞いに基づき、学習は大きく3つのカテゴリに分類される。第一に、各エージェントが環境の局所的な部分観測しか持たない状況において、全体の状況を把握するために他者と調整を行い、共通の目標を達成する協調型エージェントである。第二に、相手の行動に基づいて戦略を練り、自身の目的関数を最大化するために競い合う競争型エージェントであり、例えば「隠れん坊」のようなケースがこれに該当する。第三に、チーム内では協調しつつ、対戦相手に対しては競合するという、協調と競争の両面を併せ持つ混合型であり、ホッケーの試合のように報酬獲得のための戦略構築と、ライバルへの対抗策の策定を同時に行う。
環境内に $n$ 個のエージェント $\{a_1, a_2, \dots, a_n\}$ が存在し、各エージェントは始点と終点の属性を持つ。環境は重みなし無向グラフとして表現され、各タイムステップにおいて、エージェントは現在位置に隣接するノードへ移動するか、あるいは現在位置に留まるかのいずれかを選択でき、移動と待機はいずれもコスト $1$ を要する。この設定における衝突には、2つのエージェントが同一の頂点 $v$ に同時に到達するケースと、2つのエージェントが同一の辺を互いに逆方向に通過するケースの2種類が存在する。エージェントは、これらの衝突や障害物を回避しながら、各アイテムのピックアップから目標地点への到達に至る経路を決定する必要がある。
Single-shot MAPFでは、エージェントは配送地点に到達してアイテムを荷下ろしした時点で動作を停止するが、Lifelong MAPFでは、配送完了後にエージェントは即座に次の目標地点へと移動し、倉庫内の新たな配送タスクを継続的に遂行する。このアプローチは、内側のループにおいて、多数のSingle-shot問題を連続的に解き続けるプロセスとして定義される。これにより、単発の経路計画ではなく、絶え間なく発生するタスクに対してエージェントを動的に割り当て、継続的な運用を可能にしている。
マルチエージェント経路探索（MAPF）において、狭い通路での衝突を回避するために、本研究ではエッジ衝突と頂点衝突の2種類に焦点を当てている。エッジ衝突は、時刻 $t$ において2つのエージェントが同じエッジ $(v_i, v_j) \in V$ を同時に通過しようとする状態を指し、制約木を用いて特定の遷移を禁止することで回避される。頂点衝突は、異なる頂点から出発した2つのエージェントが、同一の頂点に同時に到達することで発生する衝突であり、最終的な解においていずれかの行動を修正することで回避される。なお、サイクル衝突、フォローイング衝突、スワッピング衝突については、衝突のない経路を構築するプロセスでは考慮されない。また、本問題はマルコフゲーム $(N, S, \{O_i\}_{i \in N}, \{A_i\}_{i \in N}, P, \{R_i\}_{i \in N})$ として定義され、各エージェント $a_i \in N$ は環境の完全な観測は行えず、局所的な観測に基づいて行動を選択する。エージェントは、共有された観測を通じて環境の全体像を把握し、個別の報酬 $R_i$ の合計を最大化するように方策を決定する。
本セクションでは、マルチエージェントのピックアップおよびデリバリー問題に対処するための2つの主要なアプローチとして、MAPF（Multi Agent Path Finding）とMARL（Multi Agent Reinforcement Learning）が紹介されている。MAPFに基づく手法としては、衝突のない経路を構築することで問題を解決する Conflict-based Search (CBS) が挙げられる。これに対し、MARLに基づく比較対象の手法として、Shared Experience Actor Critic (SEAC) が提示されている。本研究では、これら2つの異なるアプローチである CBS と SEAC を用いて、問題解決における性能の比較および評価を行う。
倉庫内のピックアップおよびデリバリー問題は、衝突のない経路を構築するマルチエージェント経路探索（MAPF）と、環境状態やエージェントの位置に基づき意思決定方策を学習するマルチエージェント強化学習（MARL）の2つのアプローチで解決される。MAPFには、単一の制御装置がエージェントを導く集中型と、エージェントが自律的に協力する分散型の手法があり、後者では学習時のみ経験を共有し実行時は個別に動く集中学習・分散実行（CTDE）や、教師エージェントが他者にフィードバックを与える手法、ターゲット方策と行動方策を分離するオフポリシーの分散強化学習などが提案されている。MARLにおいては、タスクに基づきエージェントをグループ化して方策を共有する役割特化型学習や、能力や目標の類似性に基づきクラスタリングを行いパラメータ共有を行う選択的パラメータ共有手法が、スケーラビリティや学習効率の向上に寄与している。MAPFの具体的なアルゴリズムとして、優先度に基づき経路を計画する手法があるが、これは高優先度エージェントによって低優先度エージェントの経路が遮断され、目標に到達できないという劣最適性の限界を持つ。また、動的な環境への対応として、古いノードや制約の概念を用いて実行中に新しいエージェントを導入する手法や、解を $k$ 個のセグメントに分割して衝突検証を容易にする説明可能な手法も存在する。