db-LaCAM: 不連続性を境界づけた探索と軽量MAPFによる高速かつ大規模マルチロボット動力学運動計画

Abstract

最先端のマルチロボット動力学的（kinodynamic）運動計画プランナは、高い計算負荷により、数台以上のロボットを扱うのが難しいという課題があります。その結果、スケーラビリティが制限され、計画時間が遅くなります。本研究では、現代のマルチエージェント経路探索（MAPF）アルゴリズムのスケーラビリティと高速性に、動力学的プランナの動的な状況認識（dynamic-awareness）を組み合わせ、これらの制限に対処します。具体的には、ロボットの動力学を尊重するように事前計算された一連の運動プリミティブを利用し、生成したホライズン長の運動シーケンスに対して、連続する運動間にユーザが定義した不連続性を許容するプランナ Discontinuity-Bounded LaCAM（db-LaCAM）を提案します。プランナ db-LaCAM は運動プリミティブに関して解像度完全（resolution-complete）であり、任意のロボット動力学をサポートします。大規模な実験により、db-LaCAM は最大50台のロボットを含むシナリオに対して効率よくスケールし、従来の最先端プランナと比較して最大10倍の高速な実行時間を達成しつつ、解の品質は同等に維持されることを示します。このアプローチは、2Dおよび3Dの両環境で、ユニサイクルや3D二重積分器のような動力学により検証されます。さらに、db-LaCAM で計画した軌道の安全な実行を、飛行ロボットのチームと、車両＋トレーラロボットからなる2つの異なる物理実験において実証します。