Accession Number : ADA326959

Title :   Exploring the Interaction of Geometry and Search in Path Planning.

Descriptive Note : Doctoral thesis,

Corporate Author : STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Zhu, David J.

PDF Url : ADA326959

Report Date : FEB 1992

Pagination or Media Count : 207

Abstract : This thesis addressed the problem of developing path planning algorithms that are both efficient and well-behaved. We proposed a novel approach in which we solve a path planning problem by finding and solving an appropriate abstraction of the original problem. We argued that in order for this approach to be efficient, a tighter integration of geometric reasoning and search is essential. This thesis developed evidence, both theoretical and experimental, to support this argument. In particular, we investigated in-depth two approaches for generating problem abstractions: the constraint approximation approach (in the context of robot motion planning); and the problem decomposition approach (in the context of pipe routing). For each of these two approaches, we developed algorithms that tightly integrate geometric reasoning with search and we addressed many issues raised by this integration. These algorithms have been implemented and tested in a robot motion planning system and a pipe routing system.

Descriptors :   *ALGORITHMS, *ROBOTICS, OPTIMIZATION, COMPUTER AIDED DESIGN, TIME DEPENDENCE, ROBOTS, PATHS, THESES, ARTIFICIAL INTELLIGENCE, SYSTEMS ANALYSIS, AUTONOMOUS NAVIGATION, CONTROL THEORY, PROJECTIVE GEOMETRY.

Subject Categories : Cybernetics

Distribution Statement : APPROVED FOR PUBLIC RELEASE