Information Technology Reference
In-Depth Information
is a measure of the proximity, in terms of further state transitions, that a state (and
hence the cost that leads to that state) has to a solution. The cost is estimated in
terms of the number of intermediate states and the effort to reach each state. This
provides an estimate of the cost for a solution path. Each arc of the path represents
a transformation sequence involved in getting from one state to the next, and the
cost is derived from the nature of the transformation. This utility measure forms the
basis of a representation of the heuristic knowledge. The utility guides the inference
system by selecting a route that minimizes the cost.
The computer model of a general problem solver is expected to consist of three
elements that are related to different kinds of case knowledge:
•
a data representation that describes a set of problem states and has the potential
to describe all the problem states (the abstraction of the problem),
•
a set of data updates that describes how a given state can be transformed to a new
state (the deductive system),
•
a set of heuristics that provides guidance to a search algorithm through the problem
space (the heuristic knowledge).
These elements may be represented in a wide variety of forms depending upon
the knowledge representation scheme used (e.g. clauses, rules). Many AI programs
will have these three elements made explicit in their design even though they may
have been designed through a different theoretical framework (e.g. object oriented
programming, semantic nets, frames, case systems, etc.). Most of the alternative
current AI theories (of knowledge) are concerned primarily with representation.
The appeal of Newell and Simon's theory is that the states of the problem can be
represented as propositions. These propositions are formal representations of natural
sentences that are written thus:
All (x) Elephant (x) -
>
Colour (Grey, x)
[All elephants are grey]
Exists (y) Name (Dumbo, y) and Elephant (y)
[There is an elephant called Dumbo]
and the transformation from one state to the next is the application of deductive
inference to selected propositions. The deductive inference step is an extension of
Modus Ponens called Resolution. The only requirement is that the propositions must
be normalized into clauses, a process that can be done automatically. This process
is appealing because it demonstrates “human thinking” as proposed by logicians.
Further, it defines the start of an important research program into modeling human
cognition that has deep foundations in Mathematics and the formal traditions of
Science. The program can draw upon a long history of development that includes
work from many of the best thinkers of the last two millennia. This research program
has been pursued vigorously by many centers in the UK such as Imperial College
(London) and Edinburgh University.
