Degree Type


Date of Award


Degree Name

Doctor of Philosophy


Mechanical Engineering

First Advisor

James H. Oliver


Motion planning is an important challenge in robotics research. Efficient generation of collision-free motion is a fundamental capability necessary for autonomous robots;In this dissertation, a fast and practical algorithm for moving a convex polygonal robot among a set of polygonal obstacles with translations and rotations is presented. The running time is O(c((n + k)N + nlogn)), where c is a parameter controlling the precision of the results, n is the total number of obstacle vertices, k is the number of intersections of configuration space obstacles, and N is the number of obstacles, decomposed into convex objects. This dissertation exploits a simple 3D passage-network to incorporate robot rotations as an alternative to complex cell decomposition techniques or building passage networks on approximated 3D C-space obstacles;A common approach in path planning is to compute the Minkowski difference of a polygonal robot model with the polygonal obstacle environment. However such a configuration space is valid only for a single robot orientation. In this research, multiple configuration spaces are computed between the obstacle environment and the robot at successive angular orientations spanning [pi] . Although the obstacles do not intersect, each configuration space may contain intersecting configuration space obstacles (C-space obstacles). For each configuration space, the algorithm finds the contour of the intersected C-space obstacles and the associated passage network by slabbing the collision-free space. The individual configuration spaces are then related to one another by a heuristic called "proper links" that exploit spatial coherence. Thus, each level is connected to the adjacent levels by proper links to construct a 3D network. Dijkstra's algorithm is used to search for the shortest path in the 3D network. Finally, the path is projected onto the plane to show the final locus of the path.



Digital Repository @ Iowa State University,

Copyright Owner

Shiang-Fong Chen



Proquest ID


File Format


File Size

101 pages