1998 · 137 citations · 19 references
ComputingComputer ScienceCompilersFormal MethodsKnowledge RepresentationPlan EvaluationPlan OptimizationConditional EffectsConditional PlanningPlan FormulationPropositional ReasoningPropositional RepresentationStrips Representation
The recent approaches of extending the graphplan algorithm to handle more expressive planning formalisms raise the question of what the formal meaning of "expressive power" is. We formalize the intuition that expressive power is a measure of how concisely planning domains and plans can be expressed in a particular formalism by introducing the notion of "compilation schemes" between planning formalisms. Such compilation schemes restrict the growth of planning domains and the corresponding plans. Using this notion, we analyze the expressiveness of a large family of propositional planning formalisms, ranging from basic strips to a formalism with conditional effects, partial state specifications, and propositional formulae in the preconditions. One of the results is that conditional effects cannot be compiled away if plan size should grow only linearly but can be compiled away if we allow for polynomial growth of the resulting plans. This result confirms that the recently proposed extensio...
19
Fast planning through planning graph analysis
Avrim Blum, Merrick L. Furst · Artificial Intelligence · 1997 · 1.6K citations
The computational complexity of propositional STRIPS planning
Tom Bylander · Artificial Intelligence · 1994 · 863 citations