FF-RRT*: a sampling-improved path planning algorithm for mobile robots against concave cavity obstacle

Due to the advantage of convenience and the universality of application, there is an increasing interest in mobile robots. Path planning is one of the prime concerns to be explored in mobile robots. Generally speaking, path planning is to generate a feasible and optimal path between the source and destination in a preset environment with several performance indicators, such as distance cost and work time. Nowadays, path planning algorithms have been applied substantially in many fields including, but not limited to, unmanned aerial vehicles [1, 2], additive manufacturing [3, 8] and biology [9]. It is worth noting that the detection algorithm [10] lays the foundation for path planning by identifying the external environment.

Path planning becomes a hot issue and a lot of research is being conducted. Nowadays, there are several commonly used path-planning algorithms: artificial potential field methods [11], geometric algorithms [12], grid-based searches [13], sampling-based algorithms [14, 15], and learning-based algorithms [16, 17]. Although the learning-based algorithm shows superior performance in path planning, its reliability of it needs to be further verified theoretically. Benefiting from the excellent performance, increasing attention has been focused on the sample-based algorithm in the current study. Rapidly exploring Random Trees (RRT) is a typical representation of sample-based algorithm. Compared to other algorithms, RRT can find a feasible solution without complicated computation. However, the path created by RRT is not optimal. To solve this problem, the RRT* is proposed [18]. It mainly introduces two procedures, ChooseParent and Rewire procedure, into RRT to increase the number of samples and generate an optimal path. However, the increased number of samples leads to its slow convergence. It cannot generate the optimal path during the limited time. In addition, the optimization effect is not satisfactory. To solve the problem, researchers have proposed many RRT*-variants in recent years.

Introducing a sampling strategy is one of the useful ways. On the one hand, the sampling strategy can be applied to the initial path of RRT*. RRT*-Smart [19] obtains an optimal path by applying the intelligent sampling method in RRT*. However, the algorithm only adapted to the environment containing obstacles with simple geometries. Informed-RRT* [20] generates an elliptical sampling region according to the start and goal point, which is continuously narrowed with the sampling process, to quickly gain the optimal path. However, once the generated prolate hyper-spheroid is bigger than the planning problem domain, the algorithm has poor performance. On the other hand, the sampling strategy can also be applied to searching the nodes during the path planning process. P-RRT* [21] determines the extension direction by artificial potential fields. Based on it, PQ-RRT* [22] combines it with Quick-RRT* [23] to further shorten the convergence time. Moreover, AFG-RRT* [24] and improved bidirectional RRT∗ [25] are also applied to the artificial field to ensure directional exploration. Wang et al. use a CNN model trained with the successful example to predict the extension direction and guide the generation of nodes [26]. G-RRT* [27] and ED-RRT* [28] shorten the sampling process by goal-oriented sampling. The Fast-RRT* [29] introduces the hybrid sampling strategy to narrow the sampling area and shorten the convergence rate. It is worth noting that the applicability of the hybrid sampling method is poor in the complex environment with concave cavity obstacle. Since these algorithms mainly reduce the convergence rate by improving the quality of sampling, the optimization effect is still not satisfactory.

In addition to the improved sampling strategy, reducing nodes is another effective way. Karaman et al. use the heuristic function to calculate the path cost [30]. The point will be cut off if it cannot decrease the cost. MOD-RRT* [31] expands the tree with a goal point to calculate the cost between nodes and the goal point and cut off the node which brings the additional cost. Except for reducing the tree nodes, reducing path nodes can also improve the convergence rate. In this field, Jeong et al. propose Quick-RRT* [23], which applies triangular inequality to improve the RRT*. Inspired by Quick-RRT*, Kang et al. [32] use the triangular inequality to improve the performance of RRT-Connect [33]. Furthermore, Liao et al. proposed the F-RRT* [34]. By applying the FindReachest procedure with triangular inequality and the CreatNode procedure with dichotomy method, the path cost is greatly reduced. It is worth noting that the parameter D_dichotomy needs to be identified because F-RRT ∗ with a smaller D_dichotomy not only improves the quality of the path but also increases the computation time. It is useful to combine the sampling strategy algorithm with F-RRT* to improve the quality of sampling to compensate for the increasing computation time.

This paper proposes a sampling-improved path planning algorithm, FF-RRT*. FF-RRT* takes advantage of Fast-RRT* and F-RRT* and overcomes the weakness of these two algorithms. The hybrid sampling method is improved to achieve effective sampling and overcome the application limitation of the original hybrid sampling method. The search scopes of the ChooseParent and Rewire procedures are expanded to optimize the path and shorten the convergence time. The CreatNode process creates a new parent node based on the dichotomy method to get an optimal parent node to \(x_{{{\text{rand}}}}\). Compared with F-RRT* and Fast-RRT*, FF-RRT* generates an optimal path with a short convergence time and has superior environment adaptability. The theoretical analysis is provided for the characteristics of FF-RRT*. And the superior performance of FF-RRT* is validated by the comparative simulations with four simulation environments.

This paper is organized as follows: "Problem definition" introduces the path planning problem. "Related work" introduces the related work of FF-RRT*. "FF-RRT*" states the FF-RRT*. "Analysis" presents a theoretical analysis of completeness, optimality, and computational complexity. Four simulation environments are used in "Simulation results" to demonstrate the performance of FF-RRT* compared with F-RRT* and Fast-RRT*. Finally, a summary is given in "Conclusion".

Let \(X \subseteq R^{c}\) be the workspace, where \(c \in N,c \ge 2\). Let \(X_{{{\text{obs}}}} \subset X\) be the obstacle region, and the collision-free region is \(X_{{{\text{free}}}} = X - X_{{{\text{obs}}}}\). \(x_{{\text{s}}}\) and \(x_{{\text{g}}}\) are source and destination. The path is described as a function \(\phi\).

Path planning aims to generate a path \(\phi\) that begins at the initial point \(\phi (0) = x_{{\text{s}}}\) and reaches the destination \(\phi (1) = x_{{\text{g}}}\) and \(\phi (\upsilon ) \in X_{{{\text{free}}}}\) for all \(\upsilon \in [0,1][0,1]\). The \(\phi\) that fulfills the requirement is called a feasible path. Based on the definition above, the path planning problem can be described as generate a feasible path in the workspace \(X\) with the initial conditions \(\{ x_{{\text{s}}} ,X_{{{\text{obs}}}} ,x_{{\text{g}}} \}\). Definitions 1 and 2 present, respectively, the feasibility and optimal path planning problem.

This section mainly introduces the related work of the proposed method. The main improvement of Fast-RRT* [29] and F-RRT* [34] compared to RRT* is introduced subsequently.

This paper proposes the FF-RRT* algorithm, which combines the advantages of Fast-RRT* and F-RRT* and overcomes the weakness of these two algorithms. FF-RRT is shown in Algorithm 8. The improved hybrid sampling method is used to improve the sampling quality to compensate for the large computation time generated by the CreatNode procedure of F-RRT* and remove the applicability limitation of Fast-RRT*.

First, the tree node is sampled by the improved HybridSampling procedure. The improved HybridSampling procedure is outlined in Algorithm 9. Different from the original hybrid sampling outlined in Algorithm 2, the improved hybrid sampling combines the random sampling strategy and the constrained sampling strategy to overcome the application limits of the original hybrid sampling. Second, the search scopes of the ChooseParent and Rewire procedures are expanded to the ancestor of the temporary parent node to accelerate the convergence rate. The improved ChooseParent procedure is the same as Fast-RRT* and F-RRT*. The improved Rewire procedure is shown in Algorithm 10. Thirdly, the CreatNode procedure is adopted to generate an optimal parent node for \(x_{{{\text{rand}}}}\) based on the dichotomy method to generate an optimal path. The FF-RRT* is constructed as shown in Fig. 1. And the comparison between FF-RRT* and related works is illustrated in Table 1.

FF-RRT* is simulated in 2-dimensional map, which contains four test environments. In the simulation, the performance of FF-RRT* is compared with Fast-RRT* and F-RRT, because they are the basement of FF-RRT* and are the latest representations of the variant of RRT*. Every algorithm was repeated 100 times during the simulation to resist randomness.

The simulation will compare the performance of algorithms by three indicators: Cⁱ, which is the cost of the generated path by algorithm i; Nⁱ, which is the number of iterations to generate the path by algorithm i, Tⁱ, which is the time of generating the path by algorithm i. The algorithm will stop once the feasible path is found or the max iteration is reached. The simulation is implemented on an AMD Ryzen 7 5800X CPU with 8G of RAM. The simulation environments are illustrated in Fig. 7. The four simulation environments are the same size 9000 × 6000.

During the simulation process, the parameters that need to be identified are \(R_{{{\text{near}}}}\),\(n_{\max }\), D_dichotomy, \(\lambda\). In the simulation process, \(n_{\max } = 30,000\). In the sampling procedure, \(\lambda = 0.5\). In the improved ChooseParent procedure, \(R_{{{\text{near}}}} = 200\). And in CreatNode procedure, referring to the Reference [34], we did the simulation to choose the value of \(D_{{{\text{dichotomy}}}}\). The relationship between the performance of the F-RRT* in the cluttered environment and \(D_{{{\text{dichotomy}}}}\) is shown in Fig. 8. It can be seen that when the \(D_{{{\text{dichotomy}}}}\) increases, C^F-RRT* increases, while T^F−RRT* decreases simultaneously. To avoid the additional computation time, the value of \(D_{{{\text{dichotomy}}}}\) is set as 300.

A novel sampling-improved path planning algorithm, FF-RRT* is proposed in the paper. By combining and improving the adjustments of F-RRT* and Fast-RRT*, the FF-RRT* can obtain an optimal path with a short convergence time. The major imp of FF-RRT* is to propose the improved HybridSampling procedure and introduce it into the F-RRT* to improve sampling quality and decrease the iterations to increase the convergence rate. Additionally, the improved HybridSampling procedure is applicable to the environment with concave cavity obstacle, which overcomes the application limitation of the original HybridSampling procedure in Fast-RRT*. The superior performance of the FF-RRT* was verified by numerical simulation compared to F-RRT* and Fast-RRT*. The FF-RRT* shortens 32% of the convergence time in complex maze environment and 25% of the convergence time in simple maze environment compared to F-RRT*. And in a complex maze with a concave cavity obstacle, the average convergence time of Fast-RRT* in this environment is 134% more than the complex maze environment compared to 12% with F-RRT* and 34% with FF-RRT*.

Although the FF-RRT* algorithm can effectively decrease the convergence time by improved HybridSampling procedure, the increased computation problem caused by the application of dichotomy has not been fundamentally solved. Additionally, the applicability to three-dimensional environment [35, 36] is also a valuable research direction. Meanwhile, when actually used for certain robots, such as drones, the continuity of the generated paths needs to be guaranteed [37, 38]. Hence, how to decrease the computation time of dichotomy fundamentally and maintain the continuity of the generated path in a three-dimensional environment is our future study direction.