Controlling Search with meta-Brave
P. Kefalas
and T.J.Reynolds
Abstract: We outline the Brave system:
a Horn-clause language Brave, a dialect of Prolog designed for OR-parallel
execution, plus meta-Brave, containing extra-logical features. Brave has
been stripped of Prolog’s cut, assert and retract, enforcing a declarative
programming style which enables easier parallelisation. However, we need
replacements for those predicates, in particular to code parallel versions
of search algorithms, where guidance of the search in one subtree requires
information from another subtree. Meta-Brave features directives which
allow algorithmic knowledge about the domain to be stated independently
from the Brave application program. This guidance is provided in three
main ways: partial results are selectively remembered (lemmas), conditions
of early failure of subproofs are stated (pruning), the style of search
is altered (strategies). We show how this combination of features makes
the Brave system specially suited to writing clear programs for example
search algorithms taken from Artificial Intelligence. In this paper we
investigate how OR-parallelism can be exploited in hill-climbing, genetic
algorithms and best-first search. By simulation we analyse the parallelism
obtained.
Keywords: Prolog, OR-parallelism, Meta-Control,
Search Algorithms
Appeared in: In Parallel Execution of Logic Programs, ICLP '91
Pre-Conference Workshop, Lecture Notes in Computer Science, vol.569, A.Beaumont
and G.Gupta (eds.), pp 29-38, Springer-Verlag, Paris, France, 1991
Available: Hardcopy on request from the authors. .
Back
to Dept. of Computer Science, CITY Liberal Studies
Back
to Petros Kefalas home page