Path Planning for Pushing a Disk using Compliance
Dennis Nieuwenhuisen, A. Frank van der Stappen, Mark H. Overmars
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(n2 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).
Download this deliverable.