Collision Detection Accelerated: An Optimization Perspective

Louis Montaut (1, 2) , Quentin Le Lidec (2) , Vladimir Petrik (1) , Josef Sivic (1) , Justin Carpentier (2)

1 CIIRC - Czech Institute of Informatics, Robotics and Cybernetics [Prague]
2 WILLOW - Models of visual object recognition and scene understanding

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.

Domaines: Robotique [cs.RO]; Synthèse d'image et réalité virtuelle [cs.GR]

Louis Montaut, Quentin Le Lidec, Vladimir Petrik, Josef Sivic, Justin Carpentier. Collision Detection Accelerated: An Optimization Perspective. RSS 2022 - Robotics: Science and Systems, Jun 2022, New York, United States. ⟨hal-03662157⟩