Partial-order planning

Partial-order planning is an approach to automated planning that leaves decisions about the ordering of actions as open as possible. It contrasts with total-order planning, which produces an exact ordering of actions. Given a problem in which some sequence of actions is required in order to achieve a goal, a partial-order plan specifies all actions that need to be taken, but specifies an ordering of the actions only where necessary.

Consider the following situation: a person must get from point A to point B. In between points A and B, there is an obstacle course. In a partial order plan, the specific path that this person will take to get from point A to point B will not be conceived of all at once. Instead the person will navigate the obstacle course by deciding which obstacles to master one at a time. Partial-order planning exhibits the Principle of Least Commitment, which contributes to the efficiency of this planning system as a whole. Often there are many possible plans for a problem which only differ in the order of the actions. Many traditional automated planners search for plans in the full search space containing all possible orders. In addition to the smaller search space for partial-order planning, it may also be advantageous to leave the option about the order of the actions open for later. An important distinction to be made is between ordering steps of an action and conceptualizing those steps. Partial order planning doesn’t sequence actions until it is absolutely necessary; however, these actions are conceived of much before they are sequenced. This type of planning system is simply a relation structure between actions. It is not the mechanism by which these actions mentally come to fruition.

A partial-order plan or partial plan is a plan which specifies all actions that need to be taken, but does not specify an exact order for the actions when the order does not matter. It is the result of a partial-order planner. A partial-order plan consists of four components:

In order to keep the possible orders of the actions as open as possible, the set of order conditions and causal links must be as small as possible.

A plan is a solution if the set of open preconditions is empty.

A linearization of a partial order plan is a total order plan derived from the particular partial order plan; in other words, both order plans consist of the same actions, with the order in the linearization being a linear extension of the partial order in the original partial order plan.

For example, a plan for baking a cake might start:

This is a partial plan because the order for finding eggs, flour and milk is not specified, the agent can wander around the store reactively accumulating all the items on its shopping list until the list is complete.

...
Wikipedia