🔒 Locked

Prolog - Blocks World

Started by VisualFX Mar 21, 2005 at 4:24 AM 8 replies 9.3k views

Original Post

Mar 21, 2005 at 4:24 AM

Hi, I'm wanting to develop a little game in Prolog, the Blocks World. I believe the correct term for this is a planning system which will take an initial state and a goal state and generate a plan to move the blocks so that they are in the goal state. I don't know if you know this game, it's the one with N blocks on a table, in which only blocks not having any block above them can move to above others or to the table itself. I heard about the term STRIPS, but don't know what that means. Besides, how am I supposed to move the blocks (take an action)and consequently change the status of my lists if Prolog doesn't permit variable assignments? Do I have to make this recursively? Probably yes.. since I'm using lists.. - Could anybody throw me something that may ring a bell in my head? Thanks a lot VisualFX

lucky_monkey

Mar 21, 2005 at 9:19 PM

Don't worry too much about STRIPS, it's just a way of writing possible actions, close to the way I did it in the other thread...

You problem at heart is that you have an initial world state, a set of operations on that state, and you have a desired goal state. You need to find the steps taken to get from the initial state to the goal state, or that it's not possible to do that...

An example of this type of problem from an old assignment of mine:
The coyote is trying to shoot the roadrunner with a cannon.
Three locations: mountain, tree, river
Rules:
The coyote can shoot the roadrunner if he has the cannon and is on the ground
The coyote can get the cannon if he is on the stonehenge and the stonehenge is at the tree
The coyote can climb on top of the stonehenge
The coyote can climb down from the stonehenge
The coyote can move the stonehenge to any location (mountain, tree, or river).
The coyote can run to any location (mountain, tree or river)

% Assignment 1% state(Coyote_location, Standing_on, Stonehenge_position, Holding_cannon, Shot_roadrunner)% Coyote_location: where is the coyote?% Standing_on: what is the coyote standing on (the stonehenge or the ground)?% Stonehenge_position: where is the stonehenge?% Holding_cannon: is the coyote holding the cannon?% Shot_roadrunner: has the coyote shot the roadrunner?% the coyote climbing off the stonehengetransform( state(Location, stonehenge, Location, X, Y), climb_down, state(Location, ground, Location, X, Y)).% the coyote shooting the roadrunner with the cannontransform( state(X, ground, Z, yes, _), shoot, state(X, ground, Z, yes, yes)).% the coyote getting the cannontransform( state(tree, stonehenge, tree, no, X), grab, state(tree, stonehenge, tree, yes, X)).% the coyote climbing onto the stonehengetransform( state(Location, ground, Location, X, Y), climb_up, state(Location, stonehenge, Location, X, Y)).% the coyote moving the boxtransform(state(Loc1, ground, Loc1, X, Y), move, state(Loc2, ground, Loc2, X, Y)).% the coyote running to a new positiontransform(state(Loc1, ground, Loc3, X, Y), run, state(Loc2, ground, Loc3, X, Y)).% achieve(StartState, Endstate)% True if EndState can be achieved from StartState% also prints Steps (in reverse order)achieve( InitialState, GoalState ) :- achieve( InitialState, GoalState, [] ).achieve( State, State, _ ).achieve( InitialState, GoalState, StateList ):-                transform( InitialState, Step, NewState ),		\+member( NewState, StateList ),                achieve( NewState, GoalState, [NewState|StateList] ),                display( Step ),                nl.query1 :- achieve(state(mountain, ground, river, no, no), state( _, _, _, _, yes)).% a predicate to display a list in reverse order (as it's faster and easier to prepend than append to the accumulated list of moves...)display_list([]).display_list( [H|T] ) :- display_list(T), nl, display(H).% achieveb/2, a predicate to display moves in the correct order.achieveb( InitialState, GoalState ) :- achieveb( InitialState, GoalState, [], [] ).% achieveb/3 a predicate used by achieveb/2 to display a list in the correct order.achieveb( State, State, DisplayList, _ ) :- display_list( DisplayList ).achieveb( InitialState, GoalState, DisplayList, StateList ):-                transform( InitialState, Step, NewState),		\+member( NewState, StateList ),                achieveb( NewState, GoalState, [Step|DisplayList], [NewState|StateList] ).% query2, the same as query1, but using achieveb/2 instead of achieve/2query2 :- achieveb(state(mountain, ground, river, no, no), state( _, _, _, _, yes)).

You can test it by either constructing your own queries, or using the predefined ones (query1. and query2.)

MDI

Mar 22, 2005 at 9:03 AM

Quote:
Original post by VisualFX
I heard about the term STRIPS, but don't know what that means.

STRIPS is the Stanford Research Institute Planning System. It was specially written to solve problems like the blocks world (I think it originally controlled a real robot who moved blocks from room to room or something like that). I think that the reason STRIPS is so popular is because it was one of the first planners to solve the frame problem (is that correct?).

Quote:

Besides, how am I supposed to move the blocks (take an action)and consequently change the status of my lists if Prolog doesn't permit variable assignments?

If you want to solve the problem in the way STRIPS does it (with operators etc.) it's simple. Each operator has a precondition list, and an add and delete lists which are merged with the world state list and subtracted from it respectively after the application of an operator. The task is to simply find an operator whose side effect upon the world state will bring the world state closer to the goal state.

In the previous thread I posted a more lengthy explanation for you, including some sample code.

Quote:

Do I have to make this recursively? Probably yes.. since I'm using lists..

Yes, you have to recursively find actions that bring you closer to the goal state.

fuchu

Mar 22, 2005 at 5:10 PM

I am not anywhere near this! I was just checking this place out. Why is the nodulus used so much? Is this complicated? Tell me? Is it confusing?

MDI

Mar 22, 2005 at 5:28 PM

Modulus is Prolog's line comment. Prolog is quite tricky to get your head around if you're used to procedural languages. Plus it's idea of error reporting is "no" 8-)

Fil

Apr 4, 2005 at 5:09 AM

If I understand what is your problem, that's how you can move a block from one list to another.

move_block(Block,From1,From2,To1,To2):-remove_block(Block,From1,From2),
add_block(Block,To1,To2).

remove_block(B,[B|C],C).

add_block(B,[B|C],C).

From1,To1 are the list (towers?) before the move and From2,To2 after the move.
In remove_block and add_block I take into account only the first element of the list, so you cannot move anything from the middle or the bottom (unless it's the only element of the list).
I think you'll have a list of lists (one for each "tower" you can create on your table).

I hope that helps (sorry in case I misunderstand your question [embarrass]).

lucky_monkey

Apr 4, 2005 at 7:03 PM

add_block(B,[B|C],C). should be add_block(B,C,[B|C]).
also, it's probably a better idea to solve this problem with a single world state list rather than multiple lists.

Fil

Apr 6, 2005 at 6:10 AM

Quote:

add_block(B,[B|C],C). should be add_block(B,C,[B|C]).

Yes! Of course! [embarrass] Otherwise add and remove are the same! [grin]

Quote:

also, it's probably a better idea to solve this problem with a single world state list rather than multiple lists

With multiple lists I know how the block are in the table.
Ex.

       A       B       C .  .  D      -----------blocks([[a,b,c],[],[],[d]]).

(In this case you can build max 4 lists with 4 blocks).
Using only one list you mean something similar to blocks([a,b,c,0,0,d])? I think it is more complex.

lucky_monkey

Apr 6, 2005 at 8:05 PM

The way I'd do it is have a world state list which in your example situation would contain the following:

[clear(a), on(a,b), on(b,c), on(c,table), clear(d), on(d,table), ae]

i.e. a list of predicates to the possible actions (see this post for a listing of these predicates and actions)

Fil

Apr 7, 2005 at 4:22 AM

Yes, of course! :) This way you say where each block is, instead with my version you know how the "towers" are builds. However, the two versions are equivalent to each other. Using one or the other depends on own liking.
I think that to specify initial and target state it is more easy if you use my solution, instead to know which moves you have to do to reach the target state, it is better yours. So I think you have:

problem(INITIAL_STATE,TARGET_STATE,MOVES) as the problem statement, for example:
problem([[a,b,c],[d],[],[]],[[a],[d,c,b],[],[]],MOVES).
To simplify we can assume [[a,b,c],[],[],[d]] is equivalent to [[a,b,c],[d],[],[]] and every other combination of theese lists:
equal_states([X|C1],S):-member(X,S),remove(X,S,S1),equal_states(C1,S1).

Each move now is recorded into MOVES:

remove_block(B,[B|C],C,[unstack(B,[B|C])]).

add_block(B,C,[B|C],[stack(B,C)]).

or something similar.[grin]

Hope that's helpful.
However I suggest you to download 11th chapter of "Artificial Intelligence: A Modern Approach". It speaks about planning and the block problem! :)

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.