This paper presents a new parallel algorithm for collision-free path planning of a diamond-shaped robot among arbitrarily shaped obstacles, which are represented as a discrete image, and its implementation in VLSI. The proposed algorithm is based on a retraction of free space onto the Voronoi diagram, which is constructed through the time evolution of cellular automata, after an initial phase during which the boundaries of obstacles are identified and coded with respect to their orientation. The proposed algorithm is both space and time efficient, since it does not require the modeling of objects or distance and intersection calculations. Additionally, the proposed twodimensional multistate cellular automaton architecture achieves high frequency of operation and it is particularly suited for VLSI implementation due to its inherent parallelism, structural locality, regularity, and modularity.

A new, parallel, nearest-neighbor (NN) pattern classifier, based on a 2D Cellular Automaton (CA) architecture, is presented in this paper. The proposed classifier is both time and space efficient, when compared with already existing NN classifiers, since it does not require complex distance calculations and ordering of distances, and storage requirements are kept minimal since each cell stores information only about its nearest neighborhood. The proposed classifier produces piece-wise linear discriminant curves between clusters of points of complex shape (nonlinearly separable) using the computational geometry concept known as the Voronoi diagram, which is established through CA evolution. These curves are established during an "off-line" operation and, thus, the subsequent classification of unknown patterns is achieved very fast. The VLSI design and implementation of a nearest neighborhood processor of the proposed 2D CA architecture is also presented in this paper.>