Off-campus University of Miami users: To download campus access dissertations, please use the following link to log into our proxy server with your University of Miami CaneID and Password.

Non-University of Miami users: Please talk to your librarian about requesting this dissertation through interlibrary loan.

Publication Date

2008-12-19

Availability

UM campus only

Degree Type

Dissertation

Degree Name

Doctor of Philosophy (PHD)

Department

Computer Science (Arts and Sciences)

Date of Defense

2008-11-21

First Committee Member

Victor Milenkovic - Committee Chair

Second Committee Member

Hongtan Liu - Committee Member

Third Committee Member

Brian Coomes - Committee Member

Fourth Committee Member

Elisha Sacks - Committee Member

Fifth Committee Member

Geoff Sutcliffe - Committee Member

Abstract

We present robust explicit construction of 3D configuration spaces using controlled linear perturbation. The input is two planar parts: a fixed set and a moving set, where each set is bounded by circle segments. The configuration space is the three-dimensional space of Euclidean transformation (translations plus rotations) of the moving set relative to the fixed set. The goal of constructing the 3D configuration space is to determine the boundary representation of the free space where the intersection of the moving set and fixed set is empty. To construct the configuration space, we use the controlled linear perturbation algorithm. The controlled linear perturbation algorithm assigns function signs that are correct for a nearly minimal input perturbation. The output of the algorithm is a consistent set of function signs. This approach is algorithm-independent, and the overhead over traditional floating point methods is reasonable. If the fixed and moving sets are computer representations of physical objects, then computing the configuration space greatly aids in many computational geometry problems. The main focus of computing the configuration space is for the path planning problem. We must find if a path exists from the start to the goal, where the fixed set is the obstacle, and the moving set is the object trying to reach the goal.

Keywords

SEE; Path Plotting; Events; Exact Methods; Algorithms; LAPACK; Primitives; Path Plan; SVE; Perturbation; Arrangements; Resolution Complete; Inconsistency Sensitive; Criticality; Probabilistic Complete; Free Space; 3D Manifold; Sampling; Safety Margin; LP; CPLEX; Linear Programming; Ray Tracing

Download

Share

COinS