Brave: An OR-parallel Logic Language and its Application to Search Problems in Artificial Intelligence

P. Kefalas 
This thesis presents extensions to the language Brave, an OR-Parallel dialect of Prolog, to enable coding of Artificial Intelligence algorithms. The upgrated language, Brave89, consists of two parts: Brave, which performs an all-solutions OR-Parallel search and Meta-Brave, which establishes control over the search. Brave features a conditional construction and a single solution predicate. Higher order predicates are also introduced in order to facilitate expansion and collection of lists. Two types of clause terminators are employed to direct sequential an parallel exploration of OR-choices. They are otherwise semantically transparent, only affecting the order in which solutions are produced. Meta-Brave takes the form of directives. Independent subproofs may learn form each other's results by means of a special database which contains selectively published information in the form of lemmas. A lemma directive says which results should be lemmaed. A prune directive allows subproofs to be failed on the basis of lemmaed information. Another directive may alter the proof strategy to other than the default multiple depth-first.

The performance of Brave89 is evaluated using two simulators: one written in Prolog, one in C. These implement the Brave89 non-deterministic rewrite machine. A practical tool is developed to display the behaviour of OR-Parallel execution. The requirements of AI programs are analysed and a number of algorithms coded, showing how the various language features are utilised. Running the programs on the simulators shows that there is a good scope for OR-parallelism. The langauge features chose for Brave89 are also shown to be sufficient to re-express many successful AI algorithms in a new parallel paradigm.
Keywords:  OR-Parallel Prolog, Lemmas, Meta-Control of Proof, Parallel AI Algorithms, Parallel Search, Hill-Climbing, Genetaic Algorithms, Branch & Bound, Alpha-Beta Pruning, Best-First Search.

PhD Thesis, University of Essex, 1992

Available: Hardcopy on request from the author.

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