Path planning [1–3] creates or plans a path for a mobile robot to efficiently move from a starting point to a destination point in Euclidean space, avoiding obstacles, with optimality, clearance, and completeness. Optimality implies always ensuring the planning of a path with the optimal path length. Clearance indicates how low the probability of collision between obstacles and the mobile robot is. Completeness indicates whether a path can always be planned in the presence of a solution (that is, whether a path can be created from the starting point to the destination point without colliding with obstacles).

This paper proposed a treatment method for a sampling-based rapidly exploring random tree (RRT) algorithm [4] that does not guarantee optimality. The RRT algorithm can be summarized as a method of planning a path by repeating the act of inserting a randomly sampled position as a child node in a tree with the starting point as the root node until the destination point is reached. With this algorithm, the tree extends in the shape of a stochastic fractal and has a process of determining the destination point.

The sampling-based algorithms [5–10], including the RRT algorithm, have the advantage of being able to plan a path in less time with less computation than the classical path planning algorithms, such as visibility graph-based [11], cell decomposition-based [12], and potential field-based [13] algorithms. However, they do not guarantee optimality, and have the disadvantage that completeness is guaranteed probabilistically. The latter is also called probabilistic completeness [14], which implies that completeness is guaranteed when the number of random samples is infinite, but may not be guaranteed when the number of random samples is finite. The purpose of this study is to analyze the path planning of the RRT algorithm, which guarantees completeness and shows performance closer to optimality than related works.

The proposed “post triangular rewiring” method is effective in path planning algorithms that do not guarantee optimality, such as the RRT algorithm, and show locally piecewise linear shape and can be applied as a post-processing method after a path is planned using such an algorithm.

Indeed, because the proposed method has the greatest advantage of the sampling-based path planning algorithm, that is, the fast planning speed owing to the small amount of computation compared to the classical path planning algorithms [5], the amount of computation added by the proposed method should not be large compared to that of the RRT algorithm.

The performance of the proposed method was verified through mathematical modeling. The planning time and path length of the first complete path (the path that first reaches a destination point from a starting point) were compared and analyzed through simulation when the method proposed in various environments was applied to the RRT algorithm and related works and when the method was not applied.

The RRT algorithm is a representative algorithm of the sampling-based path planning algorithm proposed by LaValle in 1998 [4]. It is useful for planning a path considering the conditions of non-holonomic constraints and is designed to have high degrees of freedom.

When a random sample is generated in the configuration space, as shown in Figure 1, the nearest node to the position of the random sample is determined among the nodes constituting the tree with the starting point as the root node. A new node is created at a position away from the node by a step length in the direction of the random sample position and inserted into the tree. If the random sample position is closer than the step length, a new node is created at the random sample position and inserted into the tree. This tree extension process is repeated until the destination point is reached.

The proposed “post triangular rewiring” method can be applied to path planning algorithms that do not guarantee optimality, such as RRT, and rewired based on the triangular inequality principle [6].

It is a post-processing method that is applied after a path is planned using such an algorithm. As shown in Figure 2(a), when there is no obstacle between the current focusing node and its grandparent node (collision-free), a shorter path can be created based on the triangular inequality, as shown in Figure 2(b). The focusing node and the grandparent node of the node are connected as a parent node and rewired, such as deleting the parent node. Therefore, when the proposed post triangular rewiring method is applied, it is possible to modify the path closer to the optimum than the original path of the RRT algorithm.

Figures 3(a) and 3(b) illustrate an example of rewiring [6], which can be expressed as Eq. (1).

Here, ξ() represents a function that receives the node as a variable and returns the parent node of that node. The n-squared (n ≥ 0) of the ξ() function can be expressed as ξn(qi)=(ξ∘ξ∘⋯∘ξ︷ )n (qi), and if n is 0, ξ⁰ (q_i) = q_i holds. That is, m_F (q_i, k) (k > 0) becomes the midpoint between m_F (q_i, k − 1) and ξ(q_i). At this time, d is (d_k − 1)/2.

In addition, by substituting into the triangular inequality in (1), it can be expressed as shown in Figure 3(c) and Equation (2).

Equation (3) provides the distance relation between ancestor nodes based on q_child.

Equation (3) is the distance D() expressed in (1) between the n-th ancestor nodes based on q_child in (2), which represents the distance between each node as a triangular inequality, and then substituted. Here, D() represents the distance between two points, that is, Equations (1)–(3) locally show that the path becomes shorter when rewired.

Algorithms 1 and 2 present the pseudocode of the proposed post triangular rewiring method.

The input value of the post triangular rewiring method includes path R planned using the path planning algorithm, such as the RRT algorithm, obstacle area information C, and threshold value ɛ of the minimum clearance.

f_modify is a variable that determines whether input path R has been modified by this method, and if the path is modified even once, the entire process is repeated. If path modification does not occur in the repeated process, the algorithm is terminated. t refers to the index of the waypoint of R, which is currently the focus. If t is 0, it indicates the starting point, which is the first point of R.

In R, when the first focusing point is q_child, its next point is q_parent, whose next point is q_ancestor, it is determined whether the distance between q_child and q_ancestor is free from obstacle collision (isT rapped() function). If it is free from collisions, it calls rewire(). rewire() connects q_child and q_ancestor, and the q_parent between them is deleted from the path. If R and t are updated owing to rewire(), update q_child (the t-th waypoint of R), q_parent, and q_ancestor accordingly. If q_parent is the last point in R, then check f_modify. Otherwise, repeat the above process again for the updated q_child and q_ancestor.

Here, path modification by rewire() deletes the waypoints and creates a path closer to the optimal path. The input value of rewire() of the post triangular rewiring method includes path R, focusing point index t, and path modification f_modify. Rewiring is performed on the t-th waypoint q_child of R, next point q_parent, and next point q_ancestor of that point. First, the path between q_child and q_parent and the path between q_parent and q_ancestor are deleted. Then, the path between q_child and q_ancestor is inserted. Finally, f_modify returns “true” because the path has been modified.

Figure 4 presents the overall flow chart of the proposed post triangular rewiring method. Here, ξ^t(q_goal) denotes the t-th next waypoint from the starting point q_goal of path R, and ξ^t+n(q_goal) denotes the n-th next waypoint in ξ^t(q_goal). That is, there are n waypoints between ξ^t(q_goal) and ξ^t+n(q_goal).

To verify the performance of the proposed post triangular rewiring method, the path between an RRT in various environments through simulation and the RRT algorithm to which the proposed method is applied, path planning results were compared.

The compared performance measures were the average of all trials when each algorithm was repeated 100 times (the sampling position was changed for each trial), path length (pixel), and planning time (ms) of the first complete path (from the starting point to the destination point until the first path is planned).

Figure 8 depicts the four environmental maps used in the experiment. Here, the green circle (S) indicates the starting point, and the purple circle (G) indicates the destination point. A black polygon with a yellow border (blue in the experimental results) represents an obstacle. The size of all environmental maps was 600 × 600 pixels, and the step length was 30 pixels.

In the related works of the path planning algorithm, various environmental maps were considered and utilized to confirm the performance of the proposed method. It is important to determine the environmental map to use because the efficiency of the performance measures expected during the experiment is slightly different depending on the composition, such as the number, arrangement, or shape of obstacles. In this study, the four environmental maps shown in Figures 5–8 were used to verify the performance of the proposed method. These maps are a part of the experimental environment proposed by Han and Seo [15] in 2017, and the efficiency of the following characteristics and performance measures is expected for each map.

Map 1 of Figure 5 appears to be an environment that is efficient to verify optimality and completeness, and it is an environment unfavorable to sampling-based path planning algorithms such as the RRT algorithm. Because the probability of determining a solution is low, several samplings are required. Map 2 of Figure 6 is an environment that is efficient to verify the optimality and completeness of the path planning algorithm. Map 3 of Figure 7 is an environment that is efficient to verify the optimality of the path planning algorithm and the planning time because it comprises obstacles (50 squares) that are close to curved. The expensive classical path planning algorithm is unfavorable. Map 4 of Figure 8 is an environment that is efficient to verify the completeness and planning time of the path planning algorithm, and is an environment unfavorable to sampling-based path planning algorithms such as the RRT algorithm. Because the sampling-based path planning algorithm depends on probabilistic completeness, the number of samples and planning time required becomes extremely large and long, respectively, as there are narrow or few entrances in the direction to the destination point.

Table 1 lists the performance of the computer used in the simulation. The simulator used for the simulation [6] was developed based on C# WPF (Microsoft Visual Studio Community 2019 Version 16.1.6 Microsoft .NET Framework Version 4.8.03752), and only a single thread was used for the calculations, except for the visual part. Indeed, there might be differences in the planning time during simulation depending on the computer performance. Therefore, in this study, the planning time was not compared absolutely, but relatively, based on the RRT algorithm.

The experimental results (path length and planning time) were analyzed when the “post triangular rewiring” method was applied to the RRT algorithm, and its path planning results in the four environmental maps were presented in the experimental environment.

In each map, a figure of the path planning (in the case of a single trial) result for each algorithm is shown, and the results of the experiment (when it is repeated) on the performance measures are presented as numerical values in each table (the figure for each algorithm is not the result of repeated trials). As for the repeated trials, there might be a large difference between the performance observed visually and the numerical results shown in the table. The figure illustrated the shape of the planned path for each algorithm. In addition, it was determined whether there was a section in which the piecewise linear shape path was smoothed by the proposed “post triangular rewiring” method.

Figure 5 shows the path planning results for Map 1 among the presented environmental maps for each algorithm. Visually, the path of the “post triangular rewiring” method appears to be the shortest.

Table 2 presents the path planning results for Map 1 (average when repeated 100 times) among the presented environmental maps for each algorithm. The path length after applying the post triangular rewiring method was 72% (1403/1932) compared to that of the RRT, which was the shortest, and the planning time was similar.

Figure 6 shows the path planning results for Map 2 among the presented environmental maps for each algorithm. Visually, the path of the “post triangular rewiring” method appears to be the shortest.

Table 3 presents the path planning results for Map 2 (average when repeated 100 times) among the presented environmental maps for each algorithm. The path length after applying the post triangular rewiring method was 82% (799/969) compared to that of the RRT, which was the shortest, and the planning time was similar.

Figure 7 depicts the path planning results for Map 3 among the presented environmental maps for each algorithm. Visually, the path of the “post triangular rewiring” method appears to be the shortest.

Table 4 presents the path planning results for Map 3 (average when repeated 100 times) among the presented environmental maps for each algorithm. The path length after applying the post triangular rewiring method was 89% (529/591) compared to that of the RRT, which was the shortest, and the planning time was similar.

Figure 8 depicts the path planning results for Map 4 among the presented environmental maps for each algorithm. Visually, the path of the “post triangular rewiring” method appeared to be the shortest.

Table 5 presents the path planning results for Map 4 (average when repeated 100 times) among the presented environmental maps for each algorithm. The path length after applying the post triangular rewiring method was 85% (1304/1533) compared to that of the RRT, which was the shortest, and the planning time was similar.

Overall, the application of the “post triangular rewiring” method exhibited a good performance in the path length for all maps, indicating that the proposed method is effective in terms of optimality.

In this paper, we proposed a “post triangular rewiring” method that could minimize the sacrifice of planning time and overcome the limitations of the optimization of the sampling derivation algorithm. The proposed “post triangular rewiring” method creates a more optimal path. In addition, as a post-processing method, it has the advantage of being applicable to all path planning algorithms that plan a locally piecewise linear path. Simulations were performed to verify the performance of the RRT algorithm, to which the post triangular rewiring method was applied. It was verified that the path length was shortened by 11–28% (average 18%) when applied to the RRT algorithm in the four different environmental maps. Consequently, the RRT algorithm applying the proposed “post triangular rewiring” method exhibited a more optimal path.

Table 1. Computer performance for simulation.

Table 2. Experimental results of Map 1.

Table 3. Experimental results of Map 2.

Table 4. Experimental results of Map 3.

Table 5. Experimental results of Map 4.

Algorithm 1. Pseudocode of the proposed “post triangular rewiring” method.

Algorithm 2. Pseudocode of the “rewire” function from the proposed method.