Complexity of robot motion planning / John Canny

Auteur: Canny, John Francis (1953-) - AuteurType de document: Monographie Collection: ACM doctoral dissertation awards Langue: anglaisPays: Etats UnisÉditeur: Cambridge (Mass.) : MIT Press, cop. 1988Description: 1 vol. ( XV-195 p.) : fig. ; 24 cm ISBN: 0262031361 ; rel. Note: Presented annually to the author(s) of the best doctoral dissertation(s) in computer science and engineering. The Doctoral Dissertation Award is accompanied by a prize of $20,000, and the Honorable Mention Award is accompanied by a prize of $10,000. Financial sponsorship of the award is provided by Google. Winning dissertations will be published in the ACM Digital Library as part of the ACM Books Series (ACM)Résumé: 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 path 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 "generalized movers' problem," 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 path among polyhedral obstacles, planning with velocity limits, and compliant motion planning with uncertainty. It introduces a clever technique, "path encoding," that allows a proof of NP-hardness for the first two problems and then shows that the general form of compliant motion planning, a problem that is the focus of a great deal of recent work in robotics, is non-deterministic exponential time hard. Canny proves this result using a highly original construction. (Source : MIT Press).Bibliographie: Bibliogr. p. 187-195. Index.Thèse: Texte remanié de : Thèse de doctorat en informatique, soutenue en 1987, organisme : Massachusetts Institute of Technology Sujets MSC: 68Uxx -- Computing methodologies and applications Computer science
68Q25 -- Analysis of algorithms and problem complexity Computer science -- Theory of computing
90B40 -- Search theory Operations research, mathematical programming -- Operations research and management science
93Cxx -- Control systems Systems theory; control
En-ligne: MIT Press | MathSciNet
Location Call Number Status Date Due
Salle R 10132-01 / 68 CAN (Browse Shelf) Available

Presented annually to the author(s) of the best doctoral dissertation(s) in computer science and engineering. The Doctoral Dissertation Award is accompanied by a prize of $20,000, and the Honorable Mention Award is accompanied by a prize of $10,000. Financial sponsorship of the award is provided by Google. Winning dissertations will be published in the ACM Digital Library as part of the ACM Books Series (ACM)

Bibliogr. p. 187-195. Index

Texte remanié de : Thèse de doctorat informatique 1987 Massachusetts Institute of Technology

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 path 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 "generalized movers' problem," 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 path among polyhedral obstacles, planning with velocity limits, and compliant motion planning with uncertainty. It introduces a clever technique, "path encoding," that allows a proof of NP-hardness for the first two problems and then shows that the general form of compliant motion planning, a problem that is the focus of a great deal of recent work in robotics, is non-deterministic exponential time hard. Canny proves this result using a highly original construction. (Source : MIT Press)

There are no comments for this item.

Log in to your account to post a comment.
Languages: English | Français | |