Finite-Time Near-Optimality Properties of Sampling-Based Motion Planners
|Title||Finite-Time Near-Optimality Properties of Sampling-Based Motion Planners|
|Publication Type||Conference Paper|
|Year of Publication||2013|
|Authors||Dobson, A, Bekris, KE|
|Conference Name||IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)|
|Conference Location||Tokyo Big Sight, Japan|
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 algorithms, such as PRM*, return optimal solutions in an asymptotic sense or near-optimal for the recently proposed roadmap spanners. Still, all these methods yield desired properties in an asymptotic fashion, meaning the properties are only truly attained after infinite amount of computation time. This work studies the finite-time properties of sampling-based algorithms in turns of path quality. The focus is on planners that construct roadmaps, as it is more straightforward to reason for these techniques. This paper argues that existing sampling-based planners, which construct roadmaps in an asymptotically optimal or 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 on point systems in Euclidean and toroidal spaces.