1 March 1991 Parallel message-passing architecture for path planning
Author Affiliations +
A prototype solving the Shortest Path Problem (SPP) by a parallel message-passing algorithm is presented. The system, an OCCAM program running on a transputer board hosted by a PC, implements a known distributed algorithm for the SPP, based on the 'diffused computation' paradigm. A new parallel message-passing architecture is proposed, built upon a static packet-switching network with a fractal topology. The recursive, unlimited network, features an interesting property when applied to four-link processors (like transputers): it's decomposable, at any hierarchical level, in four-link modules or supernodes. Labelling and routing algorithms for the network, exploiting self-similarity, are described. Experimental results, obtained with a single transputer solving irregular random graphs (up to 256 nodes) are presented, showing a time complexity function growing linearly with the total number of arcs.
© (1991) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Jose Tavora, Jose Tavora, Pedro Manuel Gon Lourtie, Pedro Manuel Gon Lourtie, "Parallel message-passing architecture for path planning", Proc. SPIE 1468, Applications of Artificial Intelligence IX, (1 March 1991); doi: 10.1117/12.45495; https://doi.org/10.1117/12.45495


Back to Top