New algorithms for multilink robot arms

摘要

Problems related to the movement of n-link robot arms in two dimensions are considered. We present an algorithm, requiring O(n) computation time, which moves an arm confined in a circular region to any reachable configuration in O(n) moves. Also given is an O(n) computation time algorithm that computes all the regions reachable by the joints of such an arm. These results are improvements over the cubic algorithms of Hopcroft, Joseph, and Whitesides (SIAM J. Comput.14, No. 2 (1985)). We finally show how to plan motion involving the minimum number of moves for an arm in the obstacle-free plane in O(n3) computational steps.