TR-140: Computing the Configuration Space of a Robot on a Mesh-of-Processors
ÐÓ°ÉÔ´´ University
Technical Report TR-140
June 1988
Computing the Configuration Space of a Robot on a Mesh-of-Processors
Frank Dehne, A.-L. Hassenklover, Jörg-Rüdiger Sack
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.