Partial-order Planning

Total-Order vs. Partial-Order Planners: Any planner that maintains a partial solution as a totally ordered list of steps found so far is called a total-order planner, or a linear planner. Alternatively, if we only represent partial-order constraints on steps, then we have a partial-order planner, which is also called a non-linear planner. In this case, we specify a set of temporal constraints between pairs of steps of the form S1 < S2 meaning that step S1 comes before, but not necessarily immediately before, step S2. We also show this temporal constraint in graph form as

S1 > S2

STRIPS is a total-order planner, as are situation-space progression and regression planners
Partial-order planners exhibit the property of least commitment because constraints ordering steps will only be inserted when necessary. On the other hand, situation-space progression planners make commitments about the order of steps as they try to find a solution and therefore may make mistakes from poor guesses about the right order of steps.

Representing a Partial-Order Plan A partial-order plan will be represented as a graph that describes the temporal constraints between plan steps selected so far. That is, each node will represent a single step in the plan (i.e., an instance of one of the operators), and an arc will designate a temporal constraint between the two steps connected by the arc. For example,

• S1 > S2 > S5
• |\ ^
• | \ | |
• | v |
• > S3 > S4

graphically represents the temporal constraints S1 < S2, S1 < S3, S1 < S4, S2 < S5, S3 < S4, and S4 < S5. This partial-order plan implicitly represents the following three total-order plans, each of which is consistent with all of the given constraints:
[S1,S2,S3,S4,S5], [S1,S3,S2,S4,S5], and [S1,S3,S4,S2,S5].