本研究は、エージェントが棚（shelf）を運搬してピッキングステーションへ運び、その後元の位置に戻すという、マルチアイテム・パッキングを伴うマルチエージェント・ピックアップ＆デリバリー（MAPD-MP）問題を対象とする。環境はグラフ $G=(V, E)$ で定義され、$N$ 台のエージェント $A=\{a_1, \dots, a_N\}$ と $M$ 個の棚 $S=\{s_1, \dots, s_M\}$ が存在する。タスク $\tau(i,j,k) = \langle s_i, v_{\rho_{jk}} \rangle$ は、棚 $s_i$ をステーション $\rho_j$ のノード $v_{\rho_{jk}}$ まで運び、ホームノードに戻して荷降ろしすることを指す。既存の優先度付き経路計画法である3PCSをベースとし、エージェントの優先度 $q_i(t)$ を運搬状態（荷物あり：$1$、なし：$0$）に基づいて設定する分散型アルゴリズムを前提としている。
提案手法は、スループット最大化のために3つの主要コンポーネントを統合した点に貢献がある。第一に、棚の選択確率 $p_k$ に基づき、確率の高い棚をステーションに近いホームノード $h(s_k)$ へ配置する棚配置最適化（SAO）を導入した。第二に、Gale–Shapleyアルゴリズムを用いた安定マッチング（TAGS）により、エージェント間のタスク処理時間の不均衡を緩和する。第三に、将来のタスクに備えて棚を専用の保持ノード $V_{hld}$ へ事前に移動させる保持ノード統合（HNI）を提案した。これにより、大規模なエージェントチームにおける協調効率の向上と、ピッキングリストの処理スループットの有意な改善を実現している。
提案手法「3PCS+All」は、SAO、TAGS、HNIの3要素で構成される。SAOは棚の返却直前にホームノードを入れ替えることで、高確率な棚をステーション近傍に配置する。TAGSでは、未割り当てタスク $\tau$ に対して最小コスト $cost(a, \tau)$ を持つエージェントを選択する `TASKASSIGNMENTWITHGS` を用い、Gale-Shapleyアルゴリズムによって安定なマッチングを形成する。HNIでは、`SUBTASKASSIGNMENTFORAGENT` を用いて、スコア $Q = C_1 + C_2 - C_4 + \min(t_{\rho_j}^{comp} - (C_1 + C_3), 0)$ が正となる最適なサブタスク $\sigma_n(i,j,k) = \langle \tau(i,j,k), v_{n'hld} \rangle$ を選択する。また、各ステーション $\rho_j$ には長さ $\delta=2$ のキュー $L_{\rho_j}$ が設けられ、タスクのプリフェッチを可能にしている。
2次元グリッド環境（Env. 1, Env. 2）において、Zipf分布 $i^{-\alpha} p_i = \text{const.}$（$\alpha \in [1.0, 2.0]$）に基づくタスクを用いて評価を行った。エージェント数 $|A|$ を $56$ から $168$ まで変化させた実験の結果、Env. 1 ($\alpha=2.0$) において、エージェント数 $168$ 時の「3PCS+All」のスループットは、TPに対して約 $88.7\%$、3PCSに対して約 $72.4\%$ の向上を達成した。また、タスク稼働率においてもTPより約 $20\%$ 高い値を記録し、保持ノードの利用率は約 $12\%$ に達した。計算量については、エージェント数に対して線形に増加するものの、最大でも約 $15\text{ ms}$ 程度に抑えられている。
提案手法は、特定の選択分布に依存せず、混雑しやすい Env. 2 や $\alpha=1.0$ の環境においても一貫して高いスループットを維持しており、堅牢性が示された。HNIの導入は、エージェントがアイドル状態になるのを防ぎ、棚の輸送サブタスクを通じて効率的にノードを活用することを可能にしている。SAOの効果については、ヒートマップにより、実行後に選択確率の高い棚がステーション近傍へ最適に配置されていることが確認された。本手法は、3PCSが「well-formed MAPD-MP問題」に対して完全性を持つことから、同様の条件下で完全性が保証される。
本研究では、エージェントが棚（shelf）を運搬してピッキングステーションへ運び、その後元の位置に戻すという、マルチアイテム・パッキングを伴うマルチエージェント・ピックアップ＆デリバリー（MAPD-MP）問題を扱う。提案手法は、既存の優先度付き経路計画法（3PCS）と統合可能な3つのコンポーネントで構成される。第一に、棚の選択確率に基づき棚の配置を最適化する棚配置最適化（SAO）、第二に、Gale–Shapleyアルゴリズムを用いてエージェント間のタスク処理時間の不均衡を緩和する安定マッチングによるタスク割り当て（TAGS）、第三に、将来のタスクに備えて棚を専用の保持ノードへ事前に移動させる保持ノード統合（HNI）である。実験では、実世界のEC倉庫で見られるロングテール現象を模したZipf分布に基づくタスクを用い、大規模なエージェントチームにおける協調効率の向上と、ピッキングリストの処理スループットの有意な改善を実証している。
本セクションでは、マルチエージェント・ピックアップ＆デリバリー（MAPD）にマルチアイテム・パッキング（MP）を拡張したMAPD-MP問題の定式化が示されている。環境はグラフ $G=(V, E)$ で定義され、$N$ 台のエージェント $A=\{a_1, \dots, a_N\}$ と $M$ 個の棚 $S=\{s_1, \dots, s_M\}$ が存在する。エージェント $a_i$ が時刻 $t$ に運搬している棚を $c_i(t) \in S \cup \{\perp\}$、棚 $s_j$ の状態（運搬者）を $d_j(t) \in A \cup \{\perp\}$ と定義し、衝突回避のため $v_i(t) \neq v_{i'}(t)$ かつ $w_j(t) \neq w_{j'}(t)$（棚の重複禁止）などの制約を課す。タスク $\tau(i,j,k) = \langle s_i, v_{\rho_{jk}} \rangle$ は、棚 $s_i$ をステーション $\rho_j$ のノード $v_{\rho_{jk}}$ まで運び、ホームノードに戻して荷降ろしすることを指す。既存手法である3PCSをベースとし、エージェントの優先度 $q_i(t)$ を運搬状態に基づき $q_i(t) = 1$（荷物あり）または $0$（荷物なし）と設定し、衝突時には低優先度エージェントが再計画を行う分散型アルゴリズムを想定している。
本セクションでは、Multi-Agent Pickup and Delivery with Multi-Item Packing (MAPD-MP) 問題における、スループットを最大化するための提案手法が詳述されている。提案手法は、棚の配置最適化 (SAO)、安定結婚アルゴリズムを用いたタスク割り当て (TAGS)、およびタスクのプリフェッチを可能にするキュー管理の3つのコンポーネントで構成される。SAOは、棚の選択確率 $p_k$ に基づき、確率の高い棚をステーションに近いホームノード $h(s_k)$ へ配置するよう、棚の返却直前にホームノードの入れ替えを行うアルゴリズムである。TAGSは、エージェントと未割当タスクの集合に対してGale-Shapleyアルゴリズムを適用し、安定なマッチングを形成することでタスクを割り当てる。また、各ステーション $\rho_j$ には長さ $\delta$（実験では $\delta=2$）のキュー $L_{\rho_j}$ が設けられ、エージェントが現在のタスクの後半部分を実行している間に、次のピッキングリストを事前に準備（プリフェッチ）できる仕組みとなっている。本手法は、既存のパスプランナである3PCSと統合可能であり、3PCSが「well-formed MAPD-MP問題」に対して完全性を持つことから、提案手法も同様の条件下で完全性が保証される。
本セクションでは、マルチエージェントにおけるタスク割り当てと、経路計画のためのHolding Node Integration (HNI) 手法が提案されている。タスク割り当てにはGale-Shapley (GS) アルゴリズムを応用した `TASKASSIGNMENTWITHGS` が用いられ、未割り当てタスク $\tau$ に対して最小コスト $cost(a, \tau)$ を持つエージェント $a$ を選択することで、タスクに最適な安定マッチングを実現する。HNIでは、エージェントが一時的に棚を置くための保持ノード集合 $V_{hld}$ を導入しており、`SUBTASKASSIGNMENTFORAGENT` 手法により、スループットを最大化するサブタスク $\sigma_n(i,j,k) = \langle \tau(i,j,k), v_{n'hld} \rangle$ を選択する。このサブタスクの選択には `GETSCORE` 関数が使用され、エージェントの移動コスト $C_1, C_2, C_3, C_4$ と、ステーションの完了予定時刻 $t_{\rho_j}^{comp}$ を用いて、スコア $Q = C_1 + C_2 - C_4 + \min(t_{\rho_j}^{comp} - (C_1 + C_3), 0)$ を計算し、これが正の場合に最適なサブタスクが選定される。なお、この割り当ては、アクティブなタスク集合 $T$ が空であること、およびキューの長さが $\delta \ge 2$ であることを前提条件としている。
提案手法では、サブタスク割り当てによる期待時間短縮量を評価するスコア $Q$ を定義しており、これはサブタスクがない場合の完了予定時刻 $t_{\text{comp}\rho_j}$ と、サブタスクを割り当てた場合のコストの差として $Q = C_1 + C_2 - C_4 + \min(t_{\text{comp}\rho_j} - (C_1 + C_3), 0)$ と計算される。棚の選択確率 $p_i$ には、エージェントの位置に近い棚が選ばれやすくなるよう Zipf 分布 $i^{-\alpha} p_i = \text{const.}$ を用い、環境に応じて $\alpha$ を $1.0$ から $2.0$ の範囲で設定している。実験では、2次元グリッド環境（Env. 1, Env. 2）を用い、エージェント数 $|A|$ を $56$ から $168$ まで変化させ、スループットやCPU時間、タスク稼働率を評価指標とした。結果として、提案手法である 3PCS+All は、エージェント数 $|A|=168$ において TP に対して約 $88.7\%$、3PCS に対して約 $72.4\%$ のスループット向上を達成し、エージェント数が増加しても高い稼働率を維持できることが示された。また、CPU 時間はエージェント数に対して線形に増加するものの、最大でも約 $15\text{ ms}$ 程度に抑えられており、実用的な計算量であることが確認された。
提案手法である「3PCS+All」は、棚の選択確率に基づく棚配置最適化（SAO）、安定マッチングを用いたタスク割り当て（TAGS）、および保持ノードを活用するHNIを統合した手法である。実験では、Env. 1（Zipf指数 $\alpha = 2.0$）において、エージェント数 $|A|$ が増加してもスループット（単位時間あたりの完了ピッキングリスト数）を維持し、ベースラインであるTPと比較して、168エージェント時でも約20%高い稼働率（task operating rate）を達成した。HNIの適用により、保持ノードの利用率（holding node usage rate）は168エージェント時に約12%に達し、エージェント数が増加して他の手法がアイドル状態になる中でも、棚の輸送サブタスクを通じて効率的にノードを活用できることが示された。また、$\alpha = 1.0$ の異なる分布や、ノード・棚の数が少なく混雑しやすい Env. 2 においても、3PCS+All は一貫して高いスループットを維持しており、特定の選択分布に依存せず、混雑環境下でも有効であることが確認された。SAOの効果については、実行前は一様であった棚の分布が、実行後には選択確率の高い棚がステーション近傍に配置されるよう最適化されることがヒートマップにより示されている。