Plan-space Planning Algorithms

Plan-Space Planning Algorithms: An alternative is to search through the space of plans rather than a space of situations. That is, we start with a simple, incomplete plan, which we call a partial plan. Then we consider ways of expanding the partial plan until we come up with a complete plan that solves the problem. We use this approach when the ordering of sub-goals affects the solution.

Here one starts with a simple, incomplete plan, a partial plan, and we look at ways of expanding the partial plan until we come up with a complete plan that solves the problem. The operators for this search are operators on plans: adding a step, imposing an ordering that puts one step before another, instantiating a previously unbound variable, and so on. Therefore the solution is the final plan.

Two types of operators are used:

• Refinement operators take a partial plan and add constraints to it. They eliminate some plans from the set and they never add new plans to it.
• A modification operator debugs incorrect plans that the planner may make, therefore we can worry about bugs later.

Representation of Plans: A plan is formally defined as a data structure consisting of the following 4 components:

1. A set of plan steps
2. A set of step ordering constraints
3. A set of variable binding constraints
4. A set of causal links

Example:
Plan(
STEPS:{S1:Op(ACTION: Start),
S2:Op(ACTION: Finish,
PRECOND: Ontable(c), On(b,c), On(a,b) },
ORDERINGS: {S1 < S2},
BINDINGS: {},
LINKS: {} )

Key Difference Between Plan-Space Planning and Situation-Space Planning In Situation-Space planners all operations, all variables, and all orderings must be fixed when each operator is applied. Plan-Space planners make commitments (i.e., what steps in what order) only as necessary. Hence, Plan-Space planners do least-commitment planning.

Start Node in Plan Space: The initial plan is created from the initial state description and the goal description by creating two "pseudo-steps:"

Start
P: none
E: all positive literals defining the initial state
Finish
P: literals defining the conjunctive goal to be achieved
E: none
and then creating the initial plan as: Start ---------> Finish

Searching Through Plan Space There are two main reasons why a given plan may not be a solution:

• Unsatisfied goal. That is, there is a goal or sub-goal that is not satisfied by the current plan steps.
• Possible threat caused by a plan step that could cause the undoing of a needed goal if that step is done at the wrong time

So, define a set of plan modification operators that detect and fix these problems