本研究は、エージェントが目標達成後に即座に次の目標を割り当てられる Lifelong MAPF（または MAPD）における移動時間の短縮を目的としている。従来の倉庫レイアウト最適化は静的な設計に依存しており、時間とともに変化する入力分布への対応が困難であった。提案手法は、アイテムの保管・置換を可能にする新しいマップグリッド型を導入し、動的なタスク割り当てと状態制御を実現する。評価では、キャッシュなしの Lifelong MAPF（LaCAMをソルバーとして使用）をベースラインとしている。
コンピュータアーキテクチャのキャッシュ設計に着想を得た、動的なキャッシュ配送メカニズム CAL-MAPF を提案した。具体的には、アイテムの一時保管を行う「cache」グリッド、計画の安定性を高めるための Read Lock および Write Lock からなるロッキング機構、およびエージェントのステータス（Status 0–4）を管理する Task Assigner (TA) を導入している。実験を通じて、性能向上に不可欠な要因として「適切な入力タスク分布」「高いキャッシュヒット率」「スムーズなトラフィック」の3点を特定した。
エージェントの集合 $\mathcal{A}$ が無向グラフ $\mathcal{G} = (\mathcal{V}, \mathcal{E})$ 上で、タスクキュー $\mathcal{Q}$ に基づき移動する問題を扱う。マップは棚 (shelves)、通路 (aisles)、荷降ろしポート (unloading ports) に加え、新たにキャッシュグリッドで構成される。TA は状態遷移マシンを用いて、エージェントがアイテムを運搬する際の目標地点とタスクを管理する。キャッシュへのアクセスにおける競合を防ぐため、複数エージェントによる取得を許容する Read Lock と、アイテム挿入時の排他的な Write Lock を用いた共有ロック機構を実装している。キャッシュ置換ポリシーには LRU、FIFO、RANDOM の3種類を検討している。
27x71 の倉庫マップ（1600個の棚、最大80個のキャッシュ、4つのポート）を用い、キャッシュ数 $\{16, 32, 48, 64, 80\}$ およびエージェント数を変化させて検証した。タスク分布には MK分布、7:2:1分布 (Zhang)、および Real Data Distribution (RDD) の3種類を採用した。実験の結果、キャッシュ数の増加に伴いキャッシュヒット率と makespan が改善し、多くの設定でベースラインを上回る性能を示した。
CAL-MAPF は特定のタスク分布やマップ構成において有効であるが、エージェント数が増加すると性能が低下する限界がある。特にエージェント数が256に達すると、交通渋滞の影響でキャッシュのロック機構が妨げられ、ヒット率の低下と makespan の悪化を招くことが確認された。したがって、本手法の優位性を維持するためには、高いキャッシュヒット率を維持できるようなスムーズなトラフィックの確保が極めて重要である。
本研究では、エージェントが目標達成後に即座に次の目標を割り当てられるLifelong Multi-Agent Path Finding (MAPF) の性能を向上させるため、Caching-Augmented Lifelong MAPF (CAL-MAPF) という新しいメカニズムを提案している。CAL-MAPFは、アイテムの一時的な保管と交換を行うための「cache」と呼ばれる新しいマップグリッドと、計画解の安定性を高めるためのロッキングメカニズムを導入しており、エージェントへの目標割り当てと状態制御を行うTask Assigner (TA) を備えている。実験では、様々なキャッシュ置換ポリシーと入力タスク分布を用いて評価が行われ、性能に大きく影響する要因として、適切な入力タスク分布、高いキャッシュヒット率、およびスムーズなトラフィックの3点が特定された。結果として、CAL-MAPFは特定のタスク分布、マップ、およびエージェント構成において、性能を向上させる可能性が示されている。
本研究は、エージェントが目標地点に到達するたびに新たな目標が割り当てられる Lifelong MAPF（または MAPD）において、コンピュータアーキテクチャのキャッシュ設計に着想を得た動的なキャッシュ配送メカニズムである CAL-MAPF を提案している。従来の倉庫レイアウト最適化は静的なストレージ設計に依存しており、時間とともに変化する入力分布への対応が困難であったが、提案手法は新しいマップグリッド型を導入することで、アイテムの一時的な保管と置換を可能にしている。CAL-MAPF は、計画の安定性を高めるためのロック機構、エージェントのステータス管理と目標割り当てを行う Task Assigner (TA) で構成され、既存の Lifelong MAPF アルゴリズムや倉庫戦略に柔軟に適応できる。実験を通じて、性能に大きく影響する要因として「入力タスクの分布」、「キャッシュヒット率」、および「マップ設計」の3点が特定されており、特定のタスク分布やマップ・エージェント構成において性能向上の可能性が示されている。
Lifelong Multi-Agent Path Finding (Lifelong MAPF) は、エージェントの集合 $\mathcal{A}$ が無向グラフ $\mathcal{G} = (\mathcal{V}, \mathcal{E})$ 上で、タスクキュー $\mathcal{Q}$ に基づき継続的に移動を行う問題である。各タスク $q \in \mathcal{Q}$ は、特定のアイテムタイプ $t$ を目的地の位置 $v_{dest}$ へ運搬することを要求し、アイテムは到達可能な頂点 $v_{item}$ に配置される。エージェントは、タスクアサイナー (TA) によって割り当てられた目標地点へ向かって、隣接する頂点への移動または待機（自己ループ $e \in \mathcal{E}$）を単位時間で行い、目標到達後は即座に次のタスクが割り当てられる。マップは、アイテムを格納する棚 (shelves)、通路 (aisles)、およびアイテムを届ける荷降ろしポート (unloading ports) の3種類のグリッドで構成される。実験設定では、キャッシュグリッドの数を 80 から 16 まで変化させ、キャッシュヒット率への影響を検証する。また、エージェントは必ず荷降ろしポート $v_{port} \in \mathcal{V}_{port}$ を経由して目的地へ向かう必要があり、ポート間の直接遷移は禁止されている。
MAPFは、複数のエージェントに対して衝突のない経路を求め、与えられたコスト関数を最小化するNP困難な問題であり、各エージェントを独立に計画するDecoupled戦略、全エージェントを同時に計画するCoupled戦略、および衝突時のみ統合を行う動的Coupled戦略に分類される。最適解を求める手法としてConflict-Based Search (CBS) やその劣最適解版であるECBS, EECBSがあり、一方でPrioritized Planning (PP) やPBS, PIBTなどはスケーラビリティと効率性に優れている。Lifelong MAPFは、エージェントが目標に到達するたびに新たな目標が割り当てられる継続的な問題であり、全体解法、一定時間ごとの再計画、および目標到達時の再計画という手法が存在し、特にMAPF-LNSやLaCAMが主要な手法として挙げられる。また、計算機科学におけるキャッシュは、LRUやFIFOなどのポリシーを用いて頻繁に使用されるデータを一時保存し、アクセス速度を向上させる役割を担う。倉庫内の自動保管回収システム（AS/RS）における保管戦略には、空間利用率の高いランダム保管、移動距離を最小化する最寄保管、需要頻度に基づく回転率ベースの保管などがあり、本研究ではこれらとキャッシュの概念を組み合わせた運用状態（Status 0〜4）を定義している。
本セクションでは、Lifelong Multi-Agent Path Finding (MAPF) において、エージェントの移動時間を短縮するためのキャッシュ機構を導入した「Caching-Augmented Lifelong MAPF (CAL-MAPF)」フレームワークを提案している。この手法では、アイテムの一時保管場所として「キャッシュグリッド」を導入し、Task Assigner (TA) が状態遷移マシンを用いてエージェントの目標地点とタスクを管理する。キャッシュへのアクセスにおける競合（race condition）を防ぐため、共有ロックである Read Lock（複数エージェントによるアイテム取得が可能）と、排他的ロックである Write Lock（アイテムの挿入時に使用）からなるロック機構を導入している。アルゴリズムの詳細は Algorithm 1–3 に示されており、TA はエージェントの状態（Status 0–4）に基づき、キャッシュ内へのアイテムの有無やロックの状態を確認しながら、棚、キャッシュ、または荷降ろしポートへの移動を指示する。実験では、キャッシュ置換ポリシーとして LRU、FIFO、RANDOM を比較しており、キャッシュなしの Lifelong MAPF (NONE) と比較して Makespan の改善と Cache Hit Rate の向上が示されている。
本実験では、提案手法であるCAL-MAPFの性能を、キャッシュを用いないLifelong MAPF（LaCAMをソルバーとして使用）をベースラインとして評価している。実験環境は、27x71の倉庫マップ（1600個の棚グリッド、最大80個のキャッシュグリッド、4つの荷降ろしポート）を用い、マルチポートおよびシングルポートの2つのシナリオで、キャッシュ数 $\{16, 32, 48, 64, 80\}$ およびエージェント数を変化させて検証した。タスク分布には、MK分布、7:2:1分布（Zhang）、およびKaggleのデータに基づくReal Data Distribution (RDD) の3種類を採用し、キャッシュ置換ポリシーとしてLRU、FIFO、RANDOMを比較している。結果として、キャッシュ数の増加に伴いキャッシュヒット率とmakespan（全タスク完了時間）が改善し、多くの設定でベースラインを上回ったが、エージェント数が増加すると交通渋滞の影響でヒット率が低下し、CAL-MAPFの優位性が減少する傾向が確認された。特に、エージェント数が256に達すると、渋滞によりキャッシュのロック機構が妨げられ、ヒット率の低下とmakespanの悪化を招くという限界が示されている。
本研究では、Lifelong MAPFの性能向上を目的とした新しいメカニズムであるCaching-Augmented Lifelong MAPF (CAL-MAPF) を提案している。具体的には、一時的なアイテムの保管と置換を行うための新しいマップグリッド型である「cache」を導入し、さらに計画解の安定性を高めるためのキャッシュ・ロッキング機構を考案した。様々なキャッシュ置換ポリシーと入力タスク分布を用いた評価実験を通じて、CAL-MAPFの性能に大きく影響を与える要因として、適切な入力タスク分布、高いキャッシュヒット率、およびスムーズなトラフィックの3点が特定された。実験の結果、CAL-MAPFは特定のタスク分布やマップおよびエージェントの構成において、性能を向上させる可能性が示された。