本研究は、自動搬送車（AGV）を用いた中央集権的な生涯型フリート管理システム（FMS）におけるマルチエージェント経路計画（MAPF）の評価を対象としている。従来のLifelong MAPF（LMAPF）研究は、離散的なグリッド上の移動を仮定するpebble motion modelなどの簡略化されたモデルに依存しており、実世界のAGVが持つ動力学的な制約、通信遅延、および実行時の不確実性を十分に考慮できていないという困難があった。
従来のLMAPF研究が無視してきた、物理ベースの運動モデルや実行環境の不確実性を統合的に扱える初のオープンソース・シミュレーション・ソフトウェアであるLSMARTを開発した。単なる経路計画の評価に留まらず、「いつ計画を行うか」「どのように計画を行うか」「計画失敗時にどのようにリカバリを行うか」という、現実的なFMS構築における3つの主要な設計課題を体系的に検証可能な枠組みを提供した点が新規である。
LSMARTは、プランナー呼び出しポリシー、インスタンス生成器、MAPFプランナー、失敗時ポリシー、Action Dependency Graph (ADG)、AGVフリート、および物理ベースシミュレータの7つのモジュールで構成される。プランナーの起動には、一定周期で行う周期的なポリシーと、タスク完了等のイベントに応じるイベントベースのポリシーがある。インスタンス生成器はADG上でcommit cutを計算して目標を割り当てる。失敗時ポリシーは、プランナーが解を見つけられない場合に、全エージェントの一時停止や、Guided PIBT、LRGWといった特定の回避策を選択して制御する。各AGVはPID制御器とアクションキューを備え、差動駆動モデルなどの連続時間での動作を行う。
warehouse、maze、empty、random、roomの6種類のマップを用い、差動駆動ロボットモデル（最大速度 $v_{\text{max}}$、最大加速度 $a_{\text{max}}$、最大角速度 $\omega_{\text{max}}$）を想定して実験を行った。評価指標にはスループットと失敗時方策の呼び出し率を用いた。実験の結果、windowed PBSを用いた設定が計画負荷と失敗率を抑え高いスループットを達成した。また、エージェント密度が高い場合は計画窓 $w$ と呼び出し周期 $T$ を長く設定することが有益である一方、エージェントモデルの精度向上やプランナの最適性を追求すると、解の質は向上するものの計算スケーラビリティが著しく低下するというトレードオフが確認された。
本研究の成果は、現実的な不確実性がシステム設計に与える影響を明らかにしたが、シミュレータの拡張性に関する課題も残されている。具体的には、現在の4連結格子以外のグラフ構造への対応や、AGVよりもさらに複雑な運動力学を持つロボットへの対応が今後の課題として挙げられている。
本研究では、自動搬送車（AGV）を用いたフリート管理システム（FMS）におけるマルチエージェント経路計画（MAPF）アルゴリズムを評価するための、オープンソースのシミュレータであるLSMARTを提案している。従来のMAPFやLifelong MAPF（LMAPF）の研究は、エージェントの運動学的な制約や通信遅延、実行時の不確実性を無視した簡略化されたモデルに依存する傾向があったが、LSMARTはこれらを考慮した現実的なシミュレーションを可能にする。具体的には、FMSにおける設計上の重要な選択肢として、計画と実行の並列化に伴う「いつ計画を行うか」、多様なプランナが存在する中での「どのように計画を行うか」、およびプランナが有効な解を返せない場合の「どのようにリカバリを行うか」という3つの課題を統合的に扱っている。本論文では、これらの設計選択肢に対して最先端の手法を用いた実験を行い、中央集権的なLMAPFシステムを効果的に構築するための指針を提示している。
LSMARTは、自動搬送車（AGV）を用いた中央集権的な生涯型フリート管理システム（FMS）において、あらゆるマルチエージェント経路計画（MAPF）アルゴリズムを評価可能な初のオープンソース・シミュレーション・ソフトウェアである。従来のLMAPF研究は、離散的なグリッド上での移動を仮定するpebble motion modelに基づいた簡略化された設定で行われることが多かったが、LSMARTは動力学的な制約、通信遅延、実行時の不確実性を考慮した物理ベースのシミュレーションを可能にする。本システムは、MAPFプランナー、問題インスタンス生成器、プランナーを呼び出すタイミングを決定する呼び出しポリシー、および計画失敗時に回復するための失敗ポリシーという4つの独立したモジュールで構成されている。特に、プランナーの呼び出しタイミングや、最適性とエージェントモデルの精度（計算量とのトレードオフ）の選択、および計画失敗への対処といった設計上の意思決定が、現実的なFMS環境下でどのように性能に影響するかを詳細に検証できる。数千台規模のAGVを用いた大規模な実験が可能であり、理想化されたモデルでは見落とされていた、実行環境の不確実性がシステム全体の設計選択に与える影響を明らかにすることができる。
本セクションでは、Lifelong Multi-Agent Path Finding (LMAPF) および Automated Guided Vehicle (AGV) Fleet Management System (FMS) の基礎定義と、既存研究における設計上の課題が整理されている。標準的なLMAPFは、エージェントが目標に到達するたびに新たな目標が割り当てられる設定であり、単位時間あたりの目標到達数であるスループットの最大化を目的とする。一方、実世界のFMSにおけるAGVは、連続時間における位置 $\mathbf{p}$、向き $\theta$、時刻 $t$ からなる状態 $s = (\mathbf{p}, \theta, t)$ を持ち、速度や加速度の制約を受ける差動駆動ロボットとしてモデル化される。既存のLMAPF研究の多くは、隣接頂点への移動または待機のみを許容する簡略化された pebble motion agent モデルに基づいているが、これは通信遅延や実行時の不確実性、AGVの運動学的制約を十分に考慮できていない。
FMSの設計における主要な検討事項として、プランナーの呼び出し方（一定周期で行う periodic または特定のイベント時に行う event-based）、重複する目標への対処法（一時的な目標を割り当てる手法や、目標到達後の動きを許容する MAPF4L など）、およびプランニング失敗時の回避策（待機動作を追加する LRGW や、ルールベースの回避策、Guided PIBT など）が挙げられる。提案手法である LSMART は、従来の pebble motion モデルに依存せず、ADG (Action Dependency Graph) を用いた実行ポリシーを採用することで、多様な呼び出し方、目標生成、および失敗回避策を体系的に比較・検証可能な環境を提供している。
LSMARTは、Lifelong Multi-Agent Path Finding (LMAPF) の評価を目的とした、拡張性の高いマルチエージェント・テストベッドである。システムは、プランナー呼び出しポリシー、インスタンス生成器、MAPFプランナー、失敗時ポリシー、Action Dependency Graph (ADG)、AGVフリート、および物理ベースシミュレータの7つのモジュールで構成される。プランナー呼び出しポリシーには、一定時間ごとにプランナーを起動する周期的なポリシーと、AGVがプランナーの計算完了前に現在のタスクを終える可能性がある場合に起動するイベントベースのポリシーの2種類が用意されている。インスタンス生成器は、ADG上でcommit cutを計算して各AGVの開始状態を決定し、目標地点を割り当てる役割を担い、distinct-one-goal、one-goal、windowed-multi-goalsの3つの形式をサポートする。失敗時ポリシーは、プランナーが衝突回避経路を見つけられなかった際の挙動を制御し、PIBTによるゼロからの再計画や全エージェントの一時停止、あるいは衝突経路を利用したGuided PIBTやLRGWといった手法を選択可能である。本システムは、pebble motionモデルやdifferential driveモデルなど、多様なAGVの運動モデルや連続時間での計画に対応しており、各AGVはPID制御器とアクションキューを備えた状態でシミュレータ上で並列に動作する。
本実験では、LSMARTの主要な設計要素であるインスタンス生成器、プランナ呼び出し方策、失敗時方策、およびエージェントモデルとプランナの最適性のトレードオフを評価している。実験は、warehouse、maze、empty、random、roomといった6種類のマップを用い、差動駆動ロボットモデル（最大速度 $v_{\text{max}}$、加速度 $a_{\text{max}}$、角速度 $\omega_{\text{max}}$）を想定し、スループットと失敗時方策の呼び出し率を指標として、エージェント数やマップサイズを変化させて実施された。インスタンス生成器の比較では、windowed PBSを用いたwindowed設定が、計画負荷を軽減し失敗率を抑えることで、一貫して高いスループットを達成することが示された。プランナ呼び出し方策については、エージェント密度が高い場合、計画窓 $w$ を長くし、呼び出し周期 $T$ を長く設定することが有益である一方、実行と計画の不一致（commit cutの推定誤差）により、頻繁な再計画が必ずしも同期を改善しないという課題が明らかになった。失敗時方策の評価では、衝突回避経路の質に応じて、LRGWが有効な場合と、PIBTのように待機を避けて移動を優先する手法が有効な場合があることが示された。最後に、エージェントモデルの精度向上やプランナの最適性（CBS等）の追求は、解の質を向上させるものの、計算スケーラビリティを著しく低下させるというトレードオフが確認された。
本研究では、運動力学的な制約、通信遅延、および実行時の不確実性を考慮したマルチエージェント経路計画（MAPF）アルゴリズムを評価可能な、初のオープンソースシミュレータであるLSMARTを提案している。LSMARTは、MAPFプランナー、インスタンス生成器、プランナーの呼び出しポリシー、および失敗時の対応ポリシーという4つの設計要素をカスタマイズ可能なモジュールとして統合しており、FMS（フリート管理システム）における新しいアルゴリズムの実験を可能にする。著者らは、従来のMAPF研究では検討されてきたものの、LSMARTのような現実的な設定下では評価されてこなかった既存手法の比較実験を行い、各設計選択肢の有効性を実証した。今後の課題として、シミュレータにおける4連結格子以外のグラフ構造への対応や、AGVよりも複雑な運動力学を持つロボットへの対応が挙げられている。