International Journal of Fuzzy Logic and Intelligent Systems 2021; 21(3): 213-221
Published online September 25, 2021
https://doi.org/10.5391/IJFIS.2021.21.3.213
© The Korean Institute of Intelligent Systems
Jin-Gu Kang and Jin-Woo Jung
Department of Computer Science and Engineering, Dongguk University, Seoul, Korea
Correspondence to :
Jin-Woo Jung (jwjung@dongguk.edu)
This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/by-nc/3.0/) which permits unrestricted noncommercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
This paper proposed the “post triangular rewiring” method that minimizes the sacrifice of planning time and overcomes the limit of optimality of sampling-based algorithms such as the rapidly exploring random tree (RRT) algorithm. The proposed “post triangular rewiring” method creates a path closer to the optimal path than the RRT algorithm before application, using the triangular inequality principle. Experiments were conducted to verify the performance of the proposed method. When the proposed method is applied to the RRT algorithm, the optimality efficiency increases compared to the planning time.
Keywords: Robot path planning, RRT, Rewiring, Triangular inequality
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
Here,
In addition, by substituting into the triangular inequality in (
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
In
Here, path modification by
Figure 4 presents the overall flow chart of the proposed post triangular rewiring method. Here,
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
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.
No potential conflict of interest relevant to this article was reported.
Process of the RRT algorithm: In the case of creating new node
Summary of the post triangular rewiring method: (a) When line segment
(a) Part of a tree consisting of node
Table 1. Computer performance for simulation.
H/W | Specification |
---|---|
CPU | Intel Core i7-6700K 4.00 GHz (8 CPUs) |
RAM | 32768 MB (32 GB DDR4) |
Table 2. Experimental results of Map 1.
Performance | RRT | Proposal |
---|---|---|
1932 (100%) | 1403 (72%) | |
687 (100%) | 688 (100%) |
The parentheses on the right of each number (average of repeated 100 times) are relative ratios based on 100% RRT (values less than 1 are counted as 1)..
Table 3. Experimental results of Map 2.
Performance | RRT | Proposal |
---|---|---|
969 (100%) | 799 (82%) | |
10 (100%) | 11 (100%) |
The parentheses on the right of each number (average of repeated 100 times) are relative ratios based on 100% RRT (values less than 1 are counted as 1)..
Table 4. Experimental results of Map 3.
Performance | RRT | Proposal |
---|---|---|
591 (100%) | 529 (89%) | |
6 (100%) | 7 (100%) |
The parentheses on the right of each number (average of repeated 100 times) are relative ratios based on 100% RRT (values less than 1 are counted as 1)..
Table 5. Experimental results of Map 4.
Performance | RRT | Proposal |
---|---|---|
1533 (100%) | 1304 (85%) | |
1526 (100%) | 1527 (100%) |
The parentheses on the right of each number (average of repeated 100 times) are relative ratios based on 100% RRT (values less than 1 are counted as 1)..
Algorithm 1. Pseudocode of the proposed “post triangular rewiring” method.
1 | |
2 | |
3 | |
4 | |
5 | |
6 | |
7 | |
8 | |
9 | |
10 | |
11 | |
12 | |
13 | |
Algorithm 2. Pseudocode of the “rewire” function from the proposed method.
1 | |
2 | |
3 | |
4 | |
5 | |
6 | |
E-mail: kanggu12@dongguk.edu
E-mail: jwjung@dongguk.edu
International Journal of Fuzzy Logic and Intelligent Systems 2021; 21(3): 213-221
Published online September 25, 2021 https://doi.org/10.5391/IJFIS.2021.21.3.213
Copyright © The Korean Institute of Intelligent Systems.
Jin-Gu Kang and Jin-Woo Jung
Department of Computer Science and Engineering, Dongguk University, Seoul, Korea
Correspondence to:Jin-Woo Jung (jwjung@dongguk.edu)
This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/by-nc/3.0/) which permits unrestricted noncommercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
This paper proposed the “post triangular rewiring” method that minimizes the sacrifice of planning time and overcomes the limit of optimality of sampling-based algorithms such as the rapidly exploring random tree (RRT) algorithm. The proposed “post triangular rewiring” method creates a path closer to the optimal path than the RRT algorithm before application, using the triangular inequality principle. Experiments were conducted to verify the performance of the proposed method. When the proposed method is applied to the RRT algorithm, the optimality efficiency increases compared to the planning time.
Keywords: Robot path planning, RRT, Rewiring, Triangular inequality
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
Here,
In addition, by substituting into the triangular inequality in (
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
In
Here, path modification by
Figure 4 presents the overall flow chart of the proposed post triangular rewiring method. Here,
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
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.
Process of the RRT algorithm: In the case of creating new node
Summary of the post triangular rewiring method: (a) When line segment
(a) Part of a tree consisting of node
Flow chart of the proposed post triangular rewiring method.
Experimental results of Map 1: (a) RRT and (b) proposed.
Experimental results of Map 2: (a) RRT and (b) proposed.
Experimental results of Map 3: (a) RRT and (b) proposed.
Experimental results of Map 4: (a) RRT and (b) proposed.
Table 1 . Computer performance for simulation.
H/W | Specification |
---|---|
CPU | Intel Core i7-6700K 4.00 GHz (8 CPUs) |
RAM | 32768 MB (32 GB DDR4) |
Table 2 . Experimental results of Map 1.
Performance | RRT | Proposal |
---|---|---|
1932 (100%) | 1403 (72%) | |
687 (100%) | 688 (100%) |
The parentheses on the right of each number (average of repeated 100 times) are relative ratios based on 100% RRT (values less than 1 are counted as 1)..
Table 3 . Experimental results of Map 2.
Performance | RRT | Proposal |
---|---|---|
969 (100%) | 799 (82%) | |
10 (100%) | 11 (100%) |
The parentheses on the right of each number (average of repeated 100 times) are relative ratios based on 100% RRT (values less than 1 are counted as 1)..
Table 4 . Experimental results of Map 3.
Performance | RRT | Proposal |
---|---|---|
591 (100%) | 529 (89%) | |
6 (100%) | 7 (100%) |
The parentheses on the right of each number (average of repeated 100 times) are relative ratios based on 100% RRT (values less than 1 are counted as 1)..
Table 5 . Experimental results of Map 4.
Performance | RRT | Proposal |
---|---|---|
1533 (100%) | 1304 (85%) | |
1526 (100%) | 1527 (100%) |
The parentheses on the right of each number (average of repeated 100 times) are relative ratios based on 100% RRT (values less than 1 are counted as 1)..
Algorithm 1. Pseudocode of the proposed “post triangular rewiring” method.
1 | |
2 | |
3 | |
4 | |
5 | |
6 | |
7 | |
8 | |
9 | |
10 | |
11 | |
12 | |
13 | |
Algorithm 2. Pseudocode of the “rewire” function from the proposed method.
1 | |
2 | |
3 | |
4 | |
5 | |
6 | |
Kyongsae Oh,Euntai Kim,Young-Wan Cho
Int. J. Fuzzy Log. Intell. Syst. 2007; 7(2): 138-142Process of the RRT algorithm: In the case of creating new node
Summary of the post triangular rewiring method: (a) When line segment
(a) Part of a tree consisting of node
Flow chart of the proposed post triangular rewiring method.
|@|~(^,^)~|@|Experimental results of Map 1: (a) RRT and (b) proposed.
|@|~(^,^)~|@|Experimental results of Map 2: (a) RRT and (b) proposed.
|@|~(^,^)~|@|Experimental results of Map 3: (a) RRT and (b) proposed.
|@|~(^,^)~|@|Experimental results of Map 4: (a) RRT and (b) proposed.