快速计算凸集间生长距离，提升机器人运动规划效率
A Ray Intersection Algorithm for Fast Growth Distance Computation Between Convex Sets
- 将生长距离转为射线相交问题，通过内外多面体逼近求解
- 算法收敛稳定，实测在多种凸集上性能领先现有方法
- 适用于机器人路径规划与刚体仿真，开源可复用
本文提出一种高效算法，用于计算具有可表示支撑函数的紧致凸集间的生长距离。生长距离指两集合绕某中心缩放至相交所需的最小缩放因子，统一衡量集合相交与分离。我们首先将生长距离问题转化为闵可夫斯基差集上的射线相交问题；随后提出一种迭代算法，通过构建闵可夫斯基差集的内、外多面体近似来求解。算法满足原始与对偶可行性及单调收敛性。我们在多个基准测试中验证了该方法，开源实现展现出在各类凸集上的领先性能。最后，展示了其在机器人运动规划与刚体仿真中的应用。
原文摘要 · Abstract (English)
In this paper, we discuss an efficient algorithm for computing the growth distance between two compact convex sets with representable support functions. The growth distance between two sets is the minimum scaling factor such that the sets intersect when scaled about some center points. Unlike the minimum distance between sets, the growth distance provides a unified measure for set intersection and separation. We first reduce the growth distance problem to an equivalent ray intersection problem on the Minkowski difference set. Then, we propose an algorithm to solve the ray intersection problem by iteratively constructing inner and outer polyhedral approximations of the Minkowski difference set. We show that our algorithm satisfies several key properties, such as primal and dual feasibility and monotone convergence. We provide extensive benchmark results for our algorithm and show that our open-source implementation achieves state-of-the-art performance across a wide variety of convex sets. Finally, we demonstrate robotics applications of our algorithm in motion planning and rigid-body simulation.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。