Share Email Print
cover

Proceedings Paper

Parallel message-passing architecture for path planning
Author(s): Jose Tavora; Pedro Manuel Gon Lourtie
Format Member Price Non-Member Price
PDF $14.40 $18.00

Paper Abstract

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.

Paper Details

Date Published: 1 March 1991
PDF: 12 pages
Proc. SPIE 1468, Applications of Artificial Intelligence IX, (1 March 1991); doi: 10.1117/12.45495
Show Author Affiliations
Jose Tavora, Instituto Superior de Economia e Gestao (Portugal)
Pedro Manuel Gon Lourtie, Instituto Superior Tecnico (Portugal)


Published in SPIE Proceedings Vol. 1468:
Applications of Artificial Intelligence IX
Mohan M. Trivedi, Editor(s)

© SPIE. Terms of Use
Back to Top