The complexity of planar compliant motion planning under uncertainty

DOI10.1007/BF01840394zbMath0696.68054OpenAlexW1965466436MaRDI QIDQ911278

Bruce Randall Donald

Publication date: 1990

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01840394

zbMATH Keywords

computational complexitymotion planningrobotcontrol uncertaintygeometrical theory of planning

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computing methodologies and applications (68U99) Artificial intelligence (68T99) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (6)

Landmark-based robot navigation ⋮ A geometric approach to error detection recovery for robot motion planning with uncertainty ⋮ Hardness of uncertain segment cover, contiguous SAT and visibility with uncertain obstacles ⋮ Reaching a goal with directional uncertainty ⋮ On information invariants in robotics ⋮ An efficient algorithm for one-step planar compliant motion planning with uncertainty

Cites Work

• Visibility of disjoint polygons
• Dynamic path planning for a planar articulated robot arm moving amidst unknown obstacles
• Generalized Voronoi diagrams for a ladder. II: Efficient construction of the diagram
• A search algorithm for motion planning with six degrees of freedom
• Simplified Voronoi diagrams
• On multiple moving objects
• A geometric approach to error detection recovery for robot motion planning with uncertainty
• Complexity of deciding Tarski algebra
• A “retraction” method for planning the motion of a disc
• Spatial Planning: A Configuration Space Approach
• Reducing Multiple Object Motion Planning to Graph Searching
• Generalized voronoi diagrams for moving a ladder. I: Topological analysis

This page was built for publication: The complexity of planar compliant motion planning under uncertainty