RI: Small: Taming Combinatorial Challenges in Multi-Object Manipulation

Rutgers University New Brunswick, New Brunswick NJ

Investigators

Abstract

A key challenge in many autonomous robot manipulation applications is the rearrangement of multiple objects. There are two situations where such needs arise: (i) the manipulation task itself is to rearrange objects, and (ii) occluding items must be rearranged to allow the robot access to the target object(s). Examples of such scenarios can arise in warehouses and industrial setups, where a robot has to frequently select, pick and transfer products, packages and pallets in the presence of many other similar objects. Another example comes from service robotics, where a robotic assistant that operates in a human space has to frequently retrieve or rearrange multiple items placed in narrow spaces, such as objects in shelves. This project investigates which classes of multi-object manipulation planning can be efficiently addressed given progress in multi-body motion planning and develops a powerful suite of novel computational solutions. The key insight is that for many real-world rearrangement tasks the sequence of object motions to solve the problem, ignoring grasping aspects, look similar to solutions of multi-body motion planning, especially for similar sized objects. The study of this link reveals it is possible to cast certain multi-object manipulation problems as a "pebble motion problem on a graph", which is well studied in algorithmic theory and multi-body motion planning. The overall objective is to provide rigorous methods with desirable completeness and optimality guarantees for multi-object manipulation, which exhibit good scalability and efficiency for problems where current methods face issues with the inherent combinatorial complexity. Such methods could also be used as guiding heuristics for tasks with additional constraints, such as non-trivial dynamics and uncertainty.