Optimization Path Planning Algorithm Rapidly-Exploring Random Trees* (RRT*) with Fixed Node, Mesh Grid and Visibility Graph Sampling-Based Method

摘要

Path planning is very necessary in an autonomous mobile robot system to ensure a planned collision- free path from the starting point to the destination point in the navigation environment In general, there are two methods for finding paths, namely Deterministic and Random Graph Search. One of the random graph search algorithms that is often used for path planning is Rapidly Exploring Random Trees (RRT). RRT is a path planning algorithm that forms nodes randomly from the start point to the end point in the navigation environment. RRT can ensure probabilistic completeness but does not guarantee that the specified path is the shortest path in the navigation environment The proposed extension of the RRT and guaranteeing a shorter path length is RRT*. RRT* claims a more optimal solution than RRT but the path formed is not yet the most optimal path. This article introduces an RRT* algorithm with several innovative methods that can form optimal paths with shorter paths, less memory usage, and fewer iterations. The fixed node method is used to select the node to be selected and stored when searching for nodes, so that it uses less memory. Meanwhile, to reduce the number of iterations needed to form a path from the starting point to the destination point, a sampling-based method is used when looking for q <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">new</inf> from q <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">near</inf> and q <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">grand</inf> .