F-RRT*: An improved path planning algorithm with improved initial solution and convergence rate. (1st December 2021)

• Record Type: Journal Article
• Authors: Liao, Bin; Wan, Fangyi; Hua, Yi; Ma, Ruirui; Zhu, Shenrui; Qing, Xinlin
• Is Part Of: Expert systems with applications. Volume 184(2021)
• Publication Date: 2021-12-01
• Subjects: Path planning -- Sampling-based algorithms -- Rapidly-exploring random tree (RRT) -- Optimal path planning; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2021.115457
• Languages: English
• ISSNs: 0957-4174

Abstract

Highlights: A tree-extending algorithm for reducing the solution cost is presented. Generating nodes essential to the optimal path with smaller samples. Searching for ancestors of the nearest vertex instead of nodes around the random point. Connecting the random point to the furthest vertex of the tree it can reach. Abstract: During the last decades, sampling-based algorithms have been used to solve the problem of motion planning. RRT*, as an optimal variant of RRT, provides asymptotic optimality. However, the slow convergence rate and costly initial solution make it inefficient. To overcome these limitations, this paper proposes a modified RRT* algorithm, F-RRT*, which generates a better initial solution and converges faster than RRT*. F-RRT* optimizes the cost of paths by creating a parent node for the random point, instead of selecting it among the existing vertices. The creation process can be divided into two steps, the FindReachest, and CreatNode procedures, which require few calculations, and the triangle inequality is used repeatedly throughout the process, thus, resulting in paths with higher performance than those of RRT*. Since the algorithm proposed in this paper is a tree extending algorithm, its performance can be further enhanced when combined with other sampling strategies. The advantages of the proposed algorithm in the initial solution and fast convergence rate are demonstrated by comparing with RRT*, RRT*-Smart, and Q-RRT* through numerical simulations in this paper.