Tree-Based Representation of Locally Shortest Paths for 2D K-Shortest Non-Homotopic Path Planning

A novel algorithm to solve the 2D k-shortest non- homotopic path planning (k-SNPP) task is proposed in this paper. The task is of practical significance as a sub-module for higher- level planning and scheduling tasks, and is gaining increasing attention and focus in recent years. There have existed algo- rithms that explicitly characterised non-homotopic paths using topological invariants such as h-signature and winding number. However, these algorithms are inefficient due to their separate treatment of topology and geometry: Topological invariants are singularly utilised for distinguishing non-homotopic property among paths, which significantly increases the volume of the robot configuration space. Meanwhile, distance-optimal path planners search for locally shortest paths in the augmented space, which becomes extremely time-consuming. In this paper, a topological tree is proposed to simultaneously leverage topology and geometry. The tree grows from the starting location and explores all topological routes, until the best kof its leaves reach the goal. It is proven that different branches of the tree explore different homotopy classes of paths, and all the branches are locally shortest. Comparative experiments for k-SNPP are conducted in challenging grid-based simulated environments to validate the performance of the proposed algorithm. The C++ implementation of the proposed algorithm is released for the benefit of the robotics community.