To push or not to push: on the rearrangement of movable objects by a mobile robot

We formulate and address the problem of planning a pushing manipulation by a mobile robot which tries to rearrange several movable objects in its work space. We present an algorithm which, when given a set of goal configurations, plans a pushing path to the "cheapest" goal or announces that no such path exists. Our method provides detailed manipulation plans, including any intermediate motion of the pusher while changing contact configuration with the pushed movables. Given a pushing problem, a pushing path is found using a two-phase procedure: a context sensitive back propagation of a cost function which maps the configuration space, and a gradient descent phase which builds the pushing path. Both phases are based on a dynamic neighborhood filter which constrains each step to consider only admissible neighboring configurations. This admissibility mechanism provides a primary tool for expressing the special characteristics of the pushing manipulation. It also allows for a full integration of any geometrical constraints imposed by the pushing robot, the pushed movables and the environment. We prove optimality and completeness of our algorithm and give some experimental results in different scenarios.