GJK++: Leveraging Acceleration Methods for Faster Collision Detection
- 8 April 2024
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Robotics
- Vol. 40 (15523098) , 2564-2581
Abstract
Collision detection is a fundamental problem in various domains, such as robotics, computational physics, and computer graphics. In general, collision detection is tackled as a computational geometry problem, with the so-called Gilbert, Johnson, and Keerthi (GJK) algorithm being the most adopted solution nowadays. While introduced in 1988, GJK remains the most effective solution to compute the distance or the collision between two 3-D convex geometries. Over the years, it was shown to be efficient, scalable, and generic, operating on a broad class of convex shapes, ranging from simple primitives (sphere, ellipsoid, box, cone, capsule, etc.) to complex meshes involving thousands of vertices. In this article, we introduce several contributions to accelerate collision detection and distance computation between convex geometries by leveraging the fact that these two problems are fundamentally optimization problems. Notably, we establish that the GJK algorithm is a specific subcase of the well-established Frank–Wolfe (FW) algorithm in convex optimization. By adapting recent works linking Polyak and Nesterov accelerations to FW methods, we also propose two accelerated extensions of the classic GJK algorithm. Through an extensive benchmark over millions of collision pairs involving objects of daily life, we show that these two accelerated GJK extensions significantly reduce the overall computational burden of collision detection, leading to computation times that are up to two times faster. Finally, we hope this work will significantly reduce the computational cost of modern robotic simulators, allowing the speedup of modern robotic applications that heavily rely on simulation, such as reinforcement learning or trajectory optimization.Keywords
All Related Versions
Funding Information
- European Regional Development
- ImPACT (CZ.02.1.01/0.0/0.0/15 003/0000468)
- French Government
- Investissements d'avenir (ANR-19-P3IA-0001)
- INEXACT (ANR-22-CE33-0007-01)
- AGIMUS project
- European Commission (101070165)
- ERC (101097822)
- European Union or the European Commission
This publication has 44 references indexed in Scilit:
- OSQP: an operator splitting solver for quadratic programsMathematical Programming Computation, 2020
- Smoothing algorithms for computing the projection onto a Minkowski sum of convex setsComputational Optimization and Applications, 2019
- On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programmingMathematical Programming, 2005
- Numerical Optimization1999
- Some comments on Wolfe's ‘away step’Mathematical Programming, 1986
- A numerically stable dual method for solving strictly convex quadratic programsMathematical Programming, 1983
- Finding the nearest point in A polytopeMathematical Programming, 1976
- An extension of the frank and Wolfe method of feasible directionsMathematical Programming, 1974
- An algorithm for quadratic programmingNaval Research Logistics Quarterly, 1956
- Über den Variabilitätsbereich der Koeffizienten von Potenzreihen, die gegebene Werte nicht annehmenMathematische Annalen, 1907