Parallel computation of configuration space on reconfigurable mesh with faults

Abstract

A reconfigurable mesh (RMESH) can be used to compute robotic paths in the presence of obstacles, where the robot and obstacle images are represented and processed in mesh processors. For a non-point-like robot, we can compute the so-called "configuration space" to expand the obstacles, so that the robot can be reduced to a reference point to facilitate the robot's motion planning. In this paper, we present algorithms to compute the configuration space in a reconfigurable mesh that contains sparsely distributed faulty processors. Robots of rectangular and circular shapes are treated. It is seen that, in terms of computing the configuration space, a reconfigurable mesh can tolerate faulty processors without much extra cost-the computation takes the optimal O(1) time in both fault-free and faulty reconfigurable meshes.