Optimization approaches for geometric constraints in robot motion planning

This thesis focuses on the development of algorithms and tools for incorporating geometric constraints in robot motion planning. We consider two types of motion planning problems: (1) We first look at point-to-point motion planning for a single robot in the presence of geometric, kinematic, and dynamic constraints. (2) We then look at multiple robot path planning problems where the robots are required to visit a set of points in the presence of geometric constraints.;Point-to-point robot motion planning, i.e., obtaining control inputs to move the robot from one state to another, taking into consideration geometric, kinematic, and dynamic constraints is a fundamental problem in realizing autonomous robotic systems. Collision detection and dynamic simulation are two important modules that form an integral part of current sampling based randomized motion planners. The collision detection module ensures that the geometric constraints are satisfied and the dynamic simulation module ensures that the state evolution satisfy the differential constraints. Most research in sampling based motion planning algorithms treat these two modules as a black-box and use them to only obtain an input giving a feasible trajectory; an input is rejected if there is any collision along the trajectory. In the first part of this thesis, we show that using a complementarity based formulation of the dynamics, we can use the collision information to modify the applied inputs and obtain inputs that ensure a collision free trajectory. This is useful in applications where collision avoidance is the primary requirement. However, in the presence of intermittent contact between the robot and objects in the environment as seen in applications like grasping, manipulation, locomotion, the presence of contact makes accurate dynamic simulation challenging. Consequently, we study the sources of errors in current dynamic simulators.;The primary sources of stability and accuracy problems in state-of-the-art time steppers for multibody systems are (a) the use of polyhedral representations of smooth bodies, (b) the decoupling of collision detection from the solution of the dynamic time-stepping subproblem, and (c) errors in model parameters. We focus on formulations, algorithm development, and analysis of time-steppers to eliminate the first two error sources. As a partial solution to problem (a) above, we provide distance computation algorithms for convex objects modeled as an intersection of implicit surfaces. The use of implicit surfaces to describe objects for dynamic simulation is impaired by the lack of algorithms to compute exact distances between implicit surface objects. In contrast to geometric approaches developed for polyhedral objects, we formulate the distance computation problem as a convex optimization problem and use a primal-dual interior point method to solve the Karush-Kuhn-Tucker (KKT) conditions obtained from the convex program. For the case of polyhedra and quadrics, we establish a theoretical time complexity of O(n 1:5), where n is the number of constraints; in practice the algorithm takes linear time. We then provide solutions for problem (a) and (b) described above for simulating multibody systems with intermittent contact by incorporating the contact constraints as a set of complementarity and algebraic equations within the dynamics model. This enables us to formulate a geometrically implicit time-stepping scheme (i:e:, we do not need to approximate the distance function) as a nonlinear complementarity problem (NCP). The resulting time-stepper is therefore more accurate; further it is the first geometrically implicit time-stepper that does not rely on a closed form expression for the distance function. We first present our approach assuming the bodies to be rigid and then extend it to locally compliant or quasi-rigid bodies. We demonstrate through example simulations the fidelity of this approach to analytical solutions and previously described simulation results. This distance computation and dynamic simulation work may also be of interest outside of robot motion planning to applications in mechanical design and haptic interaction.;For multiple robot systems, the task requirements can also lead to geometric constraints and the system performance depends on task allocation to the robots in the presence of geometric constraints. In the second part of this thesis we study such a problem, namely, path planning for multiple robots (say K) required to cover a point set in the presence of inter-robot geometric constraints so that the task completion time is minimized. (Abstract shortened by UMI.)...