|
||||||||||||||||
|
Ph.D. ThesesOptimization Based Approaches for Geometric Constraints in Robot Motion Planning
By Nilanjan Chakraborty
Robots interacting with their environment must take geometric constraints into account for effective planning. These geometric constraints arise from the presence of other objects, task requirements, and the robot's structure. Apart from the geometric constraints, the robots are also subject to dynamics and kinematics constraints. The mathematical models of these systems are non-smooth and therefore developing algorithms for their simulation and planning is challenging. In this thesis, we develop optimization-based solutions to two problems in robotics with these characteristics: (a) Simulation of systems of bodies that move with intermittent contact with each other and their use in kinodynamic robot motion planning algorithms and (b) Path planning for multiple robots that are required to cover a set of points while satisfying given geometric constraints. In the first part, I present an algorithm for using complementarity based contact dynamics simulation algorithms in kinodynamic robot motion planning. This is useful where collision avoidance is the key requirement, but in applications like grasping, manipulation, where maintaining contact is desirable, accurate dynamic simulation is very challenging. Even state-of-the-art simulators cannot accurately simulate a disc rolling on a table. I present solutions to two key sources of error in contact dynamics simulation: (a) the use of polyhedral description for smooth bodies and (b) the decoupling of collision detection and state evolution in dynamic simulation algorithms. I present an (interior point based) optimization algorithm to compute distances between convex implicit surface objects. This is the first polynomial time algorithm for distance computation between a class of non-polyhedral objects, for example, objects described as intersection of quadrics. I next present a time-stepping algorithm that combines the dynamic state evolution equations with collision detection by using the necessary and sufficient conditions for the optimization based formulation of distance computation problem. This is the first geometrically-implicit time-stepping algorithm. In the second part, I develop path planning algorithms for point set coverage by multiple robots subject to geometric constraints. This work applies directly to an industrial laser drilling system used in the electronic packaging industry. We model this problem as a $k-$Traveling Salesman Problem ($k-$TSP) with geometric constraints. The key distinguishing elements of our problem are (i) our data set consists of large number of points (of the order of $10^5$) and (ii) the robots have to spend some time at each point. I present a heuristic to solve this problem by posing the problem as two subproblems, namely, (a) a splitting problem on a graph for assigning the points to the robots (for $k = 2$, I give an optimal solution by transforming the problem to a maximum weighted matching problem) (b) a traveling salesman problem on the space of assigned pairs to specify the order of processing the points.
|
||||||||||||||||
Research
