指数的な探索空間から解を見つける：マルチロボット運動計画のための暗黙的ロードマップ探索に用いる離散RRT
Finding a needle in an exponential haystack: Discrete RRT for exploration of implicit roadmaps in multi-robot motion planning
複数ロボットの運動計画において、各ロボットのロードマップのテンソル積を暗黙的に表現し、グラフ向けに適応した離散RRTで高速に探索する手法を提案。最大60自由度のシナリオで既存手法より10倍以上高速であることを示した。
著者: Kiril Solovey, Oren Salzman, Dan Halperin
分類: cs.RO
原文アブストラクト
We present a sampling-based framework for multi-robot motion planning which combines an implicit representation of a roadmap with a novel approach for pathfinding in geometrically embedded graphs tailored for our setting. Our pathfinding algorithm, discrete-RRT (dRRT), is an adaptation of the celebrated RRT algorithm for the discrete case of a graph, and it enables a rapid exploration of the high-dimensional configuration space by carefully walking through an implicit representation of a tensor product of roadmaps for the individual robots. We demonstrate our approach experimentally on scenarios of up to 60 degrees of freedom where our algorithm is faster by a factor of at least ten when compared to existing algorithms that we are aware of.
関連論文
- 多角形環境におけるマルチロボット運動計画のFPTASマルチロボット運動計画
- ゲーム理論的運動計画における意図通信と仮説尤度マルチロボット運動計画
- 動力学制約付きマルチロボット運動計画のための競合ベース探索マルチロボット運動計画
- 非通信環境下で動作するマルチエージェント強化学習と軌道最適化を組み合わせた移動ロボットのハイブリッド運動計画マルチロボット運動計画
- 有限サンプリングによる準最適マルチロボット運動計画マルチロボット運動計画
- マルチレベル・モース理論によるマルチロボット運動計画の局所極小の可視化マルチロボット運動計画
