Prolog (World Of Blocks)

Do you wish to make a game, or do you wish to make 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?

If it's the latter, then that is quite easy (I'll show you a simple STRIPS like system):

Define some operators. These operators have a list of preconditions that must be true of the world before they can be applied, an additions list which adds facts to the world after they have been applied, and a deletion list which deletes facts from the world after they have been applied.

A sample operator is stack:

p_op(stack(BlockA, BlockB), [clear(BlockA), clear(BlockB)], [on(BlockA, BlockB)], [clear(BlockB)]).

This takes two blocks and stacks them on top of one another, providing that they are both "clear" (it's a simplified world representation, so don't blame me if there's faults in it :-)).

It's simple to write a predicate that applies an operator to the current state:

apply(Rule, State, NewState) :-  p_op(Rule, Pre, Add, Del),  subset(Pre, State),  union(State, Add, TState),  subtract(Del, TState, NewState).

(That's off the top of my head).

You then need to find a way of taking a start state and a goal state and applying a set of operators to the initial state to result in the goal state. You can do this by working backwards from the goal state.

HTH.

if you really want to make a game in prolog you really dont know much about it
first prolog is no programming language, its an logical or formal language

you can do what MDI suggests, but if you wish an executable file, a gui or something like that i suggest you try an other language (i dont hate prolog or something, but it isnt made for programming)

You don't mean "Towers of Hanoi" do you?

Quote:

Original post by iMalc You don't mean "Towers of Hanoi" do you?

I think he means that game that gets distributed as "Mahjong" even though it's nothing to do with the actual real-world game of that name (except for the appearance of the "tiles").

Thanks MDI,
I believe that's exactly what I needed to know. Now I know how to proceed with my search.

Really, thanks a lot.



P.S: Thanks to everyone else who invested some time answering my question.

Quote:

Original post by Zahlman Quote: Original post by iMalc You don't mean "Towers of Hanoi" do you? I think he means that game that gets distributed as "Mahjong" even though it's nothing to do with the actual real-world game of that name (except for the appearance of the "tiles").

No, he means the blocks world problem: you start with an arbitrary initial state, and have an arbitrary goal state. The program then works out how to get from the initial state to the goal state. All blocks are the same size, and you can't pick up a block that's underneath another block.

e.g.
initial: goal: b
bc c
steps:
pickup(b)
stack(b,c)

---

in blocks world you have:
actions:

• pickup(x)
• putdown(x)
• stack(x,y)
• unstack(x,y)

predicates:

• clear(x)
• on(x,y)
• armEmpty
• holding(x)

pickup(x):

• precondition: ae (armEmpty), on(x, table), clear(x)
• action: -ae, -on(x,table), +holding(x)

putdown(x):

• precondition: holding(x)
• action: +ae, +on(x,table), -holding(x)

unstack(x,y):

• precondition: ae, on(x, y), clear(x)
• action: -ae, -on(x,y), +holding(x), +clear(y)

stack(x,y):

• precondition: holding(x), clear(y)
• action: +ae, +on(x,y), -holding(x), -clear(y)

---

I'm a bit rusty with Prolog, but if you still need help then ask...

But how can I create an action if there are no assingments to variables in Prolog?
Is there a special way of altering the state of what's inside the knowledge base? I mean at run-time.


BTW: Thanks for the feedback

VisualFX

Yes, I kind of hinted at it in my post (not wanting to spoil the problem for you too much). Basically, your world state is kept in a Prolog list. Your operators each have an add and delete list which modifies the world state list via the apply predicate when they are applied.

Here's an example.

Start off with the canonical world state, all blocks are on the table, with none stacked:

[on(a, table), on(b, table), clear(a), clear(b), arm_empty].

This list would be a parameter to your top level planning predicate, let's call it pln for short.

You also need a goal state, which we will define as such:

[on(a, b), on(b, table), clear(a), arm_empty].

At run time, you can call ?- pln([on(a, table), on(b, table), clear(a), clear(b), arm_empty], [on(a, table), on(b, table), clear(a), clear(b), arm_empty], X). and X will be instanced with a list of operators needed to be applied to the initial state to have it result in the goal state.

The state is affected by the add and delete lists of the operators. Let's define a simple version of stack(a, b). We need to think of what must be true of the world prior to the application of the operator, what will be true after it's application, and what will no longer be true. To stack two blocks the block that will be at the bottom of the stack must be initially clear, and the arm must be already holding the block that will be on top. This forms the precondition list for the operator. After the operator has been applied, one block (a) will be on another (b) and b will no longer be clear.

So, we have three lists, precondition, add and delete, which are [clear(b), holding(a)], [on(a, b), clear(a)] and [clear(b)] respectively.

To apply an operator, you must first make sure that the precondition list is a subset of the current world condition (otherwise it's impossible to apply it to the current world state, it wouldn't make sense to try and stack two blocks which are at the bottom of stacks, for instance) then you merge the add list to the current world state and remove the delete list, resulting in your new world state. That's exactly what the apply/3 predicate did in my initial post in this thread.

So, with our example, we try to apply stack(a, b) to the initial state:

We first inspect the precondition list, but there's a problem, as the arm is not currently holding the block a. In order to complete this task, we must make holding(a) a goal, which is satisfied by applying the pickup(a) operator. Imaginging that we have applied pickup(a), we can now go on to apply stack(a, b). We first union the add and world state lists to get:

[on(b, table), clear(b), arm_empty, on(a, b), clear(a)].

And then subtract the delete list, to get:

[on(b, table), clear(a), arm_empty, on(a, b)].

I think :-P

HTH.

By the way, you might wish to ask a moderator to move this to the AI forum. The people in there are possibly more likely to be able to answer any question that you have than people in here (not that I'm implying anything or anything :-p).