Asymptotic Optimality of Rapidly Exploring Random Tree
This work addresses the theoretical limitations of RRT for robotics and motion planning, providing incremental insights into optimality conditions.
The paper proves that the Rapidly Exploring Random Tree (RRT) motion planner is not asymptotically optimal, showing that its vertex degree distribution follows a power law asymptotically, and proposes a necessary condition for asymptotic optimality in sampling-based planners.
In this paper we investigate the asymptotic optimality property of a randomized sampling based motion planner, namely RRT. We prove that a RRT planner is not an asymptotically optimal motion planner. Our result, while being consistent with similar results which exist in the literature, however, brings out an important characteristics of a RRT planner. We show that the degree distribution of the tree vertices follows a power law in an asymptotic sense. A simulation result is presented to support the theoretical claim. Based on these results we also try to establish a simple necessary condition for sampling based motion planners to be asymptotically optimal.