A study on the finite-time near-optimality properties of sampling-based motion planners
Andrew Dobson, Kostas E. Bekris · 2013
Sampling-based algorithms have proven practical in solving motion planning challenges in relatively high-dimensional instances in geometrically complex workspaces. Early work focused on quickly returning feasible solutions. Only recently was it shown under which conditions these algorithms asymptotically return optimal or near-optimal solutions. These methods yield desired properties only in an asymptotic fashion, i.e., the properties are attained after infinite computation time. This work studies the finite-time properties of sampling-based planners in terms of path quality. The focus is on roadmap-based methods, due to their simplicity. This work illustrates that existing sampling-based planners which construct roadmaps in an asymptotically (near-)optimal manner exhibit a “probably near-optimal” property in finite time. This means that it is possible to compute a confidence value, i.e. a probability, regarding the existence of upper bounds for the length of the path returned by the roadmap as a function of the number of configuration space samples. This property can result in useful tools for determining existence of solutions and a probabilistic stopping criterion for PRM-like methods. These properties are validated through experimental trials.