Title :
Parallel Branch-and-Bound Formulations for AND/OR Tree Search
Author :
Kumar, Vipin ; Kanal, Laveen N.
Author_Institution :
Department of Computer Sciences, University of Texas at Austin, Austin, TX 78712.
Abstract :
This paper discusses two general schemes for performing branch-and-bound (B&B) search in parallel. These schemes are applicable in principle to most of the problems which can be solved by B&B. The schemes are implemented for SSS*, a versatile algorithm having applications in game tree search, structural pattern analysis, and AND/OR graph search. The performance of parallel SSS* is studied in the context of AND/OR tree and game tree search. The paper concludes with comments on potential applications of these parallel implementations of SSS* in structural pattern analysis and game playing.
Keywords :
Artificial intelligence; Context modeling; Laboratories; Minimax techniques; Neodymium; Operations research; Parallel algorithms; Pattern analysis; State-space methods; Tree graphs; AND/OR graphs; branch-and-bound; game trees; minimax search; parallel algorithms;
Journal_Title :
Pattern Analysis and Machine Intelligence, IEEE Transactions on
DOI :
10.1109/TPAMI.1984.4767600
