An Improved RRT* Algorithm for Multi-Objective Optimization Based on NSGA-III

The RRT
^1
1
RRT: Rapidly exploring random trees. algorithm is a path planning method based on random sampling, which can effectively solve the path planning problem of high-dimensional planning or complex constraints. Although the RRT algorithm is a relatively efficient and completely probabilistic motion planning algorithm, there are still some problems, such as the result isn't relatively optimized or the stability of the path is awful. The improved RRT* algorithm improves the path optimization ability to a certain extent and is asymptotically optimal. However, this algorithm is incapable of dealing with multi-objective optimization problems. Since the NSGAIII-RRT*
^2
2
NSGAIII: Non-dominated Sorting Genetic Algorithms-III. algorithm is proposed in this paper to solve the defect of multi-objective optimization ability of the RRT and its improved algorithms. The non-dominated genetic sorting algorithm based on reference points is used to improve the operation of reselecting the parent nodes of the RRT
^*
algorithm, and Pareto optimal population is used instead of single path iteration. This algorithm can effectively solve the problem of high-dimensional path planning under complex approximate conditions. It can also carry out multi-objective optimization of the feasible path, and converge to a uniform set of feasible path's Pareto front. According to the results of simulation experiments, the extreme value data of the rotation angle is reduced by 42.76% on average compared with the original RRT algorithm, and the average path length of the end effector is also reduced by 63.34%.