Informed RRT* with Adjoining Obstacle Process for Robot Path Planning

Abstract

Rapidly-exploring Random Tree (RRT) algorithm is efficient and popular in robot path planning, but cannot guarantee the optimality. RRT, an extension of RRT, claims to converge to asymptotic optimality by random optimized tree node in domain with a very slow rate. Informed RRT(IRRT*), samples random nodes by RRT* within a transformed ellipse which is the subset of original domain, outperforms RRT* in convergence rate and final solution quality. However, IRRT* depends on the current solution cost to build the ellipse. If the ellipse is not converged to optimal solution, the sampling time will be increased. This paper proposes Adjoined obstacle IRRT*(AIRRT*), a modified IRRT* that improves the velocity of ellipse sampling and generates the globally optimal path faster. AIRRT* uses an Adjoined process with linear interpolation to obtain valid obstacle vertices, reduce the ellipse area and converge to a shorter path to form a new ellipse and new solution. Simulations shown that AIRRT* can obtain the optimal path in effective time under different environments, and the performance is better than other algorithms.