OR-Parallel Prolog and Search Problems in Artificial Intelligence

T.J.Reynolds and P. Kefalas 
This paper describes the language Brave, updating previous papers. Brave is a dialect of Prolog designed for all-solutions parallel execution. The language allows control of OR-parallelism by means of clause terminators and an if_ then_else construction. Language constructs allow collection of solutions into lists, as well as splitting lists to generate OR-parallelism. Brave does not possess a cut or the general power of assert and retract, instead a special database for partial results or lemmas is provided. Meta-directives under programmer control decide which results to lemma as well as controlling search by pruning on the basis of lemma information. We consider the application of Brave to search problems in Artificial Intelligence and demonstrate how the meta-control of Brave can be used to write parallel versions of well-known algorithms. Results are presented for the performance of parallel Branch-and-Bound and Alpha-Beta pruning using a multi-processor simulator.
 Keywords:  Prolog, OR-Parallelism, Memoisation, Branch & Bound, Alpha-Beta Pruning

Appeared in:  Proc. of the 7th Intern. Conf. in Logic Programming, D.H.D.Warren and P.Szeredi (eds.), pp 340-354, MIT Press, Jerusalem,Israel,1990

Available: Hardcopy on request from the authors. .

Back to Dept. of Computer Science, CITY Liberal Studies
Back to Petros Kefalas home page