Article Search
닫기

Original Article

Split Viewer

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

Post Triangular Rewiring Method for Shorter RRT Robot Path Planning

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)

Received: July 2, 2021; Revised: July 2, 2021; Accepted: September 9, 2021

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 [13] 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 [510], 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).

qancestor=ξ(qparent)=ξ2(qchild).

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, ξ0 (qi) = qi holds. That is, mF (qi, k) (k > 0) becomes the midpoint between mF (qi, k − 1) and ξ(qi). At this time, d is (dk − 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 qchild.

D(qchild,ξ(qchild))+D(ξ(qchild),ξ2(qchild))D(qchild,ξ2(qchild)).

Equation (3) is the distance D() expressed in (1) between the n-th ancestor nodes based on qchild 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.

fmodify 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 qchild, its next point is qparent, whose next point is qancestor, it is determined whether the distance between qchild and qancestor is free from obstacle collision (isT rapped() function). If it is free from collisions, it calls rewire(). rewire() connects qchild and qancestor, and the qparent between them is deleted from the path. If R and t are updated owing to rewire(), update qchild (the t-th waypoint of R), qparent, and qancestor accordingly. If qparent is the last point in R, then check fmodify. Otherwise, repeat the above process again for the updated qchild and qancestor.

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 fmodify. Rewiring is performed on the t-th waypoint qchild of R, next point qparent, and next point qancestor of that point. First, the path between qchild and qparent and the path between qparent and qancestor are deleted. Then, the path between qchild and qancestor is inserted. Finally, fmodify returns “true” because the path has been modified.

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

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 58 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.

Fig. 1.

Process of the RRT algorithm: In the case of creating new node qnew at a position separated by step length λ in the direction of the random sample position(qrand) based on the qnear node (position) nearest to the random sample position (qrand) in tree T with starting point qstart as the root node.


Fig. 2.

Summary of the post triangular rewiring method: (a) When line segment γ with node q0 and its grandparent node q2 in tree R is free from obstacle collision (Distance: γ < α+ β), (b) Grandparent node q2 of node q0 is connected as the parent node of node q0, and parent node q1 is deleted from the tree.


Fig. 3.

(a) Part of a tree consisting of node qchild, its parent node qparent, and node qancestor, the parent node of qparent. (b) If there is no obstacle between qchild and qancestor, delete the edge connecting to qparent in each node. (c) Edge α connecting qchild and qparent, edge β connecting qparent and qancestor, and edge γ connecting qchild and qancestor.


Fig. 4.

Flow chart of the proposed post triangular rewiring method.


Fig. 5.

Experimental results of Map 1: (a) RRT and (b) proposed.


Fig. 6.

Experimental results of Map 2: (a) RRT and (b) proposed.


Fig. 7.

Experimental results of Map 3: (a) RRT and (b) proposed.


Fig. 8.

Experimental results of Map 4: (a) RRT and (b) proposed.


Table. 1.

Table 1. Computer performance for simulation.

H/WSpecification
CPUIntel Core i7-6700K 4.00 GHz (8 CPUs)
RAM32768 MB (32 GB DDR4)

Table. 2.

Table 2. Experimental results of Map 1.

PerformanceRRTProposal
Path length (pixel)1932 (100%)1403 (72%)
Planning time (ms)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.

Table 3. Experimental results of Map 2.

PerformanceRRTProposal
Path length (pixel)969 (100%)799 (82%)
Planning time (ms)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.

Table 4. Experimental results of Map 3.

PerformanceRRTProposal
Path length (pixel)591 (100%)529 (89%)
Planning time (ms)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.

Table 5. Experimental results of Map 4.

PerformanceRRTProposal
Path length (pixel)1533 (100%)1304 (85%)
Planning time (ms)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)..


Table. 6.

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

Input:
R ← path from {RRT/...}
C ← position set of all (measured) boundary points in all (known) obstacles
ɛ ← threshold value of minimum Clearance
Output:
R ← modified path R
Initialize:
fmodifytrue
ProcedurepostT riangularRewire
Begin
1WhilefmodifyDo
2fmodifyfalse// is the path modified
3t ← 0 // index of the currently focused point
4qchild ← first point in R
5qparent ← next point of qchild in R
6While not [qparent is last point in R] Do
7  qancestor ← next point of qparent in R
8  If notisT rapped(qchild, qancestor, C) Then
9   Rrewire(R, ɛ, t, fmodify)
10  Else
11   tt + 1
12   qchildt-th point in R
13  qparent ← next point of qchild in R
End

Table. 7.

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

Input:
R ← path R from postT riangularRewire
t ← point index t from postT riangularRewire
fmodify ← boolean fmodify from postT riangularRewire
Output:
R ← modified path R
fmodify ← result of boolean fmodify // return by reference
Procedure rewire FrompostT riangularRewire
Begin
1qchildt-th point in R
2qparent ← next point of qchild in R
3qancestor ← next point of qparent in R
4RDelete path< qchild, qparent > and path< qparent, qancestor > from R
5RInsert path< qchild, qancestor > to R
6fmodifytrue
End

  1. Schwab, K (2016). The Fourth Industrial Revolution. Geneva, Switzerland: World Economic Forum
  2. Choi, YI, Cho, JH, and Kim, YT (2020). Collision avoidance algorithm of mobile robots at grid map intersection point. International Journal of Fuzzy Logic and Intelligent Systems. 20, 96-104. https://doi.org/10.5391/IJFIS.2020.20.2.96
    CrossRef
  3. Jung, JH, and Kim, DH (2020). Local path planning of a mobile robot using a novel grid-based potential method. International Journal of Fuzzy Logic and Intelligent Systems. 20, 26-34. https://doi.org/10.5391/IJFIS.2020.20.1.26
    CrossRef
  4. LaValle, SM, and Kuffner, JJ (2001). Randomized kinodynamic planning. The International Journal of Robotics Research. 20, 378-400. https://doi.org/10.1177/02783640122067453
    CrossRef
  5. Kuffner, JJ, and LaValle, SM (). RRT-connect: an efficient approach to single-query path planning, 995-1001. https://doi.org/10.1109/ROBOT.2000.844730
  6. Kang, JG, Lim, DW, Choi, YS, Jang, WJ, and Jung, JW (). Improved RRT-connect algorithm based on triangular inequality for robot path planning. Sensors. 21, 2021. article no. 333
  7. Karaman, S, and Frazzoli, E (2011). Sampling-based algorithms for optimal motion planning. The International Journal of Robotics Research. 30, 846-894. https://doi.org/10.1177/0278364911406761
    CrossRef
  8. Gammell, JD, Srinivasa, SS, and Barfoot, TD (). Informed RRT*: optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic, 2997-3004. https://doi.org/10.1109/IROS.2014.6942976
  9. Klemm, S, Oberlander, J, Hermann, A, Roennau, A, Schamm, T, Zollner, JM, and Dillmann, R (). RRT*-Connect: faster, asymptotically optimal motion planning, 1670-1677. https://doi.org/10.1109/ROBIO.2015.7419012
  10. Islam, F, Nasir, J, Malik, U, Ayaz, Y, and Hasan, O (). RRT*-Smart: rapid convergence implementation of RRT* towards optimal solution, 1651-1656. https://doi.org/10.1109/ICMA.2012.6284384
  11. Roy, D (2019). Visibility graph-based spatial path planning of robots using configuration space algorithms. International Journal of Robotics & Automation. 24. article no. 2853
  12. Katevas, NI, Tzafestas, SG, and Pnevmatikatos, CG (1998). The approximate cell decomposition with local node refinement global path planning method: path nodes refinement and curve parametric interpolation. Journal of Intelligent and Robotic Systems. 22, 289-314. https://doi.org/10.1023/A:1008034314006
    CrossRef
  13. Warren, CW (). Global path planning using artificial potential fields, 316-317. https://doi.org/10.1109/ROBOT.1989.100007
  14. LaValle, SM (1998). Rapidly-exploring random trees: A new tool for path planning. Ames, IA: Department of Computer Science, Iowa State University
  15. Han, J, and Seo, Y (2017). Mobile robot path planning with surrounding point set and path improvement. Applied Soft Computing. 57, 35-47. https://doi.org/10.1016/j.asoc.2017.03.035
    CrossRef

Article

Original Article

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.

Post Triangular Rewiring Method for Shorter RRT Robot Path Planning

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)

Received: July 2, 2021; Revised: July 2, 2021; Accepted: September 9, 2021

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.

Abstract

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

1. Introduction

Path planning [13] 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 [510], 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.

2. Rapidly Exploring Random Tree

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.

3. Proposed Post Triangular Rewiring Method

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).

qancestor=ξ(qparent)=ξ2(qchild).

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, ξ0 (qi) = qi holds. That is, mF (qi, k) (k > 0) becomes the midpoint between mF (qi, k − 1) and ξ(qi). At this time, d is (dk − 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 qchild.

D(qchild,ξ(qchild))+D(ξ(qchild),ξ2(qchild))D(qchild,ξ2(qchild)).

Equation (3) is the distance D() expressed in (1) between the n-th ancestor nodes based on qchild 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.

fmodify 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 qchild, its next point is qparent, whose next point is qancestor, it is determined whether the distance between qchild and qancestor is free from obstacle collision (isT rapped() function). If it is free from collisions, it calls rewire(). rewire() connects qchild and qancestor, and the qparent between them is deleted from the path. If R and t are updated owing to rewire(), update qchild (the t-th waypoint of R), qparent, and qancestor accordingly. If qparent is the last point in R, then check fmodify. Otherwise, repeat the above process again for the updated qchild and qancestor.

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 fmodify. Rewiring is performed on the t-th waypoint qchild of R, next point qparent, and next point qancestor of that point. First, the path between qchild and qparent and the path between qparent and qancestor are deleted. Then, the path between qchild and qancestor is inserted. Finally, fmodify returns “true” because the path has been modified.

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

4. Experimental Results

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 58 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.

5. Conclusion

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.

Fig 1.

Figure 1.

Process of the RRT algorithm: In the case of creating new node qnew at a position separated by step length λ in the direction of the random sample position(qrand) based on the qnear node (position) nearest to the random sample position (qrand) in tree T with starting point qstart as the root node.

The International Journal of Fuzzy Logic and Intelligent Systems 2021; 21: 213-221https://doi.org/10.5391/IJFIS.2021.21.3.213

Fig 2.

Figure 2.

Summary of the post triangular rewiring method: (a) When line segment γ with node q0 and its grandparent node q2 in tree R is free from obstacle collision (Distance: γ < α+ β), (b) Grandparent node q2 of node q0 is connected as the parent node of node q0, and parent node q1 is deleted from the tree.

The International Journal of Fuzzy Logic and Intelligent Systems 2021; 21: 213-221https://doi.org/10.5391/IJFIS.2021.21.3.213

Fig 3.

Figure 3.

(a) Part of a tree consisting of node qchild, its parent node qparent, and node qancestor, the parent node of qparent. (b) If there is no obstacle between qchild and qancestor, delete the edge connecting to qparent in each node. (c) Edge α connecting qchild and qparent, edge β connecting qparent and qancestor, and edge γ connecting qchild and qancestor.

The International Journal of Fuzzy Logic and Intelligent Systems 2021; 21: 213-221https://doi.org/10.5391/IJFIS.2021.21.3.213

Fig 4.

Figure 4.

Flow chart of the proposed post triangular rewiring method.

The International Journal of Fuzzy Logic and Intelligent Systems 2021; 21: 213-221https://doi.org/10.5391/IJFIS.2021.21.3.213

Fig 5.

Figure 5.

Experimental results of Map 1: (a) RRT and (b) proposed.

The International Journal of Fuzzy Logic and Intelligent Systems 2021; 21: 213-221https://doi.org/10.5391/IJFIS.2021.21.3.213

Fig 6.

Figure 6.

Experimental results of Map 2: (a) RRT and (b) proposed.

The International Journal of Fuzzy Logic and Intelligent Systems 2021; 21: 213-221https://doi.org/10.5391/IJFIS.2021.21.3.213

Fig 7.

Figure 7.

Experimental results of Map 3: (a) RRT and (b) proposed.

The International Journal of Fuzzy Logic and Intelligent Systems 2021; 21: 213-221https://doi.org/10.5391/IJFIS.2021.21.3.213

Fig 8.

Figure 8.

Experimental results of Map 4: (a) RRT and (b) proposed.

The International Journal of Fuzzy Logic and Intelligent Systems 2021; 21: 213-221https://doi.org/10.5391/IJFIS.2021.21.3.213

Table 1 . Computer performance for simulation.

H/WSpecification
CPUIntel Core i7-6700K 4.00 GHz (8 CPUs)
RAM32768 MB (32 GB DDR4)

Table 2 . Experimental results of Map 1.

PerformanceRRTProposal
Path length (pixel)1932 (100%)1403 (72%)
Planning time (ms)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.

PerformanceRRTProposal
Path length (pixel)969 (100%)799 (82%)
Planning time (ms)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.

PerformanceRRTProposal
Path length (pixel)591 (100%)529 (89%)
Planning time (ms)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.

PerformanceRRTProposal
Path length (pixel)1533 (100%)1304 (85%)
Planning time (ms)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.

Input:
R ← path from {RRT/...}
C ← position set of all (measured) boundary points in all (known) obstacles
ɛ ← threshold value of minimum Clearance
Output:
R ← modified path R
Initialize:
fmodifytrue
ProcedurepostT riangularRewire
Begin
1WhilefmodifyDo
2fmodifyfalse// is the path modified
3t ← 0 // index of the currently focused point
4qchild ← first point in R
5qparent ← next point of qchild in R
6While not [qparent is last point in R] Do
7  qancestor ← next point of qparent in R
8  If notisT rapped(qchild, qancestor, C) Then
9   Rrewire(R, ɛ, t, fmodify)
10  Else
11   tt + 1
12   qchildt-th point in R
13  qparent ← next point of qchild in R
End

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

Input:
R ← path R from postT riangularRewire
t ← point index t from postT riangularRewire
fmodify ← boolean fmodify from postT riangularRewire
Output:
R ← modified path R
fmodify ← result of boolean fmodify // return by reference
Procedure rewire FrompostT riangularRewire
Begin
1qchildt-th point in R
2qparent ← next point of qchild in R
3qancestor ← next point of qparent in R
4RDelete path< qchild, qparent > and path< qparent, qancestor > from R
5RInsert path< qchild, qancestor > to R
6fmodifytrue
End

References

  1. Schwab, K (2016). The Fourth Industrial Revolution. Geneva, Switzerland: World Economic Forum
  2. Choi, YI, Cho, JH, and Kim, YT (2020). Collision avoidance algorithm of mobile robots at grid map intersection point. International Journal of Fuzzy Logic and Intelligent Systems. 20, 96-104. https://doi.org/10.5391/IJFIS.2020.20.2.96
    CrossRef
  3. Jung, JH, and Kim, DH (2020). Local path planning of a mobile robot using a novel grid-based potential method. International Journal of Fuzzy Logic and Intelligent Systems. 20, 26-34. https://doi.org/10.5391/IJFIS.2020.20.1.26
    CrossRef
  4. LaValle, SM, and Kuffner, JJ (2001). Randomized kinodynamic planning. The International Journal of Robotics Research. 20, 378-400. https://doi.org/10.1177/02783640122067453
    CrossRef
  5. Kuffner, JJ, and LaValle, SM (). RRT-connect: an efficient approach to single-query path planning, 995-1001. https://doi.org/10.1109/ROBOT.2000.844730
  6. Kang, JG, Lim, DW, Choi, YS, Jang, WJ, and Jung, JW (). Improved RRT-connect algorithm based on triangular inequality for robot path planning. Sensors. 21, 2021. article no. 333
  7. Karaman, S, and Frazzoli, E (2011). Sampling-based algorithms for optimal motion planning. The International Journal of Robotics Research. 30, 846-894. https://doi.org/10.1177/0278364911406761
    CrossRef
  8. Gammell, JD, Srinivasa, SS, and Barfoot, TD (). Informed RRT*: optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic, 2997-3004. https://doi.org/10.1109/IROS.2014.6942976
  9. Klemm, S, Oberlander, J, Hermann, A, Roennau, A, Schamm, T, Zollner, JM, and Dillmann, R (). RRT*-Connect: faster, asymptotically optimal motion planning, 1670-1677. https://doi.org/10.1109/ROBIO.2015.7419012
  10. Islam, F, Nasir, J, Malik, U, Ayaz, Y, and Hasan, O (). RRT*-Smart: rapid convergence implementation of RRT* towards optimal solution, 1651-1656. https://doi.org/10.1109/ICMA.2012.6284384
  11. Roy, D (2019). Visibility graph-based spatial path planning of robots using configuration space algorithms. International Journal of Robotics & Automation. 24. article no. 2853
  12. Katevas, NI, Tzafestas, SG, and Pnevmatikatos, CG (1998). The approximate cell decomposition with local node refinement global path planning method: path nodes refinement and curve parametric interpolation. Journal of Intelligent and Robotic Systems. 22, 289-314. https://doi.org/10.1023/A:1008034314006
    CrossRef
  13. Warren, CW (). Global path planning using artificial potential fields, 316-317. https://doi.org/10.1109/ROBOT.1989.100007
  14. LaValle, SM (1998). Rapidly-exploring random trees: A new tool for path planning. Ames, IA: Department of Computer Science, Iowa State University
  15. Han, J, and Seo, Y (2017). Mobile robot path planning with surrounding point set and path improvement. Applied Soft Computing. 57, 35-47. https://doi.org/10.1016/j.asoc.2017.03.035
    CrossRef

Share this article on :

Related articles in IJFIS

Most KeyWord