Simplified and Smoothed Rapidly-Exploring Random Tree Algorithm for Robot Path Planning

Abstract

Rapidly-exploring Random Tree (RRT) is a prominent algorithm with quite successful results in achieving the optimal solution used to solve robot path planning problems. The RRT algorithm works by creating iteratively progressing random waypoints from the initial waypoint to the goal waypoint. The critical problem in the robot movement is the movement and time costs caused by the excessive number of waypoints required to be able to reach the goal, which is why reducing the number of waypoints created after path planning is an important process in solving the robot path problem. Ramer-Douglas-Peucker (RDP) is an effective algorithm to reduce waypoints. In this study, the Waypoint Simplified and Smoothed RRT Method (WSS-RRT) is proposed which reduces the distance costs between 8.13% and 13.36% by using the RDP algorithm to reduce the path into the same path with fewer waypoints, which is an array of waypoints created by the RRT algorithm.

Keywords

• distance minimization
• optimization approach
• path planning
• reduction algorithm
• simplification