Ordered sorting of cluttered objects using multiple mobile manipulators

We present a search-based planning algorithm to sort objects in clutter using a multi-robot team. We consider the object rearrangement problem in which the objects must be sorted into different groups in a particular order. In clutter, the order constraints could not be easily satisfied since some objects occlude other objects. Those objects occluding others need to be moved more than once to make the occluded objects accessible. This nonmonotone class of the rearrangement prob- lem with order constraints becomes harder if multiple robots are involved, which practically mandates proper computations of robot allocations. The proposed method first finds a sequence of objects to be sorted using a search such that the order constraint in each group is satisfied. The search can solve nonmonotone instances that require temporal relocation of some objects to access the next object to be sorted. Once a complete sorting sequence is found, the objects in the sequence are assigned to multiple mobile manipulators using a greedy allocation method. We develop four versions of the method with different search strategies. In the experiments, we show that our method can find a sorting sequence quickly (e.g., 4.6 sec with 20 objects sorted into five groups) even though the solved instances include hard nonmonotone ones. The extensive tests and the experiments in simulation show the ability of the method to solve the real-world sorting problem using multiple mobile manipulators.