A massively parallel architecture design for path planning applications
Lyle Amos Reibling · Michigan State University Libraries · 1992
This research has investigated computer system design issues for massively parallel architectures applied to path planning in two-dimensional risk fields. Physical phenomena were found to be useful in modeling shortest path planning problems. These phenomena provide analogies in nature which form the basis for the models in path planning. The electrostatic model in field theory describes the distribution of current flow through a nonuniform conducting media, such as a plate of nonhomogeneous resistive material. The paths of current flow are used as the analogy in nature to path planning by associating the resistivity of the media with the cost function of the path planning problem. The distribution of current flow for electrostatic fields is described by the Laplacian partial differential equation. An artificial neural network was designed to solve the Laplacian equation for nonhomogeneous media and was used in a massively parallel architecture to compute minimal cost and alternative paths. The scalar field for the nonhomogeneous media is found by computing a finite difference approximation to the partial differential equation. The artificial neural network computes this field. Path solutions are computed from a vector field which is orthogonal to equipotential contours of the scalar field. Connectivity of the massively parallel architecture was examined for its influence on the convergence rate of the neural network approximation. Experimental investigation of this technique has shown promising results. The solutions generated by the architectures have been checked against known admissible algorithm results. A simulation of an analog implementation of the artificial neural network with 3,600 neurons resulted in projected real-time convergence of 18 milliseconds. A significant result of this research was the discovery of an architecture design paradigm for massively parallel architectures. This paradigm is called natural parallelism.