/Multirobot Pushing — How Many Robots are Sufficient?

Multirobot Pushing — How Many Robots are Sufficient?

Laura Lindzey, Howie Choset, Siddhartha Srinivasa and Ross Alan Knepper
Tech. Report, CMU-RI-TR-12-15, Robotics Institute, Carnegie Mellon University, May, 2012

Download Publication (PDF)

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. These works may not be reposted without the explicit permission of the copyright holder.


This paper asks how many cooperating homogeneous robots are required to perform a block pushing task in a known environment. This task is particularly challenging in the presence of a highly cluttered obstacle field where the connectivity of the robots’ free configuration space depends on the block’s configuration. In order to simplify the problem, we define an equivalence relation over block configurations based on the connectivity of the robots’ free configuration space. We build a data structure that captures the relationships among the resulting equivalence classes, and then we encode constraints into the data structure that must be satisfied for the robots to be able to push the block between equivalence classes. We present an algorithm that operates on this data structure and uses existing optimization techniques to solve several variants of the minimum sufficient robots problem. Next, we give an implementation of this algorithm for an environment consisting of axis-aligned rectangles. Additionally, we provide a complete planner that finds a feasible path for the block in this environment.

BibTeX Reference
author = {Laura Lindzey and Howie Choset and Siddhartha Srinivasa and Ross Alan Knepper},
title = {Multirobot Pushing — How Many Robots are Sufficient?},
year = {2012},
month = {May},
institution = {Carnegie Mellon University},
address = {Pittsburgh, PA},
number = {CMU-RI-TR-12-15},