Blocking as a Middle-Ground for Step-Order Commitments in Planning

Proceedings of the AAAI Conference on Artificial Intelligence, 13

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 13

AAAI-96 Student Abstracts

Partial order planners commit only to the relative positions of the steps in the plan, and leave both their absolute positions as well as the relative distance between the different steps unspecified until the end of planning. Although this is seen as an advantageous feature of partial order planning, it can sometimes be a mixed-blessing. Because the relative distances between the steps are unspecified, any unordered step may be able to come between any existing steps and cause interactions and the planner may spend inordinate effort considering all possible interleavings of the subplans of the individual goals. This happens in cases where top-level goals are serializable but have long sub-plans which have internal interactions, plan-space planners would consider all simple-establishments and threats between steps of a the subplan of a top-level goal gi (represented by P,;) and Ps3 which could affect its performance drastically. State-space planners, on the other hand, fix both the distance and position, and this is often more commitment than is needed, causing extensive backtracking.