通过随机重启提升运动规划算法速度，显著缩短计算时间。
Faster Motion Planning via Restarts
- 引入新型随机重启策略加速拉斯维加斯类运动规划算法
- 实测平均提速3倍以上，路径更短且多线程收益更大
- 开源实现易部署，适合机器人路径规划研究者使用
随机化方法如PRM和RRT在运动规划中广泛应用，但在某些情况下运行时间存在固有不稳定性，导致简单实例也出现“灾难性”性能表现。本文应用多种随机重启技术（部分为新提出）来加速拉斯维加斯算法，在实践中取得显著提速效果（多数情况提升3倍或更多）。实验表明，新算法不仅运行时间更短、生成路径更优，且相比直接并行实现，多线程加速效果更明显。我们证明了新变体的最优性。代码已开源，托管于GitHub，易于部署与使用。
原文摘要 · Abstract (English)
Randomized methods such as PRM and RRT are widely used in motion planning. However, in some cases, their running-time suffers from inherent instability, leading to ``catastrophic'' performance even for relatively simple instances. We apply stochastic restart techniques, some of them new, for speeding up Las Vegas algorithms, that provide dramatic speedups in practice (a factor of $3$ [or larger] in many cases). Our experiments demonstrate that the new algorithms have faster runtimes, shorter paths, and greater gains from multi-threading (when compared with straightforward parallel implementation). We prove the optimality of the new variants. Our implementation is open source, available on github, and is easy to deploy and use.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。