A Massively Parallel Heuristic Search Algorithm

Abstract

Heuristic search is an important technique in artificial intelligence. The best-first branch-and-bound ( ) algorithm is not only the most general search algorithm, but also one of a few general algorithms which can be used to solve a wide range of nondeterministic polynomial (NP)-hard processors. The algorithm can be parallelized by using a loosely-coupled network of processors. In this distributed algorithm, each processor maintains a local OPEN list and processes it implementation. the processors are required to exchange nodes of their local OPEN lists. One of the effective methods of exchanging information between processors i s b y u s i n g a B L A C K B O A R D . H o w e v e r , t h e BLACKBOARD requires shared memory. In this paper, we present a distributed algorithm using Binary Multi-Level Multi-Access (BMLMA) communication protocol. The communication network of BMLMA provides the global sorting of messages as a by-product of the protocol. Logically, this is analogous to a global associative memory: thus, it can be used to implement a l o g i c a l a s s o c i a t i v e B L A C K B O A R D . C o m p u t e r simulation using a traveling salesman problem has confirmed the linear scalability of proposed algorithm. Keywords : branch and bound, parallel search, multi- access protocol, linear scalability

View PDF