Collision Detection Accelerated: An Optimization Perspective

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21730%2F22%3A00362937" target="_blank" >RIV/68407700:21730/22:00362937 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.15607/RSS.2022.XVIII.039" target="_blank" >https://doi.org/10.15607/RSS.2022.XVIII.039</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.15607/RSS.2022.XVIII.039" target="_blank" >10.15607/RSS.2022.XVIII.039</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Collision Detection Accelerated: An Optimization Perspective

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Collision Detection Accelerated: An Optimization Perspective

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

20204 - Robotics and automatic control

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í

2022

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 statě ve sborníku

ROBOTICS: SCIENCE AND SYSTEM XVIII

ISBN

978-0-9923747-8-5

ISSN

2330-7668

e-ISSN

2330-765X

Počet stran výsledku

14

Strana od-do

—

Název nakladatele

Robotics Science and Systems

Místo vydání

—

Místo konání akce

New York

Datum konání akce

27. 6. 2022

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000827625700039