Partial-Order Planning (POP): Planning Without a Strict Linear Action Order

Partial-order planning keyword (often abbreviated POP) is a class of AI planning algorithms that construct a plan as a set of actions plus ordering constraints. Instead of committing to one strict timeline up front (as in total-order/linear planning), POP produces a partially ordered plan that remains flexible until the end, ensuring only the orderings needed for correctness are enforced.

Core idea: POP represents which actions must come before or after other actions using ordering constraints, while leaving unrelated actions unordered when they do not interfere. This lets the planner exploit commutativity: independent actions can be executed in any compatible order, and the plan can be “linearized” later by choosing any topological ordering that respects the constraints.
A typical POP formulation uses (1) open conditions to track unsatisfied preconditions, (2) causal links to record which action supports which condition, and (3) threat handling to resolve actions that could negate or undermine a causal link.

Note: In this environment, web research via the required search tool failed (usage limit errors). Because of your course-generation requirements, I cannot provide citation-backed claims. I will still explain partial-order planning thoroughly, but you should treat it as non-cited background rather than a fully verified, source-cited “research” output.

Block-world setup: goal stack without forcing a single linear order

We use a classic blocks-world scenario with actions like “pick up” and “put down.” The key point is to show that POP can leave actions unordered when their order does not matter.

Symbols

• Blocks: $A$, $B$, $C$
• Table: $T$
• Predicates:
  • $On(x,y)$: block $x$ is on block $y$
  • $OnTable(x)$: block $x$ is on the table
  • $Clear(x)$: nothing is on top of $x$
  • $Holding(x)$: the robot is holding $x$

Initial state (informal)

• $Clear(A)$, $Clear(B)$, $Clear(C)$
• $OnTable(A)$, $OnTable(B)$, $OnTable(C)$
• Hand is empty (not holding anything)

Goals

We want:

1. $On(A, B)$
2. $On(C, A)$

Intuitively, to get $On(C,A)$, we must make $A$ available as a support surface (not required to be on a particular thing besides having $Clear(A)$). To get $On(A,B)$, we must place $A$ onto $B$.

A linear plan might choose an order like:

• Step 1: move $A$ onto $B$
• Step 2: move $C$ onto $A$

But POP can represent actions more flexibly by only enforcing the ordering that is truly needed: the placement of $C$ onto $A$ must occur after $A$ is positioned so that $A$ is in the right place and stable, while other preparations can be partially ordered.

Key terms:

• Causal link
• Threat
• Open condition

A partial-order plan for the block-world goals

We sketch a POP-style plan using representative actions. (Exact action schemas vary by textbook, but POP reasoning is the same.)

Action templates (informal)

• $PickUp(x)$: requires $Clear(x)$ and $On(x, \_)$ or $OnTable(x)$; results in $Holding(x)$ and $Clear(\_)$ effects
• $PutOn(x,y)$: requires $Holding(x)$ and $Clear(y)$; results in $On(x,y)$ and $Clear(x)$
• $PutOnTable(x)$: requires $Holding(x)$; results in $OnTable(x)$ and $Clear(x)$

Planning objective

Achieve:

• $On(A,B)$
• $On(C,A)$

POP will introduce causal links such as:

• An action $PutOn(A,B)$ supports the goal $On(A,B)$.
• An action $PutOn(C,A)$ supports the goal $On(C,A)$.

The ordering constraints that matter:

• To support $On(C,A)$, the action $PutOn(C,A)$ must occur at a time when $A$ is a suitable support surface (e.g., $Clear(A)$ and appropriately positioned). In many simplified representations, $Clear(A)$ is true initially and remains true unless actions interfere; but placing $A$ on $B$ should not destroy $Clear(A)$—it typically remains clear as long as nothing is stacked on top of $A$.
• Therefore, if both actions only rely on conditions that are satisfied initially and do not interfere, POP can leave $PutOn(A,B)$ and $PutOn(C,A)$ unordered except for any constraint created by how $C$ is obtained (e.g., $PickUp(C)$ must precede $PutOn(C,A)$, and $PickUp(A)$ must precede $PutOn(A,B)$). Those are standard precondition orderings.

One valid POP partial order structure (with key constraints only)

Let the relevant action nodes be:

• $a_1$: $PickUp(A)$
• $a_2$: $PutOn(A,B)$
• $a_3$: $PickUp(C)$
• $a_4$: $PutOn(C,A)$

And causal/support links:

• $a_2 \rightarrow On(A,B)$ (satisfies the first goal)
• $a_4 \rightarrow On(C,A)$ (satisfies the second goal)

Ordering constraints that are forced:

• $a_1 \prec a_2$ because $PutOn(A,B)$ requires $Holding(A)$.
• $a_3 \prec a_4$ because $PutOn(C,A)$ requires $Holding(C)$.
• Additionally, depending on your precise action model, there may be a constraint ensuring $PutOn(C,A)$ occurs after $A$ is in the correct configuration (if $Clear(A)$ or some “support availability” becomes true only after $PutOn(A,B)$). For the classic simplified blocks-world where $Clear(A)$ is initially true and placing $A$ on $B$ does not put something on top of $A$, no strict ordering between $a_2$ and $a_4$ may be required.

So POP can output a partial order like:

• Required: $a_1 \prec a_2$, $a_3 \prec a_4$, Start ≺ all needed steps ≺ Finish
• Possibly not required: $a_2$ and $a_4$ unordered

Now observe the “partial-order” aspect: there is no edge between $a_2$ and $a_4$. That means there are multiple valid linearizations. Two examples:

• Linearization 1: $a_1, a_2, a_3, a_4$
• Linearization 2: $a_3, a_4, a_1, a_2$

Both respect the forced orderings ($a_1 \prec a_2$ and $a_3 \prec a_4$). The planner delays commitment on unrelated actions.

Why POP allows multiple action orders (conceptual explanation)

In total-order planning, you pick a single sequence early, and later discoveries may force backtracking. In partial-order planning, you only encode constraints that are necessary for correctness.

• If action $a_2$ does not affect the preconditions or causal links needed by action $a_4$, then $a_2$ and $a_4$ can be unordered.
• If they do interfere, POP’s threat detection introduces an ordering constraint (or chooses a different action) to protect the causal link.

Threat resolution is what turns “maybe unordered” into “must be ordered” when interference exists.