Smoothed analysis of probabilistic roadmaps
type: Item
instance of: scholarly article
title: Smoothed analysis of probabilistic roadmaps
zbMATH Open document ID: 1169.65052
author: Siddhartha Chaudhuri
author: Vladlen Koltun
published in: Computational Geometry
publication date: 2009-06-30T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 90C59
Mathematics Subject Classification ID: 90C15
Mathematics Subject Classification ID: 62P30
Mathematics Subject Classification ID: 65Y20
zbMATH DE Number: 5572054
zbMATH Keywords: motion planning
zbMATH Keywords: probabilistic roadmap
zbMATH Keywords: smoothed analysis
zbMATH Keywords: locally orthogonal decomposition
zbMATH Keywords: robot planning
zbMATH Keywords: heuristic
zbMATH Keywords: combinatorial complexity
zbMATH Keywords: algorithm
describes a project that uses: k-means++
MaRDI profile type: Publication
full work available at URL: j.comgeo.2008.10.005
OpenAlex ID: W1991435017
cites work: Computing depth orders for fat objects and related problems
cites work: Castles in the air revisited
cites work: Worst-Case and Smoothed Analysis of the ICP Algorithm, with an Application to the k-Means Method
cites work: Mathematical Foundations of Computer Science 2003
cites work: Dynamic motion planning in low obstacle density environments
cites work: Q4829029
cites work: A singly exponential stratification scheme for real semi-algebraic varieties and its applications
cites work: Nearest neighbor queries in metric spaces
cites work: Algorithms - ESA 2003
cites work: Algorithms – ESA 2004
cites work: Linear size binary space partitions for fat objects
cites work: Linear size binary space partitions for uncluttered scenes
cites work: Realistic input models for geometric algorithms
cites work: Nice point sets can have nasty Delaunay triangulations
cites work: Q4942235
cites work: Q4234082
cites work: Almost tight upper bounds for vertical decompositions in four dimensions
cites work: Q4856179
cites work: Range Searching and Point Location among Fat Objects
cites work: Q4040885
cites work: Range searching in low-density environments
cites work: Q4401030
cites work: Q4418806
cites work: Smoothed analysis of termination of linear programming algorithms
cites work: Smoothed analysis of algorithms
DOI: 10.1016/J.COMGEO.2008.10.005
Recommended article: Smoothed Analysis of Probabilistic Roadmaps
Recommended article: On the Probabilistic Foundations of Probabilistic Roadmap Planning
Recommended article: A baby steps/giant steps probabilistic algorithm for computing roadmaps in smooth bounded real hypersurface
Recommended article: SMOOTH PATHS OF CONDITIONAL EXPECTATIONS
Recommended article: Smoothed Analysis of the Successive Shortest Path Algorithm
description: scientific article; zbMATH DE number 5572054