Paper Info
Title
A Study On The Finite-Time Near-Optimality Properties Of Sampling-Based Motion Planners
Abstract
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.
Year
DOI
Venue
2013
10.1109/IROS.2013.6696508
2013 IEEE/RSJ INTERNATIONAL CONFERENCE ON INTELLIGENT ROBOTS AND SYSTEMS (IROS)
Keywords
Field
DocType
path planning,probability,sampling methods
Motion planning,Mathematical optimization,Computer science,Workspace,Sampling (statistics),Probabilistic logic,Configuration space,Finite time,Computation
Conference
ISSN
Citations 
PageRank 
2153-0858
4
0.43
References 
Authors
8
2
Name
Order
Citations
PageRank
Andrew Dobson1503.90
Kostas E. Bekris293899.49