论文标题
碰撞检测加速：优化视角
Collision Detection Accelerated: An Optimization Perspective
论文作者
论文摘要
两个凸形之间的碰撞检测是任何物理引擎或机器人运动计划器的重要特征。它通常被作为计算几何问题解决，吉尔伯特，约翰逊和基尔西（GJK）算法是当今最常见的方法。在这项工作中，我们利用了碰撞检测从根本上是凸优化问题的事实。特别是，我们确定GJK算法是凸优化中建立的弗兰克 - 沃尔夫（FW）算法的特定子案例。我们通过调整连接Nesterov加速和Frank-Wolfe方法的最新作品来引入一种新的碰撞检测算法。我们基准在两个由严格凸面和非刻板凸形组成的数据集上基于提出的加速碰撞检测方法。我们的结果表明，与最先进的GJK算法相比，我们的方法大大减少了解决碰撞检测问题的迭代次数，从而导致计算时间更快两倍。
Collision detection between two convex shapes is an essential feature of any physics engine or robot motion planner. It has often been tackled as a computational geometry problem, with the Gilbert, Johnson and Keerthi (GJK) algorithm being the most common approach today. In this work we leverage the fact that collision detection is fundamentally a convex optimization problem. In particular, we establish that the GJK algorithm is a specific sub-case of the well-established Frank-Wolfe (FW) algorithm in convex optimization. We introduce a new collision detection algorithm by adapting recent works linking Nesterov acceleration and Frank-Wolfe methods. We benchmark the proposed accelerated collision detection method on two datasets composed of strictly convex and non-strictly convex shapes. Our results show that our approach significantly reduces the number of iterations to solve collision detection problems compared to the state-of-the-art GJK algorithm, leading to up to two times faster computation times.
