Nonmonotonic planning completeness

In this theorem, any proposition p can represent an operator (i.e., an operation step), whereas the situations t and s represent any intermediate state of the process. Although the validity of the theorem is general, its practical utility is confined to monotonic planning with STRIPS-like operators. For example, in nonmonotonic planning the plans are at any point when partially specified and a new mechanism is needed to guarantee that when the partial plan is completed, a given proposition (i.e., a given operation) is still true (i.e., consistent). 

For STRIPS-like operators. Chapman (1985) developed a polynomialtime algorithm, called TWEAK, around five actions that are necessary and sufficient for constructing a correct and complete plan. As soon as we try to extend these ideas to nonmonotonic planning with conditional operators, we realize that no polynomial-time algorithm can be constructed, as the following theorem explicitly prohibits (Chapman, 1985) ... 

In this section we will offer several illustrations of the various aspects of nonmonotonic operations planning (discussed in earlier sections) including the following (1) development of hierarchical models for the process and its operations, (2) conversion of constraints to temporal orderings of primitive operations, and (3) synthesis of complete plans. 

---