Degree Type

Dissertation

Date of Award

1997

Degree Name

Doctor of Philosophy

Department

Mechanical Engineering

First Advisor

James H. Oliver

Abstract

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.

DOI

https://doi.org/10.31274/rtd-180813-10480

Publisher

Digital Repository @ Iowa State University, http://lib.dr.iastate.edu/

Copyright Owner

Shiang-Fong Chen

Language

en

Proquest ID

AAI9725400

File Format

application/pdf

File Size

101 pages

Share

COinS