Efficiently Solving General Rearrangement Tasks: A Fast Extension Primitive for an Incremental Sampling-based Planner

TitleEfficiently Solving General Rearrangement Tasks: A Fast Extension Primitive for an Incremental Sampling-based Planner
Publication TypeConference Paper
Year of Publication2016
AuthorsKrontiris, A, Bekris, KE
Conference NameInternational Conference on Robotics and Automation (ICRA)
Date Published05/2016
Conference LocationStockholm, Sweden

Manipulating movable obstacles is a hard problem that involves searching high-dimensional configuration spaces. A milestone method for this problem by Stilman et al. was able to compute solutions for monotone instances. These are problems where every object needs to be transferred at most once to achieve a desired arrangement of all objects. The method uses backtracking search to find the order with which objects should be moved in the environment. This paper first proposes an approximate but significantly faster alternative for monotone rearrangement instances. The method defines a dependency graph between objects given the minimum constraint removal paths (Minimum Constraint Removal) to transfer each object to its target. From this graph it is possible to discover the order of moving the objects by performing topological sorting without the need for backtracking search. The approximation arises from the limitation to consider only the Minimum Constraint Removal paths for moving the objects. Such paths, however, minimize the number of conflicts between the objects. To solve non-monotone instances, this primitive is incorporated in a higher-level incremental search algorithm for general rearrangement planning, that operates similar to Bi-RRT. Given a start and a goal arrangement of objects, tree structures of reachable new arrangements are generated by using the primitive as an expansion procedure. The integrated solution achieves probabilistic completeness for the general non-monotone case and based on simulated experiments it achieves very good success ratios, solution times and path quality relative to all the alternatives considered.