Share Email Print

Optical Engineering

New algorithm for three-dimensional minimum cost path planning and its VLSI implementation by means of a three-dimensional cellular automata architecture
Author(s): Panagiotis G. Tzionas; Phillippos G. Tsalides; Adonios Thanailakis
Format Member Price Non-Member Price
PDF $20.00 $25.00

Paper 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.

Paper Details

Date Published: 1 November 1993
PDF: 12 pages
Opt. Eng. 32(11) doi: 10.1117/12.147721
Published in: Optical Engineering Volume 32, Issue 11
Show Author Affiliations
Panagiotis G. Tzionas, Democritus Univ. of Thrace (Greece)
Phillippos G. Tsalides, Democritus Univ. of Thrace (Greece)
Adonios Thanailakis, Democritus Univ. of Thrace (Greece)

© SPIE. Terms of Use
Back to Top