Abstract: An efficient path planning algorithm, Adaptive Topological Informed Rapidly exploring Random Tree*(ATIRRT*), applying topology is proposed in this paper to address the low efficiency of the sampling-based path planning algorithm and the random nature of sampling.First, to reduce the time and cost of finding the initial path, topological nodes are introduced to replace the feature points obtained by the Harris corner detection algorithm in STIRRT* algorithm for sampling. Specifically, an adaptive threshold selection method is introduced to eliminate redundant feature points extracted on the path skeleton.The topological nodes obtained from this threshold can make the expansion of the random tree more directional, thereby reducing the time and cost of searching for the initial path.Second, the connection mode of a non-single parent node is proposed, which strengthens the connection between topological principle of nodes on intersecting branches.Third, the number of nodes between adjacent topological nodes is increased by the node expansion strategy to speed up the convergence of the optimization algorithm.Finally, the related constraints are defined to segment and optimize the initial path step by step, which further improves the efficiency of the optimization algorithm.The simulation results reveal that the improved algorithm can significantly improve the efficiency of path planning and the length of the planned path.Compared with STIRRT* algorithm, the length of the planned path in the three types of simulation maps was reduced by 8% on average, while the planning time was reduced by 10% on average, which can quickly find a better initial path and reduce the useless exploration space in the optimization process, thereby improving the search efficiency.
global path planning,
Rapidly-exploring Random Tree(RRT),
corner detection algorithm,
node expansion strategy,