Probabilistic sampling-based algorithms represent a particularly successful approach to robotic motion planning problems [14, 26]. The key idea behind probabilistic sampling-based algorithms is to avoid the explicit construction of the configuration space (which can be prohibitive in complex planning problems) and instead conduct a search that probabilistically probes the configuration space with independent and identically distributed (i.i.d.) random samples. Explicitly, each i.i.d. point is generated in the same way (e.g., from a uniform distribution over the configuration space) and without using any information about any of the other sampled points. This probing is enabled by a collision detection module, which the motion planning algorithm considers as a "black box" [14]. Examples, roughly in chronological order, include the probabilistic roadmap algorithm (PRM) [13], expansive space trees (EST) [9, 20], Lazy-PRM [4], the rapidly exploring random trees algorithm (RRT) [15], sampling-based roadmap of trees (SRT) [22], rapidly-exploring roadmap [1], PRM~* and RRT~* [12], RRT~# [2], and the fast marching tree algorithm (FMT~*) [11]. A central result is that these algorithms provide probabilistic completeness guarantees in the sense that the probability that the planner fails to return a solution, if one exists, decays to zero as the number of samples approaches infinity [3]. Recently, it has been proven that RRT~*, PRM~*, RRT~#, and FMT~* are asymptotically optimal, i.e., the cost of the returned solution converges almost surely to the optimum [2, 11, 12].
展开▼
