本研究は、エージェントの集合 $\mathcal{A}$ が無向グラフ $\mathcal{G} = (\mathcal{V}, \mathcal{E})$ 上で継続的にタスクを遂行する Lifelong Multi-Agent Path Finding (L-MAPF) を対象としている。従来の倉庫最適化は数学的期待値モデルに基づくものが多く、低レイヤの経路計画との統合が不十分であった。本研究では、2D倉庫レイアウト内にアイテムの一時保管用として「キャッシュ（purple grids）」を導入し、高レベルのキャッシュ管理と低レベルの経路計画を統合した新しいフレームワーク L-MAPF-CM を構築する。タスク $q \in \mathcal{Q}$ はアイテムタイプ $t$ と目的地 $p$ のペア $(t, p)$ で定義され、エージェントの最大積載容量 $C$ の制約下で、タイムステップあたりの完了タスク数（スループット）の最大化を目指す。
コンピュータアーキテクチャの概念を L-MAPF に応用し、キャッシュマップのレイアウト設計と実際の経路計画を直接的に結びつける手法を提案した。具体的には、エージェントのステータスとキャッシュの状態を管理する Task Assigner (TA) を開発し、共有ロック（Read Lock）と排他的ロック（Write Lock）を用いたロッキングメカニズムを導入した。これにより、エージェント間のアイテム競合を防ぎつつ、L-MAPF アルゴリズムとの互換性を維持した動的なタスク割り当てを実現している。また、キャッシュ置換ポリシー（LRU, FIFO, RANDOM）や多様なタスク分布を用いた広範な評価により、キャッシュ機構がスループット向上に寄与することを実証した。
提案手法 L-MAPF-CM は、TA がエージェントのステータスを `SF_GET`（棚へ移動）、`CA_GET`（キャッシュから取得）、`CA_ADD`（キャッシュへ追加）、`UP_END`（荷降ろしポートへ移動）などの間で管理する状態遷移マシンに基づいている。キャッシュの整合性を保つため、TA はロック機構を用いてアイテムの読み書きを制御し、「Hold and Wait」条件を回避する設計により、デッドロックおよびスターベーションの発生を防いでいる。経路計画には LaCAM アルゴリズムを使用し、キャッシュグリッドを介してエージェントが効率的にアイテムを取得できる環境を構築する。キャッシュの管理には LRU、FIFO、RANDOM といった標準的な置換ポリシーを適用可能である。
$27 \times 71$ の倉庫マップを用い、LaCAM をパス生成に使用して性能を検証した。実験設定として、シングルポートおよび 4 つの作業グループによるマルチポートシナリオ、さらに MK 分布、7:2:1 分布（Zhang）、および実データに基づく RDD 分布の 3 種類のタスク分布を用いた。評価の結果、キャッシュ数が増加するにつれてキャッシュヒット率とスループットが向上し、ほとんどの条件下でキャッシュなしのベースラインを上回る性能を確認した。一方で、エージェント数が 256 に達すると LaCAM の特性による激しい交通渋滞が発生し、スループットが急落するという限界も明らかになった。
L-MAPF-CM の性能向上には、高いキャッシュヒット率とスムーズなトラフィックフローの維持が不可欠であることが示された。エージェント数が増加すると、キャッシュによる改善幅が減少する傾向があるため、高密度な環境下での課題が残されている。今後の展望として、タスク順序を管理するよりスマートな TA の開発、データ駆動型の置換ポリシー、交通渋滞を回避する手法、および階層型キャッシュシステムの設計が挙げられている。これらにより、より複雑な実世界の倉庫運用シナリオへの適応が期待される。
本研究では、倉庫運用等の実世界に近いシナリオを想定した Lifelong Multi-Agent Path Finding (L-MAPF) において、高レベルのキャッシュストレージと低レベルの経路計画を統合した新しいメカニズムである L-MAPF-CM を提案している。この手法では、アイテムの一時保管用として「キャッシュ」と呼ばれる新しい種類のマップグリッドを導入し、タスクアサイナー (TA) がロッキングメカニズムを用いて、エージェントのステータスに基づきターゲット位置を動的に割り当てることで、キャッシュグリッドと L-MAPF アルゴリズム間の差異を埋めている。評価実験では、異なるキャッシュ置換ポリシーおよびタスク分布を用いて L-MAPF-CM の性能を検証しており、特にキャッシュヒット率が高く、交通状況がスムーズな条件下において性能向上が確認されている。
本研究では、エージェントが目標地点に到達するたびに新たな目標が割り当てられる Lifelong Multi-Agent Path Finding (L-MAPF) において、コンピュータアーキテクチャの概念を応用した動的なキャッシュ配送メカニズムである L-MAPF-CM を提案している。従来の倉庫最適化手法は数学的期待値モデルに基づくものが多く、低レイヤの経路計画との統合が不十分であったが、本手法はキャッシュマップのレイアウト設計と実際の経路計画を直接的に結びつけている。提案手法の核となる Task Assigner (TA) は、状態遷移マシンとロック機構に基づき、エージェントのステータスとキャッシュの状態を管理することで、L-MAPF アルゴリズムとの互換性を確保しつつタスク割り当てを行う。実験では、入力分布、エージェント数、キャッシュ数、およびキャッシュ置換ポリシーを変化させて評価を行っており、高いキャッシュヒット率とスムーズなトラフィックフローが L-MAPF-CM の性能向上に不可欠であることを示している。
Lifelong Multi-Agent Path Finding (L-MAPF) は、エージェントの集合 $\mathcal{A}$ が無向グラフ $\mathcal{G} = (\mathcal{V}, \mathcal{E})$ 上で、動的かつ継続的にタスクを遂行する問題である。各エージェントは、棚（item type $t$ を保持）、通路、荷降ろしポート、およびキャッシュ領域（purple grids）からなる2D倉庫レイアウトにおいて、タスクキュー $\mathcal{Q}$ から割り当てられた目標地点へ移動する。タスク $q \in \mathcal{Q}$ はアイテムタイプ $t$ と目的地となるポート $p$ のペア $(t, p)$ で定義され、エージェントの最大積載容量は $C$ と制限される。本研究の目的は、タイムステップあたりの完了タスク数を表すスループットを最大化することである。エージェントの行動は隣接頂点への移動または待機（self-loop）のいずれかであり、各アクションは単位時間 $1$ を要する。タスクアサイナー (TA) は、エージェントが目標地点に到着するたびに、$\mathcal{Q}$ から新しい目標地点を決定し、アイドル状態のエージェントに割り当てる。
MAPFは、衝突を回避しつつコスト関数を最小化する経路を求めるNP困難な問題であり、各エージェントを独立に計画する分離型（Decoupled）、全エージェントを同時に計画する結合型（Coupled）、および衝突時のみ結合する動的結合型（Dynamically coupled）の手法が存在する。代表的な手法として、最適解を求める中央集権的なConflict-Based Search (CBS) やその劣最適解版であるECBS、EECBS、およびスケーラビリティに優れたPrioritized Planning (PP) やPBS、LaCAMなどが挙げられる。Lifelong MAPF (L-MAPF) は、エージェントが目標に到達するたびに新たな目標が割り当てられる継続的な設定であり、問題全体を解く手法、各タイムステップで全経路を再計画する手法、および目標到達時のみ再計画する手法の3種に大別される。本研究では、タスクが事前に未知であるオンライン設定のL-MAPFに焦点を当て、従来の倉庫設計におけるキャッシュ（一時保管エリア）の研究がレイアウト設計に留まっていたのに対し、低レベルの経路計画の観点からキャッシュの活用を評価する。
L-MAPF-CMは、エージェントの移動時間を短縮するためにキャッシュグリッド（一時保管エリア）を導入したLifelong Multi-Agent Path Findingのフレームワークである。この手法では、タスクアサイナ（TA）がキャッシュの整合性を保つために、共有ロック（Read Lock）と排他的ロック（Write Lock）を用いたロック機構を導入しており、これによりエージェントがキャッシュ内のアイテムを読み取る際に他のエージェントによってアイテムが書き換えられる競合状態を防いでいる。TAは状態遷移図に基づき、エージェントのステータスを `SF_GET`（棚へ移動）、`CA_GET`（キャッシュから取得）、`CA_ADD`（キャッシュへ追加）、`UP_END`（荷降ろしポートへ移動）などの間で管理し、キャッシュの利用可能性に応じて動的にターゲットを更新する。アルゴリズムは、ロック取得時に「Hold and Wait」条件を回避するように設計されているため、デッドロックおよびスターベーションが発生しないことが保証されている。実験では、LRU、FIFO、RANDOMといったキャッシュ置換ポリシーを比較しており、キャッシュなしのベースラインと比較してスループットとキャッシュヒット率の向上が示されている。
本実験では、キャッシュ機構を用いたLifelong Multi-Agent Path Finding（L-MAPF-CM）の性能を、キャッシュを持たないベースライン（L-MAPF）と比較評価している。実験は$27 \times 71$の倉庫マップを用い、LaCAMアルゴリズムをパス生成に使用して、シングルポートおよびマルチポート（4つの作業グループ）のシナリオで実施された。評価指標にはスループットとキャッシュヒット率が用いられ、タスク分布としてMK分布、7:2:1分布（Zhang）、およびKaggleのデータに基づく実データ分布（RDD）の3種類が設定されている。結果として、キャッシュ数が増加するにつれてヒット率とスループットは向上し、L-MAPF-CMはほとんどの条件下でベースラインを上回るが、エージェント数が増加するとその改善幅は減少する傾向にある。また、キャッシュ置換ポリシー（LRU, FIFO, RANDOM）による性能差は限定的であった。限界として、エージェント数が256に達すると、LaCAMの特性に起因する激しい交通渋滞が発生し、スループットが急落する現象が確認されており、マップ設計の改善やより高度なタスク割り当て・キャッシュ制御アルゴリズムの導入が必要であることが示唆されている。
本研究では、Lifelong Multi-Agent Path Finding (L-MAPF) の性能向上を目的とした手法である L-MAPF-CM を提案している。具体的には、一時的なアイテムの保管と入れ替えを行うための新しいマップグリッド型である「cache」を導入し、計画解の安定性を高めるためのキャッシュ・ロッキング機構を考案した。様々なキャッシュ置換ポリシーとタスク分布を用いた評価実験の結果、L-MAPF-CM はほとんどのテスト設定において性能向上を示した。分析により、高いキャッシュヒット率とスムーズなトラフィックの維持が L-MAPF-CM の性能において極めて重要であることが明らかになった。今後の展望として、タスク順序を管理するスマートな Task Assignment (TA) の開発、キャッシュヒット率を向上させるデータ駆動型の置換ポリシー、交通渋滞回避手法の実装、および階層型キャッシュシステムの設計が挙げられている。