Object Rearrangement using Robotic Manipulators


Robot manipulators must be able to rearrange objects to operate effectively in cluttered human environments. For instance, multiple products may need to be orderly arranged in factory floors or grocery stores. A robotic assistant may need to rearrange objects when tidying up a home or rearrange objects in a fridge when retrieving a refreshment from a fridge, which is unreachable. This work has developed methods for efficiently solving hard instances of rearrangement through grasping using a single robotic arm.


Rearrangement is challenging because of the size of the corresponding configuration space (C-space) and the involved kinematic constraints. A complete method must operate in the Cartesian product of the robot's and the objects' C-spaces. The problem becomes harder when the objects are placed in tight spaces, such as shelves, where the arm has limited maneuverability. In these situations, a robot needs to carefully displace objects to reach previously unreachable items.

Rearrangement problems may be classified into monotone and non-monotone instances. For the monotone problems a solution exist by moving each object at most once. On the other hand, for non-monotone problems at least one object has to move to an intermediate pose before reaching its final pose.


Monotone Algorithm mRS

An existing algorithm by Mike Stilman (PhD Thesis, CMU 2007) performs a backtracking search in the space of possible orders of transferring objects directly to their final poses. This method is complete for monotone problems and in the worst case, the method needs to visit a complete search tree. Nevertheless, the method does not address the case where an intermediate position for an object is needed so as to solve the problem.


Non-Monotone Algorithm plRS

Our work has extended the above approach to the case that an object's path to its final pose is blocked. In many cases it is possible to easily evacuate the blocking objects. Specifically, the method employs a subroutine that searches for a monotone path to evacuate blocking objects so as to reach the blocked one. While the subroutine does not guarantee that it will always find a solution when one exists, it is complete for the table top cases under a sparsity requirement.


The method works using backtracking search, as a result will solve all the problems that the mRS algorithm can also find a solution. In order to find an intermediate pose, the proposed framework is making use of the Minimum Constraint Removal path notion. This notion is used to find a location for the object and a path for the manipulator that minimizes collisions with the other objects in the scene. It is not guaranteed, however, that it can solve all non-monotone challenges.

A Hierarchical, Graph-theoretic Approach

The next step in this direction is to provide a hierarchical scheme for searching the space of object arrangements and using the above primitives (either the monotone or the non-monotone solver) as a local planner for transitioning between different object arrangements. A top level algorithm searches the space of object arrangements by constructing a graphical representation, where nodes correspond to object arrangements and edges expresses which pairs of arrangements are reachable one from another using local rearrangement primitives. The algorithm keeps searching the space of object arrangements till the initial and the final arrangement are in the same connected component.

The overall scheme has been shown to be a probabilistically complete approach even if the local planner is a pick-and-place process. The benefit of using the monotone or non-monotone solver as local planners in the high-level graphical representation is that they can connect an individual arrangement to a relatively large number of different ones. This is an advantage over pick and place, which can only connect arrangements that differ only by a single object pose. Experimentally the efficiency of the approach improves when the local planner becomes more powerful.


Fast Primitive Extension

As the scale of problems increases, however, exhaustively searching for all possible orders within the rearrangement primitives can result in long solution times. There is a way, however, to approximate these solvers and avoid exhaustive backtracking search given the following observation: if the paths for transferring the objects are fixed, then one can easily compute the sequence of moving objects without collisions - if one exists. In particular, the sequence is the output of topological sorting on a "constraint graph". Such a graph is shown on the left figure below.


The nodes of the constraint graph correspond to the objects and an edge expresses the constraint that a blocking object needs to be moved before the target object in the execution sequence. For instance, an edge from A to B implies that given paths for rearranging these objects to their target locations, B has to be moved before A. In particular, constraints are defined in the following way:
* If the initial pose of the object o collides with the path for object o', then o has to move first,
* If the final pose of the object o collides with the path for object o', then o' has to move first.
If there is no cycle in the constraint graph, as in the left figure, i.e., if it is a Directed Acyclic Graph (DAG), then it is possible to compute an ordering of the nodes of the constraint graph, using topological sort. For that ordering, the computed paths can be used to solve the monotone problem without the need for search. The computed paths we use correspond to solutions to the Minimim Constraint Removal problem, since these paths introduce the minimum number of constraints.

If the constraint graph is not a DAG, however, then the problem is non-monotone and it is not possible to find an order to move all objects. When there are cycles, the algorithm tries to decouple them by moving objects to intermediate locations, which may resolve the cycle. If this is possible, then a sequence of transfer paths has been found. But in the context of a hierarchical scheme, it is also useful to get a partial solution to a rearrangement problem, where some of the objects are moved to their target locations and others are left in place (e.g., move all the objects in the constraint graph until a cycle is met).


Incremental Search Approach

Instead of the top-level planner in the hierarchical scheme building a graph, one can consider the use of incremental sampling-based tree planners, such as a Bi-directional RRT, which do not require the capability to exactly connect two states but only the capability to extend from one state. The above approximate primitives, which may give partial solutions, can then be used again as local planners in the context of a high-level RRT search of the space of object arrangements.

The high-level planner builds a bi-directional tree, where nodes correspond to object arrangements. The two trees start with the initial and final arrangements correspondingly as their only nodes. Edges correspond to local rearrangement paths that will be computed by a local rearrangement primitive. While the problem is not solved, the method samples a new random arrangement. In the spirit of the original Bi−RRT algorithm, it is not necessary to exactly connect the new sampled arrangement to a node already on the tree. Instead, it is sufficient if the method makes some progress away from tree nodes and a new partial solution is linked to the tree. This requires that the rearrangement primitives can return partial solutions where just some of the objects are moved, from the initial arrangement towards the final arrangement.


The methods have been tested in 3 workspaces with a model of a Baxter arm:
* RSS challenge
* Grid on a table top
* Grid in a shelf
The ''RSS challenge'' involves 6, 11 or 16 boxes placed on a tabletop. Initially the arrangement is random and the objective is to form the word RSS. The ''grid at tabletop'' benchmark places 4, 10 and 16 objects on a tabletop. The ''grid at shelf'' challenge has 2, 6 and 10 cylinders placed in a shelf that limits the arm's reachability and does not allow overhand grasps. In both cases, the objective is to rearrange the objects from a random to a grid arrangement. All the results are collected over the successful runs.

The first set of graphs shows the results from the runs with just using the rearrangement primitives in order to connect the initial to the final arrangement.


This set of graphs shows the results from the runs using as high-level task planner the graph search algorithm similar to PRM.



This challenge has 6 cylinders placed in a shelf that limits the arm’s reachability and does not allow overhand grasps. The objective is to rearrange the objects from a random to a grid arrangement.

In this video the robot manipulator has to rearrange the objects inside the shelf and bring the target object to the user. At the end all of the other objects have to be back in their initial positions.

This is a solution for the "toy" example of towers of Hanoi. The robotic arm will move the objects from the first bin to the second bin while maintaining the same order as in their initial arrangement.

This video shows the execution of a path on a real robot. The path is computed using the algorithms of this work. This is an open loop execution where the robot knows where all the objects are placed.

Related Publications

People Involved