pop@lastresort.cs.umass.edu (06/11/90)
From: pop@cs.umass.edu ()
Path: cs.umass.edu!pop
Newsgroups: comp.lang.prolog
Subject: Planning and Purity
Expires:
References:
Sender:
Reply-To: pop@cs.umass.edu ()
Followup-To:
Distribution: world
Organization: University of Massachusetts, Amherst
Keywords: Planning in Prolog.
Many simple planning problems can be handled in Prolog using iterative
deepening. While real Prolog gurus will probably recommend some kind of
meta-interpreter or transformation system, for novices an easy
approach is to add an extra place to
every plan-specific predicate. This place is in integer D, for Depth. The
predicate fails for D=0. Thus you can conduct a search to a specified
depth. That way the original, purely logical, McCarthy-Hayes treatment of
"Situations, Actions and Causal Laws" can be run for modest examples, and
you don't have to use the horrible assert-retract kludges which emanated
from MIT some years later. You just call your top-level goal predicate
with increasing depths until it succeeds, or you run out of time. The time
complexity of this approach is no worse than breadth first search, and the
space complexity is much better.
The main problem about the McCarthy-Hayes approach is that n^2 frame
axioms are required if there are n situuation-dependent predicates. I
have been looking at the use of Boyer-Moore style reasoning about
simulation programs as a means of circumventing this problem whilst
preserving sanity.
:- current_op(P,A, =), op(P,yfx, then). /* Define then as an operator */
acceptable(D1,D2) :-
D1 > 0, D2 is D1-1.
/* The frame axiom - blocks not acted on stay put. */
on(A,B,S then puton(C,D),N1) :-
acceptable(N1,N2), /* Decrement and test count */
on(A,B,S,N2), /* was A on B before? */
diff_blk(A,C), /* are we picking up A? */
diff_blk(B,C), /* are we picking up B? */
diff_blk(B,D). /* are we trying to put C on B?*/
/* putting A on B means that A is on B. */
on(A,B, S then puton(A,B), N1) :-
acceptable(N1,N2),
cleartop(A,S,N2),
cleartop(B,S,N2).
/* if A is put on B then its top remains clear */
cleartop(A, S then puton(A,B), N1).
cleartop(A, S then puton(B,C), N1) :-
acceptable(N1,N2),
cleartop(A,S,N2),
diff_blk(A,C).
/* Now a predicate to recognise when two blocks are distinct.
NOTE we cannot replace diff_blk(A,B) by A \= B, since this does not
bind variables (and it does not have the correct Predicate Calculus semantics).
diff_blk, as defined below, is equivalent to a set of unit clauses saying
diff_blk(a,b) .....
*/
diff_blk(A,B) :-
block(A),
block(B),
A\=B.
it_deep(G,V,D,D_max) :-
D < D_max,
D1 is D+1,
(V = D, call(G) ; it_deep(G,D1,D_max)).
/* Now we describe a specific problem */
on(a,table,s0,N).
on(b,table,s0,N).
on(c,table,s0,N).
cleartop(a,s0,N).
cleartop(b,s0,N).
cleartop(c,s0,N).
block(a).
block(b).
block(c).
/*
:- spy it_deep.
:- spy on.
:- nospy on.
:- spy cleartop.
:- spy acceptable.
:- nospy acceptable.
:- on(a,b,S,3), on(b,c,S,3), print(S).
:- it_deep((on(a,b,S,N), on(b,c,S,N)),N,1,3), print(S).
s0 then puton(b, c) then puton(a, b)
:- S = ((s0 then puton(b,c)) then puton(a,b)),
on(a,b,S,2), on(b,c,S,2).
*/
Mc Carthy, J. and Hayes, P.J. [1969] Some Philosophical Problems from the
Standpoint of Artificial Intelligence, in Machine Intelligence 4 (eds Meltzer
B. and Michie, D), Edinburgh University Press.
Boyer,R.S., and Moore J.S. [1975] Proving Theorems about Lisp Functions
JACM 22(1), 129-75
Robin Popplestone.