Exploring the Interaction of Geometry and Search in Path Planning.
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 01, 1992
- Accession Number
- ADA326959
Entities
People
- David J. Zhu
Organizations
- Stanford University