Nonmonotonic planning

Section III introduces the concept of nonmonotonic planning and outlines its basic features. It is shown that the tractability of nonmonotonic planning is directly related to the form of the operators employed simple propositional operators lead to polynomial-time algorithms, whereas conditional and functional operators lead to NP-hard formulations. In addition, three specific subsections establish the theoretical foundation for the conversion of operational constraints on the plans into temporal orderings of primitive operations. The three classes of constraints considered are (1) temporal ordering of abstract operations, (2) avoidable mixtures of chemical species, and (3) quantitative bounding constraints on the state of processing systems. 

In Section IV we provide illustrations of the modeling concepts presented in Section II and how the strategy of nonmonotonic planning has been used to synthesize the switchover operating strategy for a chemical process. 

In summary, nonmonotonic planning of process operations has the following distinguishing features ... 

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) ... 

Theorem 3 (First Intractability Theorem). The problem of determining whether a proposition is necessarily true in a nonmonotonic plan whose action representation is sufficiently strong to represent conditional actions is NP-hard. 

In this section we will present a formalized methodology that allows the transformation of quantitative bounding constraints into constraints on the temporal ordering of operators within the spirit of nonmonotonic planning. 

The statement and proof of the truth criterion (see Lakshmanan, 1989) for quantitative constraints is along the lines of Chapman s truth criterion for domain independent nonmonotonic planning. From this criterion, the plan modification operations that would ensure satisfaction of constraints are... 

The synthesis of operating procedures for a chemical plant, using nonmonotonic planning ideas, consists of two distinct phases (1) formula-... 

---