Path planning for pushing a disk using compliance

We consider the path planning problem for a robot that pushes a disk shaped object in an environment among obstacles. Instead of only allowing the object to move through the free space, we also allow the object to slide along the boundaries of the environment using compliance, extending the possibilities for the robot to find a push path. We present an exact algorithm that, given a path for the object consisting of k sections, preprocesses the environment consisting of n non-intersecting line segments in O(n/sup 2/ log n) and reports a push path in O(kn log n) time or reports failure if no path exists. Under the weak assumption of low obstacle density, the query time is reduced to O((k + n) log n).

I. Introduction

Manipulation refers to a wide variety of changes that can be applied to an object. One form of manipulation is moving objects. Objects can be moved in many different ways, roughly divided in two classes, prehensile (using a form or force closure grasp) and non-prehensile. Prehensile manipulation includes grasping (for an overview see the book of Mason [19]) and squeezing [13]. Non-prehensile manipulation [17] includes pushing, rotating the support surface [12], rolling [2] and even throwing [21]. Also more passive forms of manipulation can be used, for example placing fences along a conveyor belt [7].