TR-140: Computing the Configuration Space of a Robot on a Mesh-of-Processors

Abstract

In this paper, we present a systolic algorithm for computing the configuration space of an arrangement of arbitrary obstacles in the plane for a rectilinearly convex robot. The obstacles and the robot are assumed to be represented in digitized form by a ✓ x ✓ binary image. The algorithm is designed for a Mesh-of-Processors architecture with n processors (using the canonical representation of an image on a processor array) and has an execution time of O() which is asymptotically optimal.