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.
UM campus only
Doctor of Philosophy (PHD)
Computer Science (Arts and Sciences)
Date of Defense
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
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.
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
Trac, Steven Cy, "Robust Explicit Construction of 3D Configuration Spaces Using Controlled Linear Perturbation" (2008). Open Access Dissertations. 189.