Multirobot Pushing—How Many Robots are Sufficient?

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.