本研究は、エージェント、タスク、複数のピックアップ地点およびデリバリー地点の4次元的な割り当て問題である Many-to-Many Multi-Agent Pickup and Delivery (M2M MAPD) を対象とする。従来の M2M 手法は、経路計画による交通状況を考慮せず、推定コストに基づいた割り当てを行うため、特定の通路や交差点に負荷が集中し、混雑を招くという困難がある。タスクは SKU、ソース集合 $S$、デリバリー集合 $D$、リリース時刻 $r$ のタプル $(s, D, r)$ としてオンラインで発生し、エージェントは衝突を避けつつ、指定された期限内にタスクを完了させる必要がある。
提案手法は、タスクのゴールが固定された後に経路を決定する従来のグラフ誘導型手法とは異なり、環境に残された実行履歴（スティグマジー）を読み取ることで、実行可能なソースとデスティネーションの組み合わせの順位付けと、エンドポイント選択後の経路の好みを同時に決定する点に新規性がある。これは、単に固定された目標への移動方法を改善するだけでなく、プランナーに渡される実行可能な目標そのものを最適化するアプローチである。また、フェロモンベースのルーティングではなく、型付けされ減衰するグラフメモリの抽象化としてスティグマジーを採用している。
SGM は、Rolling-Horizon Collision Resolution (RHCR) と Priority-Based Search (PBS) をバックエンドに用いる、イベント駆動型の共有メモリ層である。グラフのノードおよび有向エッジ上に、保持係数 $\gamma$ と時刻 $t$ におけるイベントの寄与 $d_{i,t}$ を用いて $M_{i,t} = \gamma M_{i,t-1} + d_{i,t}$ と更新される減衰するメモリチャネルを保持する。Endpoint Steering では、最短経路上のエッジペナルティの総和を割り当てコスト $C_{a,s,d}$ に加算してエンドポイントを選択する。Route Guidance では、有向エッジのコストを $c_{e} = 1 + \alpha \cdot \text{memory\_signal}_{e}$ と定義し、混雑や逆方向のフローを抑制する。
5種類の倉庫レイアウト、3段階のフリート規模（エージェント数 28, 56, 84）、および25個のシードを用いた計15通りの条件下で、既存の M2M および M2M-wSKU ベースラインと比較評価を行った。評価指標には、累積完了タスク数 $C(t)$、スループット $\frac{C(T)}{T}$、サービス時間、移動のブロック数などが用いられた。実験の結果、SGM は全ての条件下でベースラインを上回り、スループットを 20.5% から 36.7% 向上させた。また、プランナーの計算時間を $9.1\%$ 削減することも確認された。
SGM の性能向上は、主にメモリを用いたエンドポイント・ステアリングによってもたらされるが、ルートガイダンスは待機時間や移動のブロック回数を減少させることで実行の効率化に寄与するというトレードオフが存在する。フル SGM は高いスループットを実現するが、割り当て計算のコストが制約となる高負荷時には、計算量あたりのスループットに優れた適応型 SGM (ASGM) を選択する必要がある。今後の課題として、非定常な倉庫環境への拡張や、実ロボットへの展開が挙げられている。
本研究では、many-to-many Multi-Agent Pickup and Delivery (MAPD) において、固定された端点ではなく品目（SKU）のみが指定される状況下で、最新の交通状況を考慮した端点選択と経路優先度を決定する Stigmergic Graph Memory (SGM) を提案している。SGM は、倉庫内のノードおよび有向エッジ上に、最近の実行信号を記録する有界かつ減衰するメモリ層として機能し、衝突回避制約やプランナーの妥当性を損なうことなく、実行可能な端点の順位付けや経路の好みを形成する。5 つのレイアウト、3 つの負荷レベル、各条件 25 個のシードを用いた評価実験において、SGM は 2 つの再構成型 many-to-many 割り当てベースラインを全ての 15 通りのマップ・負荷条件で上回り、スループットを 20.5% から 36.7% 向上させた。この結果は、最近の実行メモリを活用することで、単に固定された目標への移動方法を改善するだけでなく、プランナーに渡される実行可能な目標そのものを最適化できることを示している。
Many-to-Many Multi-Agent Pickup and Delivery (M2M) は、エージェント、タスク、ピックアップ地点、デリバリー地点の4次元的な割り当て問題として定式化されるが、従来の M2M 手法は経路計画による交通状況を考慮せず、推定コストに基づいた割り当てを行うため、特定の通路や交差点への混雑を招く課題がある。本論文では、環境の変化を記憶する軽量なメモリ層である Stigmergic Graph Memory (SGM) を提案し、倉庫内のノードおよび有向エッジ上に減衰する信号を保持することで、最近の実行パターンをエンドポイントのスコアリングや経路の優先順位付けに反映させる。SGM は、スティグマジー（環境を通じた間接的な情報共有）に着想を得ており、コントローラーが実行中の交通状況を考慮して、実行可能なエンドポイントと経路を同時に選択することを可能にする。5つのレイアウト、3つの負荷レベル、各条件25個のシードを用いた評価実験において、SGM はすべての 15 通りの条件下でスループットを向上させ、M2M に対して 20.5% から 36.7% の改善を達成した。この性能向上は、経路コストや候補予算の差によるものではないことが、ルーティング制御およびマッチド・キャップ（matched-cap）制御を用いた比較実験によって示されている。
Multi-Agent Pickup and Delivery (MAPD) は、マルチロボットタスク割り当て（MRTA）と衝突回避を目的とした Multi-Agent Path Finding (MAPF) を組み合わせた問題であり、頂点やエッジの衝突制約下で、オンラインにピッキングと配送タスクを実行する。従来の MAPD は、タスク割り当てと経路計画を統合する手法や、デッドラインを考慮する手法、ロボットの運動学を考慮する手法などが存在するが、本研究が扱う Many-to-Many (M2M) MAPD は、各 SKU リクエストに対して複数のソースとデスティネーションを許容する一般化された形式である。M2M は、エージェント、タスク、ピッキング場所、配送場所の 4 次元的な割り当て問題として定式化され、従来の 1 対 1 の MAPD よりもスループットを大幅に向上させる。提案手法である Stigmergic Graph Memory (SGM) は、タスクのゴールが固定された後に経路を決定する従来のグラフ誘導型手法とは異なり、実行履歴を読み取ることで、実行可能なソースとデスティネーションの組み合わせの順位付けや、エンドポイント選択後の経路の好みを決定する点に独自性がある。また、SGM は、環境に残された痕跡を通じて間接的に協調するスティグマジーの概念を、フェロモンベースのルーティングアルゴリズムとしてではなく、型付けされ減衰するグラフメモリの抽象化として採用している。
本研究では、倉庫を無向グラフとしてモデル化し、エージェントが離散的なタイムステップごとに現在の頂点に留まるか隣接するエッジへ移動する、Many-to-Many Multi-Agent Pickup and Delivery (MM-MAPD) 問題を定義している。タスクはオンラインで発生し、各リクエストは SKU、ソース集合 $S$、デリバリー集合 $D$、およびリリース時刻 $r$ のタプル $(s, D, r)$ で表され、時刻 $t$ において未完了のタスク集合 $\mathcal{R}_t$ が存在する。タスクのインスタンス化により、エージェント $a$、ソース $s$、デリバリー先 $d$ が割り当てられ、エージェントは $t+d$ までに $s$ を訪問する必要がある。制約条件として、同一時刻に複数のエージェントが同じ頂点を占有することや、同一のエッジを逆方向に通行すること（衝突）が禁止されている。目的関数は、プランニングホライゾン $T$ の終了時までに完了したタスク数 $N(T)$ を最大化する長期的なスループットの最大化であり、タスクの実現可能性と衝突回避を両立させつつ、タスクの割り当てと衝突のない経路計画を決定する必要がある。本問題の核心的な課題は、エンドポイントの選択が経路計画の前に将来のトラフィック分布を決定してしまう点にあり、静的な割り当てでは特定の通路やエリアに負荷が集中する可能性があるが、提案手法である Stigmergic Graph Memory (SGM) は、実行履歴を用いて経路計画の目標となる前にエンドポイントの候補をランク付けすることでこの問題に対処する。
Stigmergic Graph Memory (SGM)は、Rolling-Horizon Collision Resolution (RHCR) と Priority-Based Search (PBS) をバックエンドに用いる、イベント駆動型のローリングホライゾン制御器のための共有メモリ層である。SGMは、ノードおよび有向エッジに関する複数の減衰チャネルを保持し、各チャネルの値 $M_{i,t}$ は、保持係数 $\gamma$ と時刻 $t$ におけるイベントによる寄与 $d_{i,t}$ を用いて $M_{i,t} = \gamma M_{i,t-1} + d_{i,t}$ と更新される。Endpoint Steeringでは、エージェントと目的地間の最短経路上のエッジペナルティの総和を、割り当てコスト $C_{a,s,d}$ に加算することで、適切なエンドポイントの選択を誘導する。Route Guidanceでは、有向エッジのコストを $c_{e} = 1 + \alpha \cdot \text{memory\_signal}_{e}$ と定義し、混雑、遅延、ブロッキング、逆方向のフローを抑制し、成功したフローを促進する重み付きコストを算出する。SGMは、割り当て候補を最大64箇所、リクエストあたりのペアを最大32組に制限することで計算量を抑えつつ、RHCR/PBSが元のグラフ制約と衝突回避条件を維持したまま、メモリに基づく優先順位付けのみを行うことで、解の実行可能性を保証している。
本実験では、提案手法であるSGMおよびその適応型であるASGMを、既存手法であるM2MおよびSKU情報を考慮したM2M-wSKUと比較評価する。評価は5種類の倉庫レイアウト、3段階のフリート規模（エージェント数28, 56, 84）、および25個のシードを用いたベンチマークで行われ、フリート規模は駐車容量の30.1%, 60.2%, 90.3%に対応する。評価指標として、タイムステップ $t$ における累積完了タスク数 $C(t)$、スループット $\frac{C(T)}{T}$、最終ウィンドウの活動量、サービス時間、移動のブロック数、および割り当てコストを用いる。統計的有意性の検証には、シードを一致させた二標本Wilcoxon符号付順位検定を用い、Holmの手続きによってファミリーワイズエラー率を制御している。比較対象のベースラインは、移動距離推定に基づくM2Mおよび在庫分布項を加えたM2M-wSKUであり、すべての手法において共通のRHCR/PBSプランナー、ペアリクエストリプレイ、および初期条件が適用される。さらに、経路メモリの端点制御のみ、ルーティングのみ、およびキューの保持を行わない構成によるアブレーション解析や、エッジコストの性質を分離するための制御実験も実施されている。
SGMは、多くのベンチマーク環境において、既存のM2Mベースラインと比較してタスク完了スループットを大幅に向上させる。5つのレイアウトを用いた全15のマップ・フリート条件において、SGMはペアのリクエスト再生下で、より強力なM2Mベースラインに対して20.5%から36.7%の最終スループット向上を実現している。SGMの性能向上は、メモリに基づくエンドポイント選択が、特定の制約領域への作業の集中を段階的に防ぐことで得られる。アブレーション研究により、スループットの向上は主にメモリを用いたエンドポイント・ステアリング（目標地点の決定）によってもたらされることが示されており、ルートガイダンスは、スループットを維持したまま、プランニング時間、待機時間、および移動のブロック回数を減少させることで実行の効率化に寄与する。また、SGMは異なる倉庫構造（迷路状のレイアウトなど）や中規模の転送学習環境においても、タスク完了数を向上させる汎用性を持つ。一方で、ASGMは割り当てのオーバーヘッドを削減するものの、絶対的なタスク完了スループットを犠牲にするため、計算コストとスループットのトレードオフとして機能する。
SGMは、経路計画の前にエンドポイントのインスタンス化を通じて混雑を制御する手法であり、実行履歴に基づき待機や閉塞、交通集中が発生しているソース・デスティネーションの組み合わせへのタスク割り当てを回避する。エンドポイントのみを制御するアブレーション研究では、小規模マップ条件下でフルSGMの $99.3\text{--}100.5\%$ のスループットを維持しており、性能向上の主因がゴール確定後の経路誘導ではなく、実行可能なエンドポイントを選択する段階にあることが示されている。フルSGMは、エンドポイント制御によるスループット維持に加え、グラフメモリによる経路誘導によってプランナーの計算時間を全条件で $9.1\%$ 削減し、待機や閉塞に伴う再計画の負荷を軽減する。スループットを最大化する場合はSGMが最適であるが、割り当て計算のコストが制約となる高負荷時には、計算量あたりのスループットが優れたASGMが適している。SGMは、単に経路コストや静的な高速道路を追加する手法とは異なり、エンドポイントの評価数に依存せず、広範なメモリ設定や異なるマップ環境においても頑健な混雑制御効果を発揮する。
本研究では、多くのエージェントが複数のタスクを扱う many-to-many MAPD において、直近の実行履歴を用いてエンドポイントの生成と経路の優先順位付けを制御する、境界付きグラフメモリ層である SGM を提案した。ペアリングされたベンチマークを用いた評価の結果、SGM はすべてのマップおよびフリートの条件下において、既存の many-to-many ベースラインと比較してタスク完了スループットを向上させた。アブレーション研究により、この性能向上はメモリに基づくエンドポイント生成が主な要因であることが示された。完全な SGM コントローラーは、高いスループットを維持しつつ、待機時間、移動のブロック、ブロックによる再計画、およびプランナーの実行時間を削減することに成功している。これらの結果は、many-to-many MAPD において、パスプランニングの前にどのゴールをプランナーに渡すかを制御することで、混雑を抑制できることを示唆している。今後の課題として、非定常な倉庫環境への拡張や、実ロボットへの展開が挙げられている。