Wang, Rui. Complete and efficient prehensile rearrangement in confined spaces under kinematic constraints. Retrieved from https://doi.org/doi:10.7282/t3-s0xy-9k10
DescriptionThis thesis aims to provide complete, efficient, and high-quality solutions for task and motion planning problems in the area of robot manipulation with multiple objects. Specifically, the majority of the thesis focuses on a particular problem - robotic prehensile rearrangement in confined spaces under kinematic constraints, which has broad applications such as aligning objects in the grocery shelves. It is a challenging setup as no top-down grasps are available for approaching the objects. As a result, kinematic constraints such as robot-to-object and object-to-object constraints dominate the feasibility of the problems. It calls the need to develop intelligent sequential decision-making algorithms to produce a high-quality sequence of robot motions to successfully complete rearrangement tasks without collisions. Motivated by this domain, this thesis advances the capability of algorithms that result in a high-quality sequence of robot motions, which allows to successfully complete rearrangement tasks in confined spaces without undesirable collisions.Specifically, this thesis introduces efficient monotone solvers for solving monotone problems, i.e., those that can be solved by moving each object at most once, by significantly pruning the search space of possible solutions. It first provides a dynamic programming solution which reduces the search space from O(n!) to O(2^n) (n refers to the total number of objects). Based on that, it further introduces pruning of the search space by incorporating reachability constraints from grasping configurations for objects. Then it utilizes a lazy evaluation at the task planning level to reduce the total number of expensive motion planning queries and collision checking calls. In this process, it sidesteps expensive computational operations, while maintaining desirable completeness guarantees. This thesis progresses in incorporating the proposed monotone solvers to develop probabilistic complete non-monotone solvers, which are capable of solving harder instances quickly with fewer buffer locations, i.e., intermediate placements for objects needed during the rearrangement process. It first introduces a structure that alternates the monotone calls and the actions of moving objects to buffers (called perturbations), which returns solutions with fewer object transfers. Based on that, it utilizes the lazy evaluation framework to load partial solutions more efficiently from monotone solvers to achieve additional efficiency improvement. This work also provides improved motion planning primitives for rearrangement to speed up online motion planning resolution. The combination of these algorithmic improvements allow for increased feasibility, efficiency and quality of solutions. Finally, this work demonstrates the applicability of the proposed methods via a proof-of-concept real robotic rearrangement system, which integrates visual input and the developed task and motion planning methods.