多角形ロボットのための漸近最適マルチクエリ経路計画
Asymptotically-Optimal Multi-Query Path Planning for a Polygonal Robot
多角形ロボットの並進と回転を同時に扱うため、異なる向きの可視グラフを重ね合わせた回転スタック可視グラフ(RVG)を提案し、解像度完全性と漸近最適性を示した。
著者: Duo Zhang, Zihe Ye, Jingjin Yu
分類: cs.RO
原文アブストラクト
Shortest-path roadmaps, also known as reduced visibility graphs, provides a highly efficient multi-query method for computing optimal paths in two-dimensional environments. Combined with Minkowski sum computations, shortest-path roadmaps can compute optimal paths for a translating robot in 2D. In this study, we explore the intuitive idea of stacking up a set of reduced visibility graphs at different orientations for a polygonal holonomic robot to support the fast computation of near-optimal paths, allowing simultaneous 2D translation and rotation. The resulting algorithm, rotation-stacked visibility graph (RVG), is shown to be resolution-complete and asymptotically optimal. Extensive computational experiments show RVG significantly outperforms state-of-the-art single- and multi-query sampling-based methods on both computation time and solution optimality fronts.
