# Path Planning of a Mobile Robot Based on the Improved RRT Algorithm
## 1 Introduction  
Path planning is the problem of finding a safe path from an initial state to a target state in a given area and selecting an optimal scheme based on evaluation indicators such as path distance and planning time [1, 2]. Path planning is a key technology in the fields of robotics, drones, autonomous driving, etc., and has attracted widespread attention from researchers [3]. In the past few decades, many path-planning algorithms have been proposed, such as the graph-based A* algorithm [4], the artificial potential field (APF) algorithm [5], the genetic algorithm (GA) [6, 7], the sampling-based probabilistic road map (PRM) algorithm [8], etc. The A* algorithm is an effective method for solving the shortest-path problem, but its performance depends on the grid size of the resolution. The A* algorithm has an exponential increenment in computing cost when an environment is complex. The APF algorithm constructs a virtual force field to realize real-time path planning, but it is easy to fall into a local optimum. The GA optimizes populations of candidate solutions using selection, crossover, and mutation operations to find an optimal solution, but it has a problem of premature convergence. The PRM algorithm constructs a roadmap by sampling in the configuration space and then searches for a path using graph search methods, but it relies on the quality of the samples. The RRT algorithm [9] builds a search tree by sampling randomly in the configuration space. Compared to traditional path-planning algorithms, the RRT algorithm can find a feasible path without complex environment modeling and handle high-dimensional complex situations. However, the RRT algorithm cannot guarantee the quality of the path. [PERSON] et al. [10] proposed the RRT* algorithm to solve this issue, which considers the cost of neighboring states after each successful expansion and uses Choose-Parent and Rewire strategies to modify the connection between a new state and its neighbors. The RRT* algorithm has been proven to be asymptotically optimal, as it can reach an optimalsolution when the number of samples go to infinity, but it takes a lot of time. In other words, RRT* is an algorithm that trades computing cost for performance. The crucial reason for the inefficiency of the RRT* algorithm is that the entire search tree needs to be traversed when a state is inserted into the tree. As the number of states increases, the cost of traversing the tree each time becomes huge. To accelerate the convergence process of the RRT* algorithm, in [11], the Informed-RRT* algorithm introduces an ellipsoidal heuristic set, in which the current best solution is used as the major axis of the ellipse, and the initial state and target state are treated as the focus of the ellipse, which can restrict the sampling process to this set. As better solutions are found, the heuristic set is reduced gradually. It greatly reduces unnecessary explorations in these regions where the solution probably does not exist. However, the quality of the initial path has a decisive influence on the performance of the algorithm. In the worst situation, the Informed-RRT* algorithm equals the RRT* algorithm in performance. [PERSON] et al. [12] proposed the RRT*-smart algorithm using the idea of triangle inequality to optimize the path after finding the solution and then taking bias sampling to high-quality nodes. As the name suggests, this algorithm selects sampling nodes more purposefully, but it also faces the same issue as the Informed-RRT*. [PERSON] et al. [13] presented the Fast-RRT algorithm, which increases the speed of searching for the optimal path by fusing the current solution with the best solution continuously, but this algorithm cannot guarantee to achieve the optimal solution. Recently, some post-processing methods have been used in path optimization. The advantage of these methods is that they have no impact on the performance of the planner while improving the quality of the path within an acceptable time.