A Homotopy Invariant Based on Convex Dissection Topology and a Distance Optimal Path Planning Algorithm
Jinyuan Liu, Minglei Fu, Andong Liu, Wen-an Zhang, Bo Chen
Abstract
The concept of path homotopy has received widely attention in the field of path planning in recent years. In this letter, 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.
BibTeX
@inproceedings{ral2023_ahomotopyinvaria,
title = {A Homotopy Invariant Based on Convex Dissection Topology and a Distance Optimal Path Planning Algorithm},
author = {Jinyuan Liu and Minglei Fu and Andong Liu and Wen-an Zhang and Bo Chen},
booktitle = {RA-L 2023},
year = {2023}
}