用格理论设计确定性采样，让机器人规划更快更可靠。
Effective Sampling for Robot Motion Planning Through the Lens of Lattices
- 基于Ad*格构造确定性采样点，避免随机性
- 在复杂任务中比传统方法快10倍以上
- 适合对实时性和可靠性要求高的机器人应用
基于采样的运动规划方法通过随机采样捕捉机器人自由空间结构，因可扩展、简单且具备概率完备性和渐近最优性而广受欢迎。然而，这些保证在有限样本（即有限运行时间）下的实际意义有限。本文利用格理论与Tsao等人（2020）提出的(δ,ε)-完备性概念，构建具有强有限时间保证的确定性采样集，显著降低运行时间。特别地，我们提出一种基于Ad*格的高效确定性采样方法，该格在维度≤21时为最佳几何覆盖。实验表明，该方法在复杂运动规划任务中相较现有确定性和均匀随机采样方法至少提升一个数量级的效率。本工作在提供深层数学洞察的同时，推动了基于采样的运动规划的实际应用。
原文摘要 · Abstract (English)
Sampling-based methods for motion planning, which capture the structure of the robot's free space via (typically random) sampling, have gained popularity due to their scalability, simplicity, and for offering global guarantees, such as probabilistic completeness and asymptotic optimality. Unfortunately, the practicality of those guarantees remains limited as they do not provide insights into the behavior of motion planners for a finite number of samples (i.e., a finite running time). In this work, we harness lattice theory and the concept of $(δ,ε)$-completeness by Tsao et al. (2020) to construct deterministic sample sets that endow their planners with strong finite-time guarantees while minimizing running time. In particular, we introduce a highly-efficient deterministic sampling approach based on the $A_d^*$ lattice, which is the best-known geometric covering in dimensions $\leq 21$. Using our new sampling approach, we obtain at least an order-of-magnitude speedup over existing deterministic and uniform random sampling methods for complex motion-planning problems. Overall, our work provides deep mathematical insights while advancing the practical applicability of sampling-based motion planning.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。