Some definitions:

• A goal is a statement about the world that a planning agent (ie. a mobile in our case) wishes to pertain.
• A plan is a sequence of actions which, if executed in order, will achieve some goal.
• An action is a set of preconditions and effects.
• A precondition is a statement about the world that must hold true for its associated action to take place.
• An effect is a statement about the world that holds true after an action has been executed (that didn’t hold place before).

The core planning engine functions as follows:

• Take a goal.
  • If it is satisfied already, stop. Success!
• Look through all actions known to the planner.
• Place all actions that have the goal as an effect into a consideration set.
  • If the consideration set is empty, stop. Failure!
• Select an action from the consideration set.
• Set up all the action’s preconditions as goals.
• Recursively attempt to create plans for those goals.
  • If it succeeds, stop. Success!
• If it fails, backtrack and try a different action from the consideration set.

Thus, planning can be seen as a search through the space of actions (or goals).

This describes an absolutely basic planning engine. There are many planning engines in existence in the field of AI, able to plan at degrees of sophistication far superior to this one. For the purpose of quest generation, though, the above is reasonably adequate.

You’ll have to wait a while longer before I demonstrate this, though. First, I really ought to present an example of the basic machinery in action.

An Example

A mobile is standing next to a market stall, which has a loaf of bread on it that the mobile has just bought. The mobile’s goal is for the loaf to be on the mobile’s nearby cart. It knows three actions:

Action:	pick up X from Y
Preconditions:	X is at Y I am at Y not (X is heavy)
Effects:	not (X is at Y) I’m carrying X
Action:	put down X at Y
Preconditions:	I’m carrying X I am at Y
Effects:	not (I’m carrying X) X is at Y
Action:	walk from X to Y
Preconditions:	I am at X
Effects:	not (I am at X) I am at Y

The initial state of the world is:

I am at stall
bread is at stall

The mobile’s goal is [bread is at cart]. It looks through all the actions it knows, and sees that this can be achieved by put down bread at cart. It replaces its goal by the preconditions of put down X at Y, ie. I’m carrying bread and I am at cart. To achieve I’m carrying bread, it looks through its actions again and finds that there’s only one that can do it, pick up X at Y. It replaces its goal I’m carrying bread with the preconditions of pick up X at Y; these are bread is at stall, I am at stall and not(bread is heavy). All three are currently satisfied. This means the mobile is able to pick up the bread, thereby leaving the goal stack as [I am at cart]. Only one action will achieve this effect, walk from X to Y. The precondition for this, I am at stall, is already true, therefore the mobile can walk from stall to cart. Doing so empties the goal stack (ie. enables the second precondition of put down bread at cart), the execution of which satisfies the original goal. The final plan is therefore:

pick up bread at stall
walk from stall to cart
put down bread at cart

From the mobile’s point of view, this can be paraphrased as:

“I want the bread to be at the cart, so what action, out of all the actions I know, can I undertake to cause that? Well I could put down the bread, that would work, but to do so I’d have to be carrying the bread, which I’m not. Also, I’d have to be at the cart, which I’m not. OK, so what can I do that will leave me carrying the bread? I could pick it up – and what’s more, I can do that right now! Is there any way I can get to the cart? Yes, I could walk there – something else I can do right now. OK, so my plan is: pick up the bread, walk to the cart, put down the bread.”.

That’s the basic planning machinery. Next time, I’ll point out some problems with it.