Geometric Motion Planning Methods for Robotics and Biological Crystallography
MetadataShow full item record
This dissertation presents several novel approaches to motion planning problems by incorporating useful geometrical models. Two different approaches are addressed in the contexts of biological crystallography and robot motion planning, respectively. In the context of biological crystallography, the method of molecular replacement (MR) is frequently used to obtain the phase information for a crystallographic unit cell packed with copies of a macromolecule of unknown conformation. This is important because an X-ray diffraction experiment on its own does not provide full structural information. MR works quite well for single-domain proteins that can be treated as single rigid-bodies. However, for multi-domain structures and complexes, computational requirements can become prohibitive due to the ``curse of dimensionality''. We introduce a new phasing approach by using geometric constraints on protein crystals to generate packing models and therefore replace the computationally expensive MR searches in a continuous configuration space with a search on a relatively small discrete set of candidate packing arrangements. In the context of robot motion planning, an approach based on the closed-form representation of the robot's collision-free configuration space (C-space) is presented. In this approach, the robot, obstacles, and environment are modeled as ellipsoids or finite unions of ellipsoids in the workspace. These objects can be quite general, approximated by unions of different ellipsoidal bounding boxes, and this approach represents an alternative to polyhedral representations of bodies. The approach builds on the core idea that the space of collision-free motions of one moving ellipsoid relative to one fixed ellipsoid can be characterized exactly in closed form. This means that for ellipsoidal bodies, there is no need to sample and discard configurations suspected of being in collision. This approach of ``knowing where to look'' for path planning in C-spaces is especially useful for the narrow passage problem. Additionally, the quality of samples on the rotation and motion spaces is important in these applications, especially for sampling based motion planning methods. In this dissertation, we also developed a group-theoretic based approach to achieve almost-uniform sampling of these spaces and to further facilitate a broader class of motion planning problems. This approach is based on decomposing the rotation and Special Euclidean groups into identical Voronoi cells centered on the elements of their discrete subgroups. Within each cell, regular grids in exponential coordinates are used to achieve almost-uniform sampling at any level of resolution, without having to store large numbers of coordinates, and without requiring sophisticated data structures. We also analyze the shape of these cells, and discuss how this new method can be used in the context of conformational searches in the fields of structural biology and robotics contexts.