Title: New algorithm for three-dimensional minimum cost path planning and its VLSI implementation by means of a three-dimensional cellular automata architecture
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<sup>2</sup>, 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.
Publication Year: 1993
Publication Date: 1993-01-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 2
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot