Partial-Order Planner(POP) is a regression planner; it uses problem decomposition; it searches plan space rather than state space; it build partially-ordered plans; and it operates by the principle of least-commitment.

A plan in POP (whether it be a finished one or an unfinished one) comprises:

• A set of plan steps. Each of these is a STRIPS operator, but with the variables instantiated.
• A set of ordering constraints: Si -< Sj means step Si must occur sometime before Sj (not necessarily immediately before).
• A set of causal links: $S_i \underrightarrow{c}S_j$ means step Si achieves precondition c of step Sj .

So, it comprises actions (steps) with constraints (for ordering and causality) on them.

The algorithm needs to start off with an initial plan. This is an unfinished plan, which we will refine until we reach a solution plan. The initial plan comprises two dummy steps, called Start and Finish.

Start is a step with no preconditions, only effects: the effects are the initial state of the world. Finish is a step with no effects, only preconditions: the preconditions

are the goal.

By way of an example, consider this initial state and goal state:

Plan(STEPS: {S1: Op(ACTION: Start,
    EFFECT: clear(b) ^ clear(c) ^ on(c, a) ^ ontable(a) ^
     ontable(b) ^ armempty),
     S2: Op( ACTION: Finish,
    PRECOND: on(c, b) ^ on(a, c))},
ORDERINGS: {S1-< S2},
LINKS: {})

This initial plan is refined using POP’s plan refinement operators. As we apply them, they will take us from an unfinished plan to a less and less unfinished plan, and ultimately to a solution plan. There are four operators, falling into two groups:

• Goal achievement operators

  1. Step addition: Add a new step Si which has an effect c that can achieve an as yet unachieved precondition of an existing step Sj . Also add the following constraints: Si -<sj and="" si="" c="" sj="" and="" start="" -<si="" -&lt;="" finish.<="" li="">
  2. Use an effect c of an existing step Si to achieve an as yet unachieved precondition of another existing step Sj . And add just two constraints: Si -< Sj and Si c Sj.

• Causal links must be protected from threats, i.e. steps that delete (or negate or clobber) the protected condition. If S threatens link Si c Sj :

  1. Promote: add the constraint S -< Si; or
  2. Demote: add the constraint Sj -< S

The goal achievement operators ought to be obvious enough. They find preconditions of steps in the unfinished plan that are not yet achieved. The two goal achievement operators remedy this either by adding a new step whose effect achieves the precondition, or by exploiting one of the effects of a step that is already in the plan.

The promotion and demotion operators may be less clear. Why are these needed? POP uses problem-decomposition: faced with a conjunctive precondition, it uses goal achievement on each conjunct separately. But, as we know, this brings the risk that the steps we add when achieving one part of a precondition might interfere with the achievement of another precondition. And the idea of promotion and demotion is to add ordering constraints so that the step cannot interfere with the achievement of the precondition.

Finally, we have to be able to recognise when we have reached a solution plan: a finished plan.

A solution plan is one in which:

• every precondition of every step is achieved by the effect of some other step and all possible clobberers have been suitably demoted or promoted; and
• there are no contradictions in the ordering constraints, e.g. disallowed is Si -< Sj and Sj -<si; also="" disallowed="" is="" si="" -<sj="" ,="" sj="" -&lt;="" sk="" and="" sk="" -&lt;="" si.<="" li="">

Note that solutions may still be partially-ordered. This retains flexibility for as long as possible. Only immediately prior to execution will the plan need linearisation, i.e. the imposition of arbitrary ordering constraints on steps that are not yet ordered. (In fact, if there’s more than one agent, or if there’s a single agent but it is capable of multitasking, then some linearisation can be avoided: steps can be carried out in parallel.)