マルチエージェント経路計画（MAPF）は、多数のロボットが衝突を回避しながら目的地へ移動する経路を求める問題である。既存の評価手法は、ロボットの運動力学的な制約や実行時の不確実性を考慮しない簡略化されたモデルに依存しており、実世界での性能が不明確である。また、既存の物理エンジンを用いたシミュレータは、ユーザー定義のマップや新しいプランナの統合に多大な工数を要する点や、扱えるロボット数が数百台未満に限定されるというスケーラビリティの課題がある。
SMARTは、物理エンジンベースのシミュレーションと、アクション依存グラフ（ADG）を用いた実行監視フレームワークを組み合わせることで、簡略化されたモデルで生成された経路の堅牢な実行を可能にする。既存の評価ツールとは異なり、多様なMAPFプランナやロボットモデルを容易に統合できるモジュール式設計を採用している。
システムは、シミュレータ、実行監視（EM）サーバ、および各ロボットの実行器（エグゼキュータ）の3つのモジュールで構成される。シミュレータは大規模実験向けのARGoS3と高精度なIsaac Simをサポートする。EMサーバは標準的なMAPF計画を解析し、各ロボットの動作の連続性を保証するType-1エッジと、ロボット間の通過順序を規定するType-2エッジを持つアクション依存グラフ（ADG）を構築する。ADGの構築時には、サイクル衝突によるデッドロックを防ぐため、連続する頂点の間に新たな頂点を挿入してグラフを非巡回化する。各エグゼキュータは、RPCを用いてサーバからアクションを受け取り、PID制御器を用いてシミュレータへ制御コマンドを送信する。
MAPF-LNS2、CBS、PBSといった多様なプランナや、運動力学を考慮した複数のロボットモデルを用いた検証において、実行成功率100%を達成した。ARGoS3を用いた実験では、最大2,000台のロボットをサポートし、大規模な倉庫環境でも約10.0のシミュレーション速度を維持した。また、7台のJetBotを用いた実機検証においても、10回の試行すべてにおいて成功した。
Isaac Simは高精度なモデル化が可能である反面、CPUおよびメモリの消費が激しく、ロボット数が増えるとシミュレーション速度が実時間を下回るというトレードオフがある。今後の課題として、タスクが継続的に発生する生涯MAPFへの拡張、人間との協調を想定した高度な動的障害物モデルの統合、および代替的な実行フレームワークのサポートが挙げられている。
SMART（Scalable Multi-Agent Realistic Testbed）は、マルチエージェント経路計画（MAPF）アルゴリズムを評価するための、現実的かつ効率的なソフトウェアツールです。従来のMAPF研究は簡略化されたロボットモデルに依存することが多く、実世界での性能が不明確であるという課題があります。SMARTは物理エンジンベースのシミュレータを用いることで、ロボットの運動力学や実行時の不確実性といった複雑な要因を考慮した現実的なシミュレーション環境を実現しています。また、アクション依存グラフに基づく実行監視フレームワークを採用しており、多様なMAPFプランナやロボットモデルとのシームレスな統合が可能です。本ツールは数千台規模のロボットへとスケールすることができ、研究者や産業界の専門家が、自身の環境におけるプランナの性能を効率的にテストすることを可能にします。
マルチエージェント経路計画（MAPF）は、既知の環境内で多数のロボットの衝突のない経路を計画する問題ですが、既存の最先端アルゴリズムはロボットの運動力学的な制約や実行時の不確実性を考慮しない簡略化されたモデルに依存しています。本研究では、現実的な設定でMAPFプランナーを評価するためのスケーラブルなソフトウェアツールであるSMARTを提案します。SMARTは、物理エンジンに基づくシミュレータ、経路の実行状況を追跡し実行器と通信する実行モニタリング（EM）サーバ、およびロボットごとの実行器の3つの主要コンポーネントで構成されます。EMサーバは、Action Dependency Graph（ADG）という実行フレームワークを活用することで、簡略化されたモデルで生成された経路の堅牢な実行を支援します。SMARTは、ロボットの運動力学、衝突力学、通信遅延、実行時の不完全性、および時間的な不確実性といった現実世界の要因を組み込んでいます。ARGoS3やIsaac Simとの統合により、SMARTは数千台のロボット規模までスケールし、一貫した再現可能な結果を得ることが可能です。
マルチエージェント経路計画（MAPF）問題は、2次元グリッドマップから構成される無向グラフにおいて、全ロボットが衝突を回避しながら始点から終点へ移動する経路を求めるもので、一般に移動時間の総和であるsum-of-costの最小化を目的とします。既存研究には、最適性や限定的な劣解を保証する手法、数千台規模のロボットを扱うスケーラビリティ重視の手法、および運動力学や遅延などの現実的な要因を考慮するために、高レベルの衝突回避と低レベルの個別制御を組み合わせた2レベル構成の手法が存在します。計画の実行においては、厳密な時刻同期は効率を低下させ、遅延のたびに再計画を行う手法は計算コストが高いため、Action Dependency Graph（ADG）のような実行フレームワークが有効です。ADGは、各ロボットの動作の連続性を保証するType-1エッジと、共有頂点におけるロボット間の通過順序を規定するType-2エッジを持つ有向グラフとして、動作間の依存関係を記述します。既存の評価ツールには物理エンジンを用いた高精度なシミュレータもありますが、ユーザー定義のマップや新しいプランナの統合に多大な工数を要することや、計算負荷の高いシミュレータに依存するため、扱えるロボット数が100台未満、あるいは10台程度までに制限されるといったスケーラビリティの課題があります。
SMARTは、シミュレータ、実行監視（EM）サーバ、および各ロボットの実行器（エグゼキュータ）の3つの主要モジュールで構成される、C++実装のマルチエージェント経路計画（MAPF）用テストベッドである。シミュレータは、障害物の配置やロボットの速度・加速度制限などの設定に基づき、大規模実験に適したARGoS3と高精度なIsaac Simの2種類のプラットフォームをサポートしている。EMサーバは、各ロボットの時刻付き位置のシーケンスとして記述された標準的なMAPF計画を解析し、アクション間の依存関係を示す有向非巡回グラフ（ADG）を構築して実行を管理する。ADGの構築において、従来のMAPF計画に存在するサイクル衝突によるデッドロックを防ぐため、連続する頂点の間に新たな頂点を追加することでグラフを非巡回化する手法を導入している。各エグゼキュータは、RPCを用いてサーバからアクションを受け取り、PID制御器を用いてシミュレータへ制御コマンドを送るが、高速走行を実現するために連続する同種のアクションを一つのアクションに統合して実行する。評価指標として、全ロボットの完了時間の平均、最大完了時間、およびアクションキューのサイズや速度を含むロボットの状態推移が提供される。
SMARTは、マルチエージェント経路計画の解を評価するためのプラットフォームであり、Webインターフェースによる利用とローカル環境への導入という2通りの方法を提供します。Web版はSoftware-as-a-Serviceとして提供され、MovingAI Benchmark形式のマップやシナリオファイルをアップロードし、ロボットの運動学的制約を設定することで、3Dビジュアライザを用いたシミュレーションを実行できます。ユーザーはシミュレーションの再生速度や時間ステップを制御できるほか、特定のロボットを選択してその経路や実行状態、ロボット間のType-2エッジを確認することが可能です。また、高度なカスタマイズが必要な場合はローカルでのコンパイルも可能であり、ヘッドレスモードでの実行や独自のパイプラインへの統合、実機ロボットとの連携といった用途に対応しています。
本研究では、提案するテストベッドSMARTの性能を、高性能サーバーと低スペックなノートPCの2種類の計算機を用いて評価している。評価にはARGoS3とIsaac Simの2種類のシミュレータを使用し、MovingAIベンチマークやロボット競技会のマップを用いて、MAPF-LNS2、CBS、PBSといった多様なプランナーや、回転や運動力学を考慮した複数のロボットモデルとの互換性を検証した結果、すべての設定で実行成功率100%を達成した。ARGoS3を用いた実験では、最大2,000台のロボットをサポートし、大規模な倉庫環境でも実時間より約10倍速いシミュレーション速度を維持できる高いスケーラビリティと、ロボット数が増えても実行時間の変動が極めて小さい高い再現性を確認した。一方で、フォトリアルな描写が可能なIsaac Simは、複雑な要因をモデル化できる反面、計算リソースの消費が激しく、シミュレーション速度が実時間を下回るため、少数のロボットを用いた実験に適している。また、実機を用いた7台のJetBotによる検証では、無線通信や物理的な制約がある環境下でも、10回の試行すべてにおいて計画を完遂し、実世界への適用可能性が示された。
本研究では、現実的な設定下でマルチエージェント経路計画（MAPF）のプランナーを評価するための、スケーラブルなテストベッドであるSMARTを提案している。SMARTは既存の2次元グリッドベースのベンチマークと互換性があり、簡略化されたモデルと実世界への展開との乖離を埋める設計となっている。ARGoS3およびIsaac Simの2つのシミュレータと統合されており、ARGoS3を使用することで、高いシミュレーション速度を維持しながら数千台規模のロボットを扱うことが可能である。モジュール式でプランナーに依存しない設計により、学術的なアルゴリズム比較から、倉庫や製造現場といった産業界の具体的なユースケースまで幅広く対応できる。今後の展望として、タスクが継続的に発生する生涯MAPFへの拡張、人間との協調を想定した高度な動的障害物モデルの統合、および代替的な実行フレームワークのサポートが挙げられている。