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). 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.