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/

Global: Zendy Plus annual

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

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

An efficient algorithm to solve the $k$ shortest non-homotopic path planning($k$-SNPP) problem in a 2D environment is proposed in this paper. Motivated byaccelerating the inefficient exploration of the homotopy-augmented space of the2D environment, our fundamental idea is to identify the non-$k$-optimal pathtopologies as early as possible and terminate the pathfinding along them. Thisis a non-trivial practice because it has to be done at an intermediate state ofthe path planning process when locally shortest paths have not been fullyconstructed. In other words, the paths to be compared have not rendezvoused atthe goal location, which makes the homotopy theory, modelling the spatialrelationship among the paths having the same endpoint, not applicable.  This paper is the first work that develops a systematic distance-basedtopology simplification mechanism to solve the $k$-SNPP task, whose corecontribution is to assert the distance-based order of non-homotopic locallyshortest paths before constructing them. If the order can be predicted, thenthose path topologies having more than $k$ better topologies are proven free ofthe desired $k$ paths and thus can be safely discarded during the path planningprocess. To this end, a hierarchical topological tree is proposed as animplementation of the mechanism, whose nodes are proven to expand innon-homotopic directions and edges (collision-free path segments) are provenlocally shortest. With efficient criteria that observe the order relationsbetween partly constructed locally shortest paths being imparted into the tree,the tree nodes that expand in non-$k$-optimal topologies will not be expanded.As a result, the computational time for solving the $k$-SNPP problem is reducedby near two orders of magnitude.

Efficient Search of the k Shortest Non-Homotopic Paths by Eliminating Non-k-Optimal Topologies