During the last decade, incremental sampling-based motion planning
algorithms, such as the Rapidly-exploring Random Trees (RRTs) have been shown
to work well in practice and to possess theoretical guarantees such as
probabilistic completeness. However, no theoretical bounds on the quality of
the solution obtained by these algorithms have been established so far. The
first contribution of this paper is a negative result: it is proven that, under
mild technical conditions, the cost of the best path in the RRT converges
almost surely to a non-optimal value. Second, a new algorithm is considered,
called the Rapidly-exploring Random Graph (RRG), and it is shown that the cost
of the best path in the RRG converges to the optimum almost surely. Third, a
tree version of RRG is introduced, called the RRT$^*$ algorithm, which
preserves the asymptotic optimality of RRG while maintaining a tree structure
like RRT. The analysis of the new algorithms hinges on novel connections
between sampling-based motion planning algorithms and the theory of random
geometric graphs. In terms of computational complexity, it is shown that the
number of simple operations required by both the RRG and RRT$^*$ algorithms is
asymptotically within a constant factor of that required by RRT.

本文介绍了一种新型的算法 —— 快速探索随机图（RRG）及其树形版本 RRT $ ^ * $ 算法，并证明这两个算法都可以在几乎确定地收敛到最优解。此外，文章还建立起采样运动规划算法和随机几何图理论之间的新联系，以证明所提出算法的复杂度与传统 RRT 算法相比是等价的。