Optimal hypercube algorithms for robot configuration space computation
Jing-Fu Fu Jeng, Wing Ning Li · 1995
Computing the conjguration space is an importm problem in spatial planning for robotics applicatiorxIn this paper, we present parallel algorithms for computing the configuration space by using hypercube multiprocessors.The digitized images of the obstacies and the robot are stored in an Nx N image plane.In this paper, we develop optimal hypercube algorithms to compute the configuration space for circle and rectangle shaped robots.We also develop several new basic hypercube operations.The time compkxity of all the algorithnu is 0 (1ogN) and k asymptotically optimal for hypercube computers.The space complexity of each processor is 0 (1) which is again optimal.