Finite-Time Near-Optimality Properties of Sampling-Based Motion Planners

TitleFinite-Time Near-Optimality Properties of Sampling-Based Motion Planners
Publication TypeConference Paper
Year of Publication2013
AuthorsDobson, A, Bekris, KE
Conference NameIEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)
Date Published11/2013
Conference LocationTokyo 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.

Refereed DesignationRefereed