Here's your practice assignment 4. I'll assume that, with the
logic programming expertise you've developed by working on your
term project, you'd have no difficulty at all finding the solution
to this problem, so you don't have to turn in a solution. But
you might want to give some consideration to how you might do
this...you never know what could appear on a final exam.
----------
Spike the warehouse robot spends his mundane existence shuttling
between four rooms in a warehouse, pushing boxes from one room to
another. Spike hasn't been blessed with an arm; he just literally
pushes boxes from one room to another. The current state of
Spike's world looks like this:
room1 room2 room3 room4
---------------------------------------------
| | | | |
| | | | |
| box1 box2 spike |
| |
| | | | |
| | | | |
---------------------------------------------
That is, room1 is adjacent to room2, room2 is adjacent to room3,
room3 is adjacent to room4, Spike is in room4, box1 is in
room2, and box2 is in room3.
Spike knows how to do two things. He can move from one room
to another, and he can push a given box from one room to another.
Those actions can be described in more detail as follows:
move_spike(Room1,Room2) has Spike the robot moving from
Room1 to Room2. The preconditions are that Spike has to be
in Room1, and Room1 has to be adjacent to Room2.
push_box(Box,Room1,Room2) has Spike pushing the box indicated
by Box from Room1 to Room2. The preconditions are that Spike has
to be in Room1, Box has to be in Room1, and Room1 has to be
adjacent to Room2.
Spike gets a command from his supervisor: Spike is to move
box1 from room2 to room3. Your job (which is far more
interesting than Spike's) is to modify the STRIPS-style planning
procedure given below so that it works in the domain of a robot,
some boxes, and some rooms instead of an arm, a table, and some blocks.
You'll want to change the blocks-world planner as little as
possible, but you will want to replace blocks-world actions with
warehouse actions. And of course you'll want to describe the
current state and goal state of the warehouse world, not the
blocks world. Chapter 8 will give you lots of ideas about what
must be changed.
Here's some sample output. Note that a small depth bound
keeps the planner from finding plans with cycles. You don't
have to worry about cycles (although you could if you really
want to). We'll keep the depth bound small, but a larger depth
bound could result in paths with cycles...for the purposes of
this homework assignment, that's ok, so long as the planner also
finds paths without cycles.
cilog: bound 10.
cilog: ask goals(G) & achieve_all(G,init,P).
Answer: goals([in_room(box1,room3)])
&achieve_all([in_room(box1, room3)], init,
do(push_box(box1, room2, room3),
do(move_spike(room3, room2),
do(move_spike(room4, room3), init)))).
Runtime since last report: 0 secs.
[ok,more,how,help]: more.
Answer: goals([in_room(box1, room3)])
&achieve_all([in_room(box1, room3)], init,
do(push_box(box1, room2, room3),
do(push_box(box2, room3, room2),
do(move_spike(room4, room3), init)))).
Runtime since last report: 0 secs.
[ok,more,how,help]: more.
Query failed due to depth-bound 10.
Runtime since last report: 0 secs.
[New-depth-bound,where,ok,help]: ok.
cilog:
Finally, here's the existing planner code that we talked
about in class. Enjoy:
/*
This is an implementation of the simple STRIPS planner
shown on page 302 of the Computational Intelligence text.
The domain is a very simple blocks world problem, and
the representations of state and actions, while described
in chapter 8 of the text, are adapted from a more
complicated sample program and knowledge base found at
http://www.cs.ubc.ca/spider/poole/ci/code/cilog/cilog_code/cilog_code.html
(click on delrob_strips.pl).
launch it with the query:
cilog: ask goals(G) & achieve_all(G,init,Plan).
Note that the add list is denoted here by "achieves" instead of "add",
and that the add and delete lists aren't exactly lists.
*/
/* stack action */
preconditions(stack(X,Y),[cleartop(Y),X\=Y,holding(X)]).
achieves(stack(X,Y),armempty).
achieves(stack(X,Y),on(X,Y)).
deletes(stack(X,Y),cleartop(Y)).
deletes(stack(X,Y),holding(X)).
/* unstack action */
preconditions(unstack(X,Y),[on(X,Y),cleartop(X),X\=Y],armempty).
achieves(unstack(X,Y),holding(X)).
achieves(unstack(X,Y),cleartop(Y)).
deletes(unstack(X,Y),on(X,Y)).
deletes(unstack(X,Y),armempty).
/* pickup action */
preconditions(pickup(X),[cleartop(X),ontable(X),armempty]).
achieves(pickup(X),holding(X)).
deletes(pickup(X),ontable(X)).
deletes(pickup(X),armempty).
/* putdown action */
preconditions(putdown(X),[holding(X)]).
achieves(putdown(X),ontable(X)).
achieves(putdown(X),armempty).
deletes(putdown(X),holding(X)).
/* initial situation */
holds(ontable(a),init).
holds(ontable(b),init).
holds(ontable(c),init).
holds(cleartop(a),init).
holds(cleartop(b),init).
holds(cleartop(c),init).
holds(armempty,init).
achieves(init,X) <- holds(X,init).
goals([on(b,c),on(a,b)]).
/* the more complex STRIPS planner */
remove(X,[X|Y],Y).
achieve_all([],W0,W0).
achieve_all(Goals,W0,W2) <-
remove(G,Goals,Rem_Gs) &
achieve(G,W0,W1) &
achieve_all(Rem_Gs,W1,W2).
achieve(G,W,W) <- true_in(G,W).
achieve(A \= B,W,W) <- A \= B.
achieve(G,W0,do(Action,W1)) <-
achieves(Action,G) &
preconditions(Action,Pre) &
achieve_all(Pre,W0,W1).
true_in(G,init) <-
holds(G,init).
true_in(G,do(A,_)) <-
achieves(A,G).
true_in(G,do(A,S)) <-
true_in(G,S) &
~ deletes(A,G).
Last revised: November 30, 2004