English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

The complexity of nearest-neighbor search dominates the asymptotic runningtime of many sampling-based motion-planning algorithms. However, collisiondetection is often considered to be the computational bottleneck in practice.Examining various asymptotically optimal planning algorithms, we characterizesettings, which we call NN-sensitive, in which the practical computational roleof nearest-neighbor search is far from being negligible, i.e., the portion ofrunning time taken up by nearest-neighbor search is comparable, or sometimeseven greater than the portion of time taken up by collision detection. Thisreinforces and substantiates the claim that motion-planning algorithms couldsignificantly benefit from efficient and possibly specifically-tailorednearest-neighbor data structures. The asymptotic (near) optimality of thesealgorithms relies on a prescribed connection radius, defining a ball around aconfiguration $q$, such that $q$ needs to be connected to all otherconfigurations in that ball. To facilitate our study, we show how to adapt thisradius to non-Euclidean spaces, which are prevalent in motion planning. Thistechnical result is of independent interest, as it enables to compare theradial-connection approach with the common alternative, namely, connecting eachconfiguration to its $k$ nearest neighbors ($k$-NN). Indeed, as we demonstrate,there are scenarios where using the radial connection scheme, a solution pathof a specific cost is produced ten-fold (and more) faster than with $k$-NN.

Collision detection or nearest-neighbor search? On the computational bottleneck in sampling-based motion planning