v.Bijan@UCLA-LOCUS@sri-unix.UUCP (10/11/83)
From: Bijan Arbab <v.Bijan@UCLA-LOCUS>
Please see if you have a solution, hint, reference, interest
or etc. in the following two problems I am posting. The
description of the first problem is rather long so please
drag along (I am sorry for that).
First Problem:
1. on planning and the 'frame problem' In the book 'Logic For
Problem Solving' on p.133 Kowalski writes:
"... The use of logic, in both the n-ary and binary representations,
runs into the 'frame problem': how to deal with the fact that almost
all statements which hold true of a given state continue to hold
after an action has been preformed. It has aften been assumed that
such facts cannot be expressed naturally in logic and cannot be used
efficiently.
The supposed inadequacies of logic have led to the development of
special system, such as Strips and Planner. We shall argue that an
equally satisfactory treatment of the frame problem can be obtained
in logic: by using terms to name statements and by using the frame
axiom, which describes the statement which continue to hold after
an action has been preformed, top-down rather than bottom-up."
He then continues to explain; on pp 135 he gives the following
program:
Initial state 0
(1) poss(0)
(2) holds(on(a,b),0)
(3) holds(on(b,p),0) A
(4) holds(on(c,r),0) B C
(5) holds(clear(a),0) -------------
(6) holds(clear(q),0) p q r
(7) holds(clear(c),0)
State-Independent Assertions
(8) manip(a)
(9) manip(b)
(10) manip(c)
Goal State
(11) <- holds(on(a,b),W), holds(on(b,c),W), holds(on(c,r),W), poss(W).
State Space and Preconditions
(12) poss(result(trans(X,Y,Z),W) <- poss(W), manip(X), diff(X,Z),
holds(clear(X),W), holds(clear(Z),W),
holds(on(X,Y),W).
Added Statements
(13) holds(on(X,Z), result(trans(X,Y,Z),W))
(14) holds(clear(Y), result(trans(X,Y,Z),W))
Frame Axiom and Deleted Statements
(15) holds(U,result(trans(X,Y<Z),W)) <- holds(U,W), diff(U, on(X,Y)),
diff(U, clear(Z))
Then he claims that a if the clauses are executed top-down and if the
subgoals are considered breadth-first and left to right in the order
they are written we will get the following trace of the program:
<-holds(on(a,b),W), holds(on(b,c),W), holds(on(c,r),W),
poss(W)
13 |
15 | W=result(trans(a,Y,b),W1)
15 |
12 |
<-holds(on(b,c),W1), holds(on(c,r),W1), poss(W1), manip(a),
holds(clear(a),W1), holds(clear(b),W1), holds(on(a,Y),W1),
diff(a,b)
13 |
15 |
12 |
8 | W1= result(trans(a,Y1,c),W2)
15 |
15 |
15 |
<-holds(on(c,r),W2), poss(W2), manip(b), holds(clear(b),W2),
holds(clear(c),W2), holds(on(b,Y1),W2), diff(b,c),
holds(clear(a),W2), holds(on(a,y),W2)
15 |
12 |
9 |
14 | W2= result(trans(a,b,Y),W3)
15 |
15 |
15 |
13 |
<-holds(on(c,r),W3), poos(W3), manip(a), holds(clear(a),W3),
holds(clear(y),W3), holds(on(a,b),W3), diff(a,y),
holds(clear(c),W3), holds(on(b,Y1,W3)
4|
1|
8|
5| W3=0 Y=q Y1=p
6|
2|
7|
3|
The Question is, how did he get the substitution for:
W2= result(trans(a,b,Y),W3)
by applying only top-down reasoning ?
I have reproduced his program in Prolog and am not able to get
the same trace. The problem is that at the point where he is
getting the substitution for W2 my program, which is the above
program typed in Prolog, will start to reason bottom-up and
therefore finds a solution that is longer.
Second Problem
2. on breath first search and Prolog
Can you write a function in Prolog for
is-all(A,Y,Q) where
A is a list of all Y's such that query Q is solved. E.G. if
the world is like
p(a)
p(b)p
p(c)
and the goal is
is-all(A,Y,p(Y))
then the list a.b.c.nil should be bound to A. Is there a pure
Prolog definition for is-all? By pure Prolog I mean the use
of addaxiom and delaxiom is not allowed !
Note: in most Prologs an equivelent function is already built
-in. But is not defined in Prolog.
Thank for all your help,
-- Bijan