构建旋转堆叠的可视图，实现多查询下移动机器人的高效最优路径规划。
Asymptotically-Optimal Multi-Query Path Planning for a Polygonal Robot
- 通过堆叠不同朝向的简化可视图，支持机器人2D平移与旋转同时进行
- 算法在计算时间和解的最优性上均显著优于现有采样方法
- 适用于需要快速多路径规划的移动机器人场景
最短路径路网（又称缩减可见图）是一种高效的二维环境多查询最优路径计算方法。结合闵可夫斯基和运算，最短路径路网可实现二维环境下平动机器人的最优路径计算。本文探索将一组缩减可见图在不同方向上堆叠，用于支持多边形全向机器人在二维空间中同时实现平移与旋转的近似最优路径快速计算。所提出的旋转堆叠可见图（RVG）算法被证明具有分辨率完备性和渐近最优性。大量实验表明，与当前最先进的单/多查询采样方法相比，RVG在计算时间与解的最优性表现上均有显著提升。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。