The complexity of robot motion planning

作者：John Canny · 发表于：Medical Entomology and Zoology · 年份：1988 · 被引用次数：1393 · 研究领域：Robotic Path Planning Algorithms、Computational Geometry and Mesh Generation、Logic, programming, and type systems

The Complexity of Robot Motion Planning makes original contributions both to robotics and to the analysis of algorithms. In this groundbreaking monograph John Canny resolves long-standing problems concerning the complexity of motion planning and, for the central problem of finding a collision free for a jointed robot in the presence of obstacles, obtains exponential speedups over existing algorithms by applying high-powered new mathematical techniques.Canny's new algorithm for this movers' the most-studied and basic robot motion planning problem, has a single exponential running time, and is polynomial for any given robot. The algorithm has an optimal running time exponent and is based on the notion of roadmaps - one-dimensional subsets of the robot's configuration space. In deriving the single exponential bound, Canny introduces and reveals the power of two tools that have not been previously used in geometric algorithms: the generalized (multivariable) resultant for a system of polynomials and Whitney's notion of stratified sets. He has also developed a novel representation of object orientation based on unnormalized quaternions which reduces the complexity of the algorithms and enhances their practical applicability.After dealing with the movers' problem, the book next attacks and derives several lower bounds on extensions of the problem: finding the shortest among polyhedral obstacles, planning with velocity limits, and compliant motion planning with uncertainty. It intro...