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

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.