Text

theses

Rearranging multiple objects is a critical skill for robots so that they can effectively deal with clutter in human spaces. This is a challenging problem as it involves combinatorially large, continuous C-spaces involving multiple movable bodies and complex kinematic constraints. This work aims to identify ways of decomposing such problems into a hierarchy of challenges that can be addressed effectively individually, while their composition can provide a solution to the overall instance. The first direction for such a hierarchical decomposition aims to take advantage of developments in the multi-robot community, where there are efficient solvers for the “pebble motion on a graph” problem. Unlabeled rearrangement problems with a robotic manipulator are decomposed into a sequence of subproblems, each one of which can be viewed as a “pebble motion on a graph” problem. The labeled case, however, is not easily decomposed to a “pebble motion on a graph” problem instances. To deal with general object rearrangement, including both the labeled and the unlabeled case, this work builds on top of prior work that was able to compute solutions for labeled monotone instances through a backtracking search process. Monotone instances are those where every object needs to be transferred at most once to achieve a desired arrangement. This thesis extends the backtracking process to a method that addresses many non-monotone challenges. In order to solve the non-monotone cases the method is using solutions to the Minimum Constraint Removal (MCR) path problem so as to transfer each object to its target. An MCR path minimizes the number of constraints that need to be removed from the path of an object. This work then utilizes the monotone or the non-monotone backtracking search process as local connection primitives in the context of a higher-level task planner, which operates similar to a Probabilistic Roadmap Method (PRM), that searches the space of object placements. It is shown that the integration of these primitives with the higher-level planner achieves probabilistic completeness guarantees for the general object rearrangement problems. To improve the efficiency of the above hierarchical framework, this work introduces approximate but significantly faster primitives for monotone and non-monotone rearrangement instances. The methods avoid backtracking search by building a dependency graph between objects given solutions to the Minimum Constraint Removal (MCR) path planning problem to transfer each object to its target. From this graph, the approach discovers the order of moving objects by performing topological sorting. These new approximate but fast primitives that do not need backtracking search are incorporated in a higher-level incremental search algorithm for general rearrangement planning, which operates similar to a Bi-directional Rapidly-exploring Random Tree (Bi-RRT). Given a start and a goal object arrangement, tree structures of reachable new arrangements are generated by using the new and fast approximate primitives as an expansion procedure. These methods have been evaluated in simulation using models of robotics manipulators, such as a Baxter or a Motoman robot arm, in order to study their capability in solving difficult instances of rearrangement problems. This work compares the different alternatives in terms of success ratio, running time, scalability and path quality. Overall, this work aims to emphasize the benefit of using more powerful primitives, which are reasoning about the combinatorial and the underlying multi-object nature of the rearrangement problem, in the context of high-level task planning for robotic manipulation.

ETD_8520

Ph.D.

Includes bibliographical references

by Athanasios Krontiris

doi:10.7282/T3MG7SMR

ETD doctoral

The author owns the copyright to this work.