Parallel computation of configuration space on reconfigurable mesh with faults

The reconfigurable mesh (RMESH) can be used to compute robotic paths in presence of obstacles, in which 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 configuration space in a reconfigurable mesh that contains sparsely distributed faulty processors. The robots of rectangular and circular shapes are treated. It will be seen that in terms of computing configuration space, reconfigurable mesh can tolerate faulty processors without much extra cost - the computation takes the optimal 0(1) time in both fault-free and faulty reconfigurable meshes.