Introduction -
Assignment 0 Discussion
| Pretend
that the picture below actually depicts a situation in the real
world. We would like to represent the information in this world
in such a way that it will provide the basis for reasoning about
how to solve the three-disk Tower of Hanoi problem. |
 |
First,
a rather "neutral" description of the facts depicted
above:
|
Three vertical gray pegs
of equal length and equally spaced on a
horizontal gray rod.
Three disks of varying size and color
all on the left-most peg where:
the smallest is green and rests
on top of the next smallest disk;
the next smallest is blue and rests
on top of the largest disk;
the largest disk is red and rests
on the horizontal rod
The background is black.
The goal situation which is not depicted is identical
to the above description except that the three disks rest on
the right-most peg.
|
|
|
You
will notice that some of the descriptions above are displayed
in red. These are aspects of domain which remain constant and
will play no role in reasoning about how to solve the Tower of
Hanoi Problem. You will probably find that you left this information
out without even giving it a thought.which of course is a clever
thing to do.
Next,
a more careful description of the domain which will help us see
how to express these facts in FOL:
A
set of pegs {p1, p2, p3}
A set of disks {d1, d2, d3}
A function: pegof(di)
Unary Relation Names: {DISK, PEG}
Binary Relation Names: {ON, ABOVE, <, NE}
A Binary Relation: ON(di,pj)
A binary relation: ABOVE(di, dj)
A binary relation: <(di,dj)
A binary relation: NE(xi,xj) |
|
And
with these we can restate the above as:
PEG(p1)
& PEG(p2) & PEG(p3) &
DISK(d1) & DISK(d2) & DISK(d3) &
NE(p1, p2) & NE(p1, p3) & NE(p2, p3) &
NE(d1, d2) & NE(d1, d3) & NE(d2, d3) &
ON(d3, p1) & ON(d2, p1) & ON(d1, p1) &
ABOVE(d1, d2) & ABOVE(d2, d3) &
<(d1, d2) & <(d1, d3) & <(d2, d3) |
|
But
for purposes of reasoning about the domain several rules that
are not part of the "facts" need to be stated:
NE(x1,
x2) Æ
NE(x2, x1) the
relation NE is symmetric
<(di, dj) <(dj, dk) Æ <(di, dk) the
relation < is transitive
ON(di,pj) & ABOVE(di, dk) Æ <(di, dk) this is a "law"
of this world |
|
And, in order
to state the rules for moving the disks from peg to peg it may
be useful to state some "functional" relations, such
as:
FREE(p,
di) := "(d)
[ON(d,p) Æ
<(di,d)] Peg p is free to accept disk di
EMPTY(p) := ÿ$(d) ON(d,p) There
are no disks on Peg p.
TOP(di,pj) := ÿ$(d) ON(d,p) & <(d,di) di
is the top disk on Peg pj. |
|
|
Now,
we need to state the rule(s) for moving a disk from one peg to
another. In English the rule can be stated as:
If a diski is the top disk
of the peg it is currently on then it can be moved to a peg that
is either empty or whose top disk is larger than diski.
That was relatively painless
but how do we state this in FOL???.not so painlessly it turns
out!!
TOP(di,pj) & FREE(pk, di)
& NE(pj, pk)
seems to express the condition that must hold for a particular
disk to be moved from Pegj to Pegk;
and
ÿ ON(di,pj)
& ON(di,pk)
seems to express at least some of the consequences of carrying
out the action
but how do we represent actions,
or the new situation that results from the action?
|
|
Well
the key is to note that I used the term situation above. A move
takes us from one situation to another but we didn't introduce
this idea into our language. Chapter 3 of your text provides
about as simple an explanation as you will find about how to
do this in the situation calculus but we will defer that
until later. That solution commits us to a linear time logic,
frame axioms, and the like....who said exploring intelligence
at the knowledge level was easy?
And, we haven't even considered
your knowledge about the problem solution. For example, the smallest
disk must be moved on every other move if the solution is to
be optimal and free of cycles. And, by the way, avoid cycles..How
is this knowledge about this class of problem to be expressed?
Finally,
there is the issue of the actual terms used to describe the problem.
Why talk about Pegs, but aren't they just locations? Why refer
to disks?...aren't they just a set of objects that are linearly
ordered? And, why restrict the number of pegs (locations) to
three but allow the number disks (ordered objects) to be unlimited?
These questions are crucially relevant to questions of transfer.
|
|
And,
one more important caveat. Here we have focused on trying to
represent the knowledge about this problem in the syntax of first
order logic. This is because it is a well-understood tool for
use in this way and there is a well-defined proof procedure associated
with this language. Additionally, there is a well-developed computational
language (Prolog) which can treat FOL statements (restricted
to a form referred to as Horn clauses) as a data structure. BUT,
there are many interesting ways in which to express the knowledge
about this problem. One particularly compact way is to represent
a state as a string of letters drawn from the alphabet {L,M,
R}. We interpret these letters as referring to the left, middle,
and right pegs. Then, we employ a string of these letters where
the length of the string is equal to the number of disks involved
in a particular problem. Each element of the string then corresponds
to a disk and we interpret the left to right order of the string
as a representation of the size of the disk. Thus, the first
element in the string represents the largest disk, the second
element represents the next largest disk, etc.
Thus,
our picture above is represented in this language as LLL; that
is, the largest disk, the next largest disk and the smallest
disk are all on the left peg. If the smallest disk were moved
to the right peg then the resulting situation would be represented
as LLR and so on. Note this is a very compact representation
and it might allow us to write a simpler program for solving
the Tower of Hanoi problem then if we try to solve it using the
FOL representation. But of course, this representation is much
less general than the language of FOL.
One
of the things that we will be quite interested in is whether
we can determine the human's choice of representation language;
whether this representation changes with experience, etc. Recall
that the expert chess player seems to represent the configuration
of pieces on a chess board quite differently from the novice.
And, if you have ever looked at an x-ray you know that the radiologist
often sees things that aren't at all apparent to the novices'
examination of the same image.
|
|
|
