Planning

In a completely accessible world a simple planning agent can loop through the following sequence.

1. Tell its knowledge base what it perceives at time t,
2. Deduce a complete and correct model of the world.
3. Ask the Knowledge base for a goal
4. Invoke a planner to produce a sequence of actions that will produce the goal,
5. If the plan is not empty then
   take the action
   Tell the KB that it has taken the first action
   Set the plan to the remaining actions
6. Update the time.

Planning as problem solving

One way that a planner could be constructed is by using a problem solver. After all the agent has available to it a set of actions that it can perform and it can represent the states in the world model and the effect of actions on them. Presumably it can recognise the goal.

Planning has come to be viewed as different from problem solving because it emphasizes different aspects of the process of finding plans. The most apparent of these is the willingness to consider partial plans.

Partial Plans

In problem solving the solutions are usually generated as sequences of actions that originate at the start state (or that terminate at the goal in the case of backward or bidirectional search). Often the choice of action is based upon a heuristic function. In planning the choice of action is more likely to be based on some property of the goal. For example in a plan to cook a thanksgiving dinner one knows that buying a turkey is part of the plan. Thus one might try to grow this partial plan into a complete plan.

Most of the interesting questions in problem solving arise in the case where the problem involves a high degree of interaction between the features of the problem. So that it is hrd to change one thing without messing up a lot of other parts of the problem. However in planning this is much less the case. Buying a turkey is a quite distinct activity from setting the table. You can work out how to do one without knowing how you propose to do the other. This permits a divide and conquer approach to planning.

Aside

Representations for States and Goals

Planners use a restricted language for representing problems. this means that there are fewer possible solutions to search through. We will consider one such language here: the STRIPS language.

In STRIPS states are represented by conjunctions of function free ground literals (check AIMA for formal definitions of this). Thus we might have

at(home) /\ have(turkey) /\ not have(cranberry_sauce)

Goals are also represented as conjunctions of literals. Goals however can contain variables (which will be instantiated as part of the solution).

Actions are represented by

1. A description used to return the action to the environment, in our case a name suffices
2. the precondition a conjunction of positive literals that says what must be true before the action can be applied
3. the effect of an operator is a conjunction of literals that describe how the situation changes when an action is performed.

Representing Plans

An incomplete plan is a partial plan we can search through the space of partial plans for a complete plan. Operators on partial plans include

• adding a step to the plan
• imposing an order that puts one step before another,
• instantiating a previosly unbound varaible

Refinement Operators on plans take a partial plan and add constraints to it. Other operators are called modification operators. Following AIMA we only work with refinement operators.

A plan consists of four components

• A set of plan steps. Each step is an operator for the problem.
• A set of step ordereing constraints
• A set of variable binding constraints
• A set of causal links Si -- c --> Sj; read as Si achieves precondition c for Sj.

With this formalism a partial plan from which to start looks like.

Plan(Steps: {S1: Op(Action:Start),
	       S2: Op(Action:Finish,
                               Precond: Description of Goal State)}
       Orderings:  {S1 < S2}
       Bindings: {},
       Links: {}
      )

A solution is a plan that an agent can execute, and that guarantees achievement of the goal.

A Partial Order Planning Algorithm

Prolog Code for Planners

Return to UG AI home page

Last Changed: 13 November 1995