Computing the configuration space for a convex robot on hypercube multiprocessors

Abstract

Computing the configuration space obstacles is an important problem in spatial planning for robotics applications. In this paper we present a parallel algorithm for computing the configuration space obstacles by using hypercube multiprocessors. The digitized images of the obstacles and the robot are stored in an N/spl times/N image plane. An algorithm for handling robots whose shapes are arbitrary convex polygons was presented. Our algorithms take O(logN) time and O(I) space which is asymptotically optimal for hypercube computers.