A Homotopy Invariant Based on Convex Dissection Topology and a Distance Optimal Path Planning Algorithm

原文アブストラクト

The concept of path homotopy has received widely attention in the field of path planning in recent years. In this article, a homotopy invariant based on convex dissection for a two-dimensional bounded Euclidean space is developed, which can efficiently encode all homotopy path classes between any two points. Thereafter, the optimal path planning task consists of two steps: (i) search for the homotopy path class that may contain the optimal path, and (ii) obtain the shortest homotopy path in this class. Furthermore, an optimal path planning algorithm called CDT-RRT* (Rapidly-exploring Random Tree Star based on Convex Division Topology) is proposed. We designed an efficient sampling formula for CDT-RRT*, which gives it a tendency to actively explore unknown homotopy classes, and incorporated the principles of the Elastic Band algorithm to obtain the shortest path in each class. Through a series of experiments, it was determined that the performance of the proposed algorithm is comparable with state-of-the-art path planning algorithms. Hence, the application significance of the developed homotopy invariant in the field of path planning was verified.