Smoothed analysis of probabilistic roadmaps (Q1028227)

The probabilistic roadmap algorithm that revolutionized robot planning is a simple heuristic that exhibits rapid performance with unbounded worst-case running time as a function of the input's combinatorial complexity. This paper initiates the use of smoothed analysis to explain the success of the probabilistic roadmap algorithm. A locally orthogonal decomposition is defined. The authors prove that for the roadmap to accurately represent the free configuration space it is sufficient that a milestone is sampled from every cell of this decomposition. A smoothed lower bound on the volume of every decomposition cell is proved, and a smoothed polynomial upper bound on the required number of milestones is established.