1 November 1993 New algorithm for three-dimensional minimum cost path planning and its VLSI implementation by means of a three-dimensional cellular automata architecture
Author Affiliations +
Optical Engineering, 32(11), (1993). doi:10.1117/12.147721
Abstract
A new algorithm for the estimation of the minimum cost path between a pair of points in the 3-D space and it's VLSI implementation by means of a new multistate conditional 3-D cellular automata (CA) architecture are presented. The proposed algorithm establishes the minimum cost path between the source and target points along the maximum allowable change of direction on the 3-D grid in the presence of obstacles. Lines at arbitrary angles on this grid are piecewise approximated with elementary line segments along the principle axes of the grid, as well as along the diagonals of the 3-D elementary Cartesian cube and along the diagonals of the faces of this cube. The proposed algorithm guarantees to find the minimum cost path in 3-D space, if such a path exists. The VLSI implementation presented is realized by mapping the 3-D CA architecture onto a 2-D chip surface, resulting in a very high speed of operation, while the storage requirements are kept low. The die dimensions for the chip are 9.57 x 9.47 mm = 90.59 mm2, and the frequency of operation under nominal operating conditions is 42 MHz. Thus, the chip is especially suitable for real-time 3-D applications, such as 3-D automated navigation, target tracking in 3-D, 3-D path planning, 3-D VLSI routing, etc.
Panagiotis G. Tzionas, Phillippos G. Tsalides, Adonios Thanailakis, "New algorithm for three-dimensional minimum cost path planning and its VLSI implementation by means of a three-dimensional cellular automata architecture," Optical Engineering 32(11), (1 November 1993). https://doi.org/10.1117/12.147721
JOURNAL ARTICLE
12 PAGES


SHARE
Back to Top