DocumentCode
426202
Title
Sampling-based planning for discrete spaces
Author
Morgan, Stuart ; Branicky, Michael S.
Author_Institution
Dept. of Electr. Eng. & Comput. Sci., Case Western Reserve Univ., Cleveland, OH, USA
Volume
2
fYear
2004
fDate
28 Sept.-2 Oct. 2004
Firstpage
1938
Abstract
In this paper, we introduce several discrete space search algorithms based on continuous-space motion planning techniques such as rapidly exploring random trees (RRTs) and probabilistic roadmaps (PRMs). We describe methods for adapting these algorithms for discrete use by replacing distance metrics with cost-to-go heuristic estimates and substituting local planners for straight-line connectivity. Finally, we explore coverage and optimality properties of these algorithms in discrete spaces.
Keywords
discrete systems; path planning; probability; random processes; tree searching; continuous-space motion planning; discrete space search algorithm; probabilistic roadmap; rapidly exploring random trees; sampling based planning; Computer science; Euclidean distance; Motion control; Search problems; Space exploration; Testing;
fLanguage
English
Publisher
ieee
Conference_Titel
Intelligent Robots and Systems, 2004. (IROS 2004). Proceedings. 2004 IEEE/RSJ International Conference on
Print_ISBN
0-7803-8463-6
Type
conf
DOI
10.1109/IROS.2004.1389681
Filename
1389681
Link To Document