GJK++: Leveraging Acceleration Methods for Faster Collision Detection

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21730%2F24%3A00376350" target="_blank" >RIV/68407700:21730/24:00376350 - isvavai.cz</a>

Result on the web

<a href="https://doi.org/10.1109/TRO.2024.3386370" target="_blank" >https://doi.org/10.1109/TRO.2024.3386370</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1109/TRO.2024.3386370" target="_blank" >10.1109/TRO.2024.3386370</a>

Result language

angličtina

Original language name

GJK++: Leveraging Acceleration Methods for Faster Collision Detection

Original language description

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.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

<a href="/en/project/EF15_003%2F0000468" target="_blank" >EF15_003/0000468: Intelligent Machine Perception</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2024

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

IEEE Transactions on Robotics

ISSN

1552-3098

e-ISSN

1941-0468

Volume of the periodical

40

Issue of the periodical within the volume

April

Country of publishing house

US - UNITED STATES

Number of pages

18

Pages from-to

2564-2581

UT code for WoS article

001214506500002

EID of the result in the Scopus database

2-s2.0-85190173290