New algorithm for three-dimensional minimum cost path planning and its VLSI implementation by means of a three-dimensional cellular automata architecture

Panagiotis G. Tzionas; Phillippos G. Tsalides; Adonios Thanailakis

doi:10.1117/12.147721

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

Panagiotis G. Tzionas, Phillippos G. Tsalides, Adonios Thanailakis

Author Affiliations +

Optical Engineering, Vol. 32, Issue 11, (November 1993). https://doi.org/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 mm², 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.

Citation Download Citation

Panagiotis G. Tzionas, Phillippos G. Tsalides, and 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

Published: 1 November 1993

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

;

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE