本研究は、タスク、エージェント、ピックアップ地点、デリバリー地点の4要素を同時に決定する必要がある、NP困難な「Many-to-Many MAPD」問題を扱う。従来のMAPDは1つのタスクに対して1つのピックアップ・デリバリー地点を想定していたが、本研究ではSKU（Stock Keeping Unit）識別子によって追跡されるアイテムが複数の場所に存在し得る設定を導入している。これにより、問題はエージェント、タスク、開始地点、目的地の4次元的な割り当て問題へと発展する。本研究では、タスク完了時間の総和を最小化する標準的な「M2M」と、SKUの空間分布を考慮して将来の性能向上を図る「M2M-wSKU」の2つのバリアントを提案している。
提案手法M2Mは、既存の最先端手法であるLNS-PBSと比較して、異なる環境や在庫密度において平均で最大22,000タスク多く完了するという高いスループットを達成した。特に在庫密度が90%の高密度環境下では、LNS-PBSに対して38.77%ものスループット向上を示し、既存手法が直面する性能低下に対して高いレジリエンス（堅牢性）を持つことを証明した。また、計算コストを1秒程度の閾値内に抑えつつ、大規模なエージェント数やタスク数に対してもスケーラビリティを維持している。さらに、SKUの分布を考慮するM2M-wSKUの検討を通じて、アイテムの空間配置がシステム性能に与える影響についても示唆を与えている。
M2Mは、まずエージェント、タスク、開始地点、目的地に対する初期の劣最適解を算出する。初期割り当て $\mathcal{X}_0$ は、4つのコスト行列 $\mathcal{C}_{as}, \mathcal{C}_{ad}, \mathcal{C}_{ts}, \mathcal{C}_{td}$ に分解された4次元コストテンソル $\mathcal{C}$ を用いて、最小コストのペアを反復的に割り当てることで構築される。次に、Large Neighborhood Search (LNS) メタヒューリスティクスを用いて解を改善する。具体的には、Shaw Removal演算子によるタスクの削除と、M2Mアルゴリズムを用いたRepair演算子による再割り当てを、Metropolis基準 $P(\text{accept}) = \min(1, \exp(-\Delta / T))$ に基づいて反復的に行う。経路計画にはPriority Based Search (PBS) を用い、タスクのセグメントごとに衝突のない経路を算出する。M2M-wSKUでは、KD-Treeを用いた近傍探索により、コスト関数に $w_{SKU}$ 項を追加してSKUの空間分布を制御する。
$27 \times 50$ の離散2次元グリッド環境において、3種類のレイアウト（Restricted, Open-top, Open）と3つの在庫密度（30%, 60%, 90%）を用いた8時間のシミュレーション実験を実施した。エージェント数 $M=10$、最大アクティブタスク数 $N=120$、SKU数 $30$ と設定し、10回の試行の平均値を評価している。LNS-PBSをベースラインとして、タスクスループット、計算時間、スケーラビリティを指標とした。実験の結果、在庫密度30%においてM2MはRestrictedで4.95%、Open-topで6.13%のスループット向上を示した。計算時間はM2Mで $1.15 \pm 0.03\text{s}$ と、ベースラインの $1.07 \pm 0.01\text{s}$ と同等の性能を維持している。
M2Mは、環境が「Open」になるほど既存手法との差が縮小する傾向があるが、高密度な在庫環境（90%密度）では圧倒的な優位性を示す。これは、従来の1対1への変換手法が、選択肢の多いMany-to-Manyの設定において最適性を著しく損なうためと考えられる。一方で、M2M-wSKUが標準のM2Mを明確に上回らなかった点は、アイテムを分散させるための追加計算が必ずしも即時のスループット向上に直結しない可能性を示唆している。スケーラビリティに関しては、マップサイズを $61 \times 100$ に拡大すると、エンドポイントの増加に伴い対応可能なエージェント・タスク数が $M=50, N=50$ まで低下するという限界も確認されており、さらなる大規模環境への対応が今後の課題である。
本研究では、従来の Multi-Agent Pickup-and-Delivery (MAPD) が想定していた「1つのタスクに対して1つのピックアップ・デリバリー地点」という制約を拡張し、SKU（Stock Keeping Unit）識別子によって追跡されるアイテムが複数の場所に存在し得る「Many-to-Many MAPD」問題を定義している。この問題は、アイテムの保管・回収場所の選択肢が複数存在するため、NP困難な4次元の割り当て問題へと発展する。提案手法である Many-to-Many Multi-Agent Pickup and Delivery (M2M) には、推定タスク完了時間を最小化する「M2M」と、目的関数に SKU の分布を組み込んだ「M2M-wSKU」の2つのバリアントが存在する。3つの倉庫レイアウトを用いた8時間のシミュレーション実験の結果、M2M は既存の最先端手法と同等以上の性能を示し、異なる環境や在庫密度において平均で最大 22,000 タスク多く完了するという高いスループットを達成した。
本研究では、従来の1対1のMAPD（Multi-Agent Pickup-and-Delivery）設定とは異なり、タスク、エージェント、ピックアップ地点、デリバリー地点の4要素を同時に決定する必要がある、NP困難な「Many-to-Many MAPD」問題を扱う。提案手法であるM2Mは、まずエージェント・タスク・開始地点・目的地に対する初期の劣最適解を算出し、その後、Large Neighborhood Search (LNS) メタヒューリスティクスを用いて指定時間内に割り当てを反復的に改善した後、経路計画ソルバーとしてPriority Based Search (PBS) を用いる。コスト関数には、タスク完了時間の総和を最小化する標準的なM2Mと、SKU（在庫管理単位）の空間分布を考慮して将来の性能向上を図るM2M-wSKUの2つのバリエーションが存在する。3つのレイアウトと3つの在庫密度を用いた8時間の倉庫シミュレーションによる評価の結果、M2MはベースラインであるLNS-PBSと比較して、タスクスループットにおいて最大で平均22,000タスク、すなわち最大38.8%の向上を達成した。
MAPD問題は、マルチロボット・タスク割り当て（MRTA）とマルチエージェント経路計画（MAPF）の2つのサブ問題に分解される。本研究が対象とするMRTAは、Gerkeyらの分類におけるST-SR-TA（Single Task, Single Robot, Task Assignment）かつタスク間に依存関係がない（No Dependencies）NP困難な問題であり、従来の1対1の割り当てではハンガリアン法やTSPが用いられてきたが、Many-to-manyのケースでは4次元割り当て問題として、高次元ハンガリアン法の修正、貪欲法、あるいは混合整数線形計画法（MILP）によるオフライン手法が提案されている。MAPFに関しては、最適性を保証するConflict Based Search (CBS) や、そのスケーラビリティを改善したECBS、優先度に基づくCooperative A*やPriority Based Search (PBS)、さらにPickup and Deliveryに対応したMLA*やRHCR、模倣学習を用いた手法などが存在する。既存のMAPD手法には、MRTAにハンガリアン法とCBSを組み合わせたCENTRALや、TSPとICBS/最小費用流を併用するTA-Hybrid、LNSと優先度付き計画を用いるRMCAなどがある。本研究では、ハンガリアン法による初期解をLarge Neighborhood Search (LNS) で改善し、PBSで経路計画を行うLNS-PBSを、既存手法の中で最も優れた性能を示すベースラインとして採用している。
Many-to-Many Multi-Agent Pickup and Delivery (M2M-MAPD) 問題は、エージェントの集合 $\mathcal{A}$ と、開始地点の候補集合 $S_i$ および目的地候補集合 $D_i$ を持つタスクの集合 $\mathcal{T}$ が与えられたとき、タスクのスループット（tasks/min）を最大化しつつ、衝突のない経路計画とタスク割り当てを求める問題である。従来の 1-to-1 設定がエージェントとタスクの 2 次元割当問題であるのに対し、本手法ではエージェント、タスク、開始地点、目的地の 4 要素を扱う 4 次元割当問題としてモデル化され、総コストの最小化を目指す。エージェント $a \in \mathcal{A}$ の時刻 $t$ における位置を $p_a(t)$ とすると、移動は無向グラフ $G$ に基づき、隣接頂点への移動または待機として定義され、同一頂点への存在 ($p_a(t) = p_b(t)$) または同一エッジの共有による衝突を回避しなければならない。各タスク $i \in \mathcal{T}$ はタプル $(S_i, D_i)$ で指定され、エージェント $a$ への割り当ては $(i, s, d)$ と表され、ここで $s \in S_i$ かつ $d \in D_i$ である。解は、タスクの順序制約（$s_i$ が $d_i$ より先に訪問されること）を満たし、各エージェントが最大 $K$ 個のタスクを順次実行する形式をとる。最終的な目的は、計算コストを特定の閾値（例：1秒）以下に抑えながら、システム全体の性能であるタスクスループットを最大化することである。
提案手法であるM2Mは、エージェント集合 $\mathcal{A}$ と、開始地点 $s_j$ および目的地 $d_j$ を持つタスク集合 $\mathcal{T}$ を入力とし、多対多のタスク割り当て $\mathcal{X}$ と移動計画を算出する。初期割り当て $\mathcal{X}_0$ は、エージェントの最終目的地からタスクの開始地点、およびタスクの目的地への移動時間を考慮した4次元コストテンソル $\mathcal{C}$ を用いて、最小コストのペアを反復的に割り当てることで構築される。計算量の増大を避けるため、$\mathcal{C}$ は4つのコスト行列 $\mathcal{C}_{as}, \mathcal{C}_{ad}, \mathcal{C}_{ts}, \mathcal{C}_{td}$ に分解して扱われ、各タスクの割り当て長は $K$ に制限される。その後、Large Neighborhood Search (LNS) を用いて解を改善し、Shaw Removal演算子によるタスクの削除と、M2Mアルゴリズムを用いたRepair演算子による再割り当てを、Metropolis基準 $P(\text{accept}) = \min(1, \exp(-\Delta / T))$ に基づいて反復する。さらに、SKUの空間分布を考慮したM2M-wSKUでは、コスト関数に $w_{SKU}$ を用いた項を追加し、KD-Treeを用いた近傍探索により、同一SKUのアイテムが密集または分散するように目的地や開始地点を選択する。最終的な移動計画は、ECBSやPBSなどのMAPFアルゴリズムを用いて、タスクのセグメントごとに計算される。
本実験では、実世界の倉庫物流を模した $27 \times 50$ の離散2次元グリッド環境において、提案手法である $M2M$ および SKU 分布情報をコスト関数に組み込んだ $M2M\text{-}wSKU$ を、既存の SOTA 手法である $LNS\text{-}PBS$（Many-to-Many タスクを距離最小化により One-to-One タスクへ変換して適用）と比較評価する。実験設定では、通路の構造が異なる Restricted, Open-top, Open の3種類のマップを使用し、エージェント数 $M=10$、最大アクティブタスク数 $N=120$、SKU数 $30$ とし、各実験は10回のシミュレーションの平均値として報告される。$M2M$ 系列のパラメータとして、Shaw Removal weights を $1$ および $2$、焼きなまし法の初期温度を $100$、減衰率を $0.95$ に設定し、タスク割り当ての総時間制限を $1$ 秒、タスク削除数を $3$、タスクシーケンス制限を $10$ としている。評価指標には、単位時間あたりの完了タスク数を示す Throughput、タスク割り当てステップの Computation Time、およびエージェント数 $M$ やタスク数 $N$ の増加に伴う Scalability の3点を用いる。なお、MIP や SP は大規模な倉庫環境において計算効率が不十分であるため、ベースラインからは除外されている。
本実験では、提案手法であるM2Mおよびその派生手法M2M-wSKUの性能を、ベースラインであるLNS-PBSと比較し、タスクスループット（tasks/min.）を指標として評価している。3種類のマップ（Restricted, Open-Top, Open）において、在庫密度30%の条件下でM2MはLNS-PBSに対し、Restrictedで4.95%、Open-Topで6.13%の平均スループット向上を示し、環境がより「Open」になるほど手法間の差は縮小する傾向にある。在庫密度を30%, 60%, 90%と増加させた実験では、M2MはLNS-PBSに対してそれぞれ4.95%, 2.40%, 38.77%のスループット向上を達成しており、高密度な環境下でもLNS-PBSのような大幅な性能低下を起こさず、高いレジリエンスを示す。計算時間については、LNS-PBSが $1.07 \pm 0.01\text{s}$、M2Mが $1.15 \pm 0.03\text{s}$、M2M-wSKUが $1.16 \pm 0.04\text{s}$ と、いずれの手法も1秒程度の計算予算内で同等の高い計算性能を維持している。スケーラビリティに関しては、マップサイズ $27 \times 50$ ではエージェント数 $M=150$ かつタスク数 $N=150$ まで1秒以内で対応可能だが、マップサイズを $61 \times 100$ に拡大すると、エンドポイントの増加に伴い $M=50, N=50$ まで低下するという限界が確認された。
本研究の結果、提案手法である M2M は、あらゆるマップタイプにおいて既存の最先端手法である LNS-PBS と同等以上の性能を一貫して示した。特に、在庫密度が増加するシナリオにおいて、LNS-PBS の平均スループットが著しく低下するのに対し、M2M は高い堅牢性を維持することが確認された。また、M2M はその変種である M2M-wSKU を明確に上回っており、アイテムを倉庫内に分散させるための追加的な計算コストが性能向上に寄与しないことが示唆された。さらに、より大規模な環境や、より多くのエージェントおよびタスクを用いた設定においても M2M のスケーラビリティが実証されたが、今後の課題として、エージェント数、タスク数、および環境サイズに対するスケーラビリティのさらなる向上が挙げられている。