The window corner algorithm for robot path planning with translations

Abstract

The feasible path problem is solved for planning a collision-free path to translate an arbitrary polyhedral robot from an initial position to some goal position in a polyhedral environment. The shortest path problem entails finding the shortest feasible path. The authors present two versions of the window corner (WC) algorithm, which is a novel solution to the problems for the case of single and multistep translational paths for two dimensions, and then summarize the extension to the three-dimensional WC algorithm, for feasible paths. The concept of window corners in the polyhedral cone representation (PCR) is introduced, which reduces the search space. The PCR cones store constraints between boundary elements. The PCO representation has O(m) vertices compared to O(m/sup 2/) in a C-space representation. The WC algorithm was tested and an example from assembly path planning is presented.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>