GJK++: Leveraging Acceleration Methods for Faster Collision Detection

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

GJK++: Leveraging Acceleration Methods for Faster Collision Detection

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

GJK++: Leveraging Acceleration Methods for Faster Collision Detection

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

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

Projekt

<a href="/cs/project/EF15_003%2F0000468" target="_blank" >EF15_003/0000468: Inteligentní strojové vnímání</a><br>

Návaznosti

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

Rok uplatnění

2024

Kód důvěrnosti údajů

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

Název periodika

IEEE Transactions on Robotics

ISSN

1552-3098

e-ISSN

1941-0468

Svazek periodika

40

Číslo periodika v rámci svazku

April

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

18

Strana od-do

2564-2581

Kód UT WoS článku

001214506500002

EID výsledku v databázi Scopus

2-s2.0-85190173290