本研究は、複数のモジュール型ユニット（RubikCells）で構成されるRCWSにおける、動的なマルチエージェント・ピックアップ＆デリバリー（Dynamic-MAPD）問題を扱う。従来のMAPDはタスクが固定されていることを前提とするが、本研究では実行中に既存の注文に新しいSKUが追加される「内部的な注文の進化」を定義している。これにより、タスク数と空間的分布が動的に変化する複雑なマルチゴールMAPD問題となる。ロボットは、複数のアイテムを順次回収して配送する必要があり、納期 $D_j$ の遵守と総フロータイム $\sum_{j \in \mathcal{T}} C_j$ の最小化が求められる。
本論文の主な貢献は、注文の動的変化を体系的に扱うDynamic-MAPD問題を定義したことである。提案手法は、注文の更新イベントをトリガーとして、共有トークンを用いてロボットの経路を逐次的に再計画するイベント駆動型フレームワークである。具体的には、注文を特定のロボットに固定しつつ優先度に基づき再計画するDynamic-TPと、アイドルロボットによる支援を可能にするCooperative-TPの2種類を提案している。これにより、静的な設定や非協力的なベースラインと比較して、動的な環境下でのオーダーフロータイムを大幅に削減することに成功した。
RCWSは $W \times H$ の矩形グリッドグラフ $\mathcal{G} = (\mathcal{V}, \mathcal{E})$ としてモデル化される。提案手法は以下の2つのモードを持つ。
1. **Dynamic-TP (Binding Mode)**: 注文更新時、デッドラインまでの残り時間 $T_{rem} = T_{deadline} - T_{current}$ に基づく優先度付きキューを用いて、緊急度の高い順にトークンを取得する。経路計画には $A^*$ 探索を用い、完全な経路 $\text{Path}_1$ が困難な場合は安全な終点への部分的な経路 $\text{Path}_2$ を生成する。計算量は更新イベントあたり $O(C)$ である。
2. **Cooperative-TP (Cooperative Mode)**: アイドルロボット $r_{idle}$ が、追加アイテムの回収・配送の推定時間 $T_{coop}$ と、元のロボット $r_{bound}$ が全アイテムを回収する推定時間 $T_{base}$ を比較し、$\max(T_{r_{bound}, \text{rem}}, T_{coop}) < T_{base}$ を満たす場合に支援を行う。計算量は $O(N_{idle} \cdot C)$ となる。
$10 \times 10$ および $20 \times 20$ のセルサイズを用いたシミュレーション実験により、Dynamic-TP、Cooperative-TP、およびベースライン（Token Passing, TP-Append）を比較評価した。更新確率 $p$ と追加SKU数 $k$ を変化させた結果、Cooperative-TP（C-TP）が最も高い性能を示した。高動的な環境下では、D-TPのフロータイムが $154.5$、TPが $354.8$ であるのに対し、C-TPは $63.3$ まで削減できることが示された。計算量については、D-TPはロボット数に依存せず $10\text{--}15\text{ ms}$ で安定しているが、C-TPはロボット数が $10$ から $50$ に増えると実行時間が $15\text{ ms}$ から $150\text{ ms}$ へ増加する。しかし、最大構成でも $1$ 秒未満であり、リアルタイム要件を満たしている。
本研究は、RCWSにおける注文の動的な進化をモデル化し、イベント駆動型のトークンパッシングによってリアルタイムな適応を実現した。Dynamic-TPは、ロボットが現在位置から直接ルートを更新することで、動的なタスク追加に対してデッドロックフリーかつ効率的な対応を可能にしている。さらにCooperative-TPは、アイドル状態のリソースを動的に活用することで、システム全体のフロータイムを劇的に改善できることを示した。今後の課題として、より多様な動的注文パターンの調査、異種ロボットシステムの検討、および実世界への実装が挙げられている。
本研究では、ロボットによるセル型倉庫システム（RCWS）において、実行中の注文に対して新たなSKUが追加される「内部的な注文の進化（internal order evolution）」を考慮した、初の動的なマルチエージェント・ピックアップ＆デリバリー（MAPD）問題を定式化している。提案手法はトークン・パッシング・パラダイムに基づいた2つのイベント駆動型オンライン再計画アルゴリズムであり、一つ目の「Dynamic Token Passing」は、注文の追加に伴う分解と優先度ベースのトークン・スケジューリングにより、衝突回避を維持しつつ局所的な再計画を行う。二つ目の「Cooperative Token Passing」は、アイドル状態のロボットが新たに追加されたピックアップ作業を適宜支援することを可能にし、システム全体の効率を向上させる。RCWS環境におけるシミュレーション実験の結果、提案手法は静的な設定や非協力的なベースラインと比較して、注文のフロータイム（order flowtime）を大幅に削減できることが示されている。
本研究では、複数のモジュール型ユニット（RubikCells）で構成されるロボット細胞型倉庫システム（RCWS）における、動的なマルチエージェント・ピックアップ＆デリバリー（Dynamic-MAPD）問題を定義している。RCWSにおける注文は複数のSKUを含み、ロボットはそれらを順次回収して配送する必要があるため、従来のMAPFやMAPDよりも複雑なマルチゴールMAPD問題として定式化される。本論文の核心は、実行中に既存の注文に新しいSKUが追加されるという「内部的な注文の進化」に対応することであり、これに伴いタスクの数と空間的分布が動的に変化する。提案手法として、イベント駆動型の注文更新に対応し、トークン取得後に現在の位置から経路を再計画する「Dynamic Token Passing (Dynamic-TP)」アルゴリズムを提案している。さらに、アイドル状態のロボットが新しく追加されたSKUを含む進行中の注文を一時的に支援することを可能にする「Cooperative Token Passing (Coop-TP)」アルゴリズムへと拡張し、動的な環境下でのリアルタイムな協調制御を目指している。
MAPD（Multi-Agent Pickup and Delivery）の研究は、主にロボット移動型フルフィルメントシステム（RMFS）におけるG2P（goods-to-person）パラダイムに基づき、容量制限付きMAPDや、棚の移動を伴うダブルデック型MAPDなどが提案されてきた。研究の進展により、R2G（robot-to-goods）設定におけるベンチマークとなるToken Passingアルゴリズムや、エネルギー消費・充電、分散協調、タスクの期限（deadline）、外部エージェントの存在、実行遅延といった現実的な制約を考慮した様々な拡張が行われている。また、複数の目的地を順に回るmulti-goal MAPDや、ペイロード制約下で複数のタスクを扱うmulti-task設定も研究されており、大規模環境向けにLarge Neighborhood SearchやTSPベースのオンラインアルゴリズムが提案されている。これらはVRP（Vehicle Routing Problem）とグラフ上で定義される点は共通するが、VRPが衝突回避を考慮しない疎な道路ネットワークを扱うのに対し、MAPDは時空間的な衝突回避が必要な密なグリッド状グラフにおける密結合な協調を必要とする点で異なる。既存研究において、実行中のオーダーに対してSKUが動的に追加される状況を体系的に扱ったものはなく、本研究ではDynamic-MAPD問題を定義し、オーダーの動的な変化にリアルタイムで適応する2つのイベント駆動型Token Passingアルゴリズムを提案する。
本セクションでは、ロボット細胞型倉庫システム（RCWS）における動的MAPD問題の定式化が述べられている。RubikCellは、水平・垂直方向にそれぞれ $W$ および $H$ 個の収納キャビネットを持つ $W \times H$ の矩形グリッドグラフ $\mathcal{G} = (\mathcal{V}, \mathcal{E})$ としてモデル化され、エッジ $\mathcal{E}$ は隣接する頂点間を結ぶ4方向の移動を許容する。タスク集合 $\mathcal{T}$ の各タスク $j \in \mathcal{T}$ は、回収すべきアイテムの集合 $\mathcal{L}_j$ を持ち、実行中に新たなアイテムが追加される動的な性質を持つ。タスクの更新は、確率 $p$ で発生するインジケータ $\mathbb{I}_{j,t}$ に基づき、追加アイテム数 $n_{j,t}$ が空間分布からサンプリングされることでモデル化され、更新後のタスクは $\mathcal{L}'_j = \mathcal{L}_j \cup \mathcal{L}_{new,j}$ となる。各タスクには納期 $D_j$ が設定されており、完了時刻 $C_j \le D_j$ を満たす必要がある。本問題の目的は、移動の実現可能性、衝突回避、および納期制約を遵守しつつ、全タスクの完了時刻の総和である総フロータイム $\sum_{j \in \mathcal{T}} C_j$ を最小化することである。
本セクションでは、動的なMAPD問題に対応するため、従来のToken Passing (TP) 方式を拡張したイベント駆動型のメカニズムを提案している。提案手法は、注文の更新イベントをトリガーとして、共有トークンを用いてロボットの経路を逐次的に再計画するもので、デッドロックフリー性と完全性を維持しつつ、以下の2つの実行モードを提供する。
1. **Dynamic-TP (Binding Mode)**: 各注文は一度割り当てられると特定のロボットに固定される。注文更新時には、デッドラインまでの残り時間 $T_{rem} = T_{deadline} - T_{current}$ に基づく優先度付きキューを用いて、緊急度の高い順にロボットがトークンを取得する。経路計画には $A^*$ 探索を用いた $\text{Path}_1$（完全な経路）を試行し、失敗した場合は安全な終点への $\text{Path}_2$（部分的な経路）を生成する。
2. **Cooperative-TP (Cooperative Mode)**: 待機中のアイドルロボットが、新規追加アイテムの回収を支援することを許可する。協力の条件は、アイドルロボット $r_{idle}$ が追加アイテムを回収して配送する推定時間 $T_{coop}$ と、元のロボット $r_{bound}$ が全アイテムを回収する推定時間 $T_{base}$ を比較し、$\max(T_{r_{bound}, \text{rem}}, T_{coop}) < T_{base}$ を満たすことである。
計算量については、単一の経路計画コストを $C$ とすると、Dynamic-TPの更新イベントあたりの複雑度は $O(C)$ であり、Cooperative-TPではアイドルロボットの数を $N_{idle}$ とすると $O(N_{idle} \cdot C)$ となる。
本研究では、RubikCell構造を持つグリッドベースのロボット細胞型倉庫システム（RCWS）において、動的なSKU更新に対応する4つのタスク計画戦略（提案手法：Dynamic-TP, Cooperative-TP、ベースライン：Token Passing, TP-Append）を、2種類のセルサイズ（$10 \times 10$ および $20 \times 20$）で評価している。評価指標には平均オーダーフロータイム（average flowtime per order）を用い、更新確率 $p$ および追加SKU数 $k$ を変化させることで、動的強度の影響を調査した。実験結果として、すべての戦略において $p$ および $k$ の増加に伴いフロータイムが単調増加するが、提案手法であるCooperative-TP（C-TP）が最も優れた性能を示し、特に高動的な環境下では、D-TPの $154.5$ から TPの $354.8$ に対し、C-TPは $63.3$ までフロータイムを削減できることが確認された。計算量に関しては、D-TPの更新時平均実行時間がロボット数に依存せず約 $10\text{--}15\text{ ms}$ で安定しているのに対し、C-TPはアイドルロボットの評価を行うため、ロボット数が $10$ から $50$ に増えるにつれて実行時間が約 $15\text{ ms}$ から $150\text{ ms}$ へと増加するトレードオフが存在する。しかし、最大構成においても実行時間は $1$ 秒未満であり、実用的なリアルタイム要件を満たしている。
本論文では、ロボット細胞型倉庫システム（RCWS）において、実行中に動的に変化する注文を明示的にモデル化するため、従来のMAPDを拡張したDynamic-MAPD問題を提案している。この問題に対し、注文の更新時に適時かつ一貫した再計画を可能にする、イベント駆動型のトークンパッシング・フレームワークを開発した。提案手法のうち、Dynamic-TPはロボットが現在位置から直接ルートを更新することを可能にし、その協調拡張版では、アイドル状態のロボットを活用して新規追加されたアイテムに対応する。今後の展望として、より多様な動的注文パターンの調査、異種ロボットシステムの検討、および実世界への実装が挙げられている。