  We present a method to apply heuristic search algorithms to solve
rearrangement planning by pushing problems. In these problems, a robot must
push an object through clutter to achieve a goal. To do this, we exploit the
fact that contact with objects in the environment is critical to goal
achievement. We dynamically generate goal-directed primitives that create and
maintain contact between robot and object at each state expansion during the
search. These primitives focus exploration toward critical areas of
state-space, providing tractability to the high-dimensional planning problem.
We demonstrate that the use of these primitives, combined with an informative
yet simple to compute heuristic, improves success rate when compared to a
planner that uses only primitives formed from discretizing the robot's action
space. In addition, we show our planner outperforms RRT-based approaches by
producing shorter paths faster. We demonstrate our algorithm both in simulation
and on a 7-DOF arm pushing objects on a table.
