A fast path planning algorithm for piano mover's problem on raster

Abstract

This article presents the near-optimal path-planning algorithm for piano mover's problem of robot motion among obstacles on raster. Beginning with a top view of a workspace arrangement among obstacles, the so-called free workspace is first obtained by virtually expanding the obstacles. The proposed method adopts virtual obstacle domain and collision avoidance scheme based on the higher geometry maze routing algorithm with all the possible directions to find the near-optimal path from the source position to the destination position. The time complexity of this method is O(RradicN) in average or O(RN) for the worst case, where N and R are the numbers of cells in the free workspace and the detection circle with the radius of VR <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> as its collision-detection domain, respectively, R<N. The obtained path is the near-optimal path, which some cells can be revisited as the piano mover's problem, with no collisions between the robot and the obstacles