Planning with Incomplete Knowledge and Limited Quantification

We present a new method for partial order planning in the STRIPS/SNLP style. Our contribution centers on how we drop the closed world assumption while adding a useful class of universally quantified propositions to the representation of states and actions. These quantified expressions allow expression of partially closed worlds, such as "block A has no other block on it", or "F is the only Tex file in directory D." In addition, we argue informally that the time complexity of our algorithm is no worse than traditional partial order planners that make the closed world assumption. STRIPS-style planning (Fikes & Nilsson 1971) is decidable only if we restrict the language to finitely many ground terms (Erol, Nau, & Subrahmanian 1992). STRIPS-style planning becomes NP-complete only when we bound the length of the plan being sought (Gupta & Nau 1991). Thus, planning is intractable in the general case. However, thanks to recent advances in applying stochastic search to propositional satisfiab..