Brave: An OR-parallel Logic Language and its Application
to Search Problems in Artificial Intelligence
P. Kefalas
Abstract: 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