Genetic RRT: Asymptotically Optimal Sampling-based Path Planning via Optimization of Genetic Algorithm

Abstract

As one of the most frequently used stochastic planners, Rapidly-exploring random trees (RRT) is commonly applied to the path-planning problem in the continuous state space. For single-query problems, RRTs demonstrate nice properties in computation speed and universality. However, the probabilistically complete results of the planning problems hinder their further use. To date, some heuristic-biased sampling searches like hRRT and Informed RRT* addressed the optimality problem of RRTs in the path-planning. However, using the heuristic subsets to bias sampling improved the performance of the algorithms while eliminating the probability of finding other equal optimal solutions simultaneously. To minimize the cost of solutions in the path-planning problems, this paper presents a novel method to focus on the optimization of paths planned by RRTs in terms of the genetic algorithm. The demonstrated planning technique’s advantages can be seen with a new algorithm, Genetic RRT, which retains the multi-results nature and the same effectiveness toward high-dimension path-planning problems as RRTs while significantly increasing the probability of finding an asymptotically optimal path via optimization of genetic algorithm, as the number of iterations increases.