PRASAD@RED.RUTGERS.EDU (03/14/86)
Exploration, Search and Discovery
By:
Michael Sims (MSims@Rutgers.Arpa)
Departments of Mathematics and Computer Science
Rutgers University
March 18, 1986, Tuesday, 11 AM
Hill Center #423
Abstract
Search has shown immense utility as a theoretical description of what
our computer programs do. We would like to apply the same descriptive
methods to describing discovery systems, such as Eurisko, Bacon, or
the speaker's IL (named for Imre Lakatos) system. Some investigations
by discovery systems are of a sufficiently distinct character, that it
has proved useful to create a new classification for them, called
Exploration.
To form the appropriate distinctions we begin by giving a definition of
what Newell and Simon called Physical Symbol Systems in their Turing
Award Lecture. We then describe two subclasses of Physical Symbol
Systems: 'Search' and 'Exploration'. Search roughly corresponds to what
is most frequently meant by the term, and contains an explicit test for
a solution structure. Exploration on the other hand has no explicit
termination condition, and hence does not value the elements of the
exploration space in terms of a solution structure.
Discovery may be done by either exploration or search. Eurisko and IL
do exploration at the top level, although many of their subtasks are
accomplished via searches. On the other hand, Bacon and IL-BP, an
explanation based learning component of IL, do discovery by doing
search.
Although many problems can be implemented as either search or
exploration, some problem are more naturally, or efficiently
implemented as one or the other. This new classification leads to an
evaluation of the relative efficiencies, the appropriateness
of introducing randomness, and the different roles played by the
search and the exploration evaluation functions.
-------