Computing the configuration space for a convex robot on hypercube multiprocessors
Jing-Fu Jenq, Wing Ning Li · 2002
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.