Robotics: Science and Systems XVIII

Collision Detection Accelerated: An Optimization Perspective

Louis Montaut, Quentin Le Lidec, Vladimír Petrík, Josef Sivic, Justin Carpentier

Abstract:

Collision detection between two convex shapes is an essential feature of any physics engine or robot motion planner. It has been often tackled as a computational geometry problem, with the Gilbert, Johnson and Keerthi (GJK) algorithm being the most common approach today. In this work we show 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.

Download:

Bibtex:

  
@INPROCEEDINGS{Montaut-RSS-22, 
    AUTHOR    = {Louis Montaut AND {Quentin Le} Lidec AND Vladimír Petrík AND Josef Sivic AND Justin Carpentier}, 
    TITLE     = {{Collision Detection Accelerated: An Optimization Perspective}}, 
    BOOKTITLE = {Proceedings of Robotics: Science and Systems}, 
    YEAR      = {2022}, 
    ADDRESS   = {New York City, NY, USA}, 
    MONTH     = {June}, 
    DOI       = {10.15607/RSS.2022.XVIII.039} 
}