Planning Algorithms Compared

Total and Partial Order Planning Algorithms Compared

From S. Minton, J. Bresina, & M. Drummond Commitment strategies in planning: A comparative analysis.

The Total Ordered Planning Algorithm:

TO(P,G)

1. Termination check: If G is empty, report success and stop.

2. Goal selection: Let c be a goal in G, and let Oneed be the plan step for which c is a precondition.

3. Operator selection: Let Oadd be an operator in the library that adds c.

    If there is no such Oadd, then terminate and report failure.

Backtracking point - all such operators must be considered.

4. Ordering selection: Let Odel be the last deleter of c.

    Insert Oadd somewhere between Odel and Oneed, call the resulting plan P'.

5. Update goal set: Let G' be the set of preconditions in P' that are not true.

6. Recursive invocation: TO(P',G')

The Partially Ordered Planning Algorithm:

UA(P,G)

1. Termination check: If G is empty, report success and stop.

2. Goal selection: Let c be a goal in G, and let Oneed be the plan step for which c is a precondition.

3. Operator selection: Let Oadd be an operator in the library that adds c.

    If there is no such Oadd, then terminate and report failure.

Backtracking point - all such operators must be considered.

4. Ordering selection: Let Odel be the last deleter of c.

Order O`add` after Odel and before Oneed

Repeat until there are no interactions:

·Select a step Oint that interacts with Oadd.
Order Oint either before or after Oadd.

Backtracking point - both orders must be considered for completeness.

Let P' be the resulting plan.

5. Update goal set: Let G' be the set of preconditions in P' that are not true.

6. Recursive invocation: TO(P',G')

Planning - Table of Contents

© Charles F. Schmidt