期刊名称：Journal of Automation, Mobile Robotics & Intelligent Systems (JAMRIS)
印刷版ISSN：1897-8649
电子版ISSN：2080-2145
出版年度：2008
卷号：32
页码：203-288
出版社：Industrial Research Inst. for Automation and Measurements, Warsaw
摘要：We study the complexity of cost-optimal classical planning over propositional
state variables and unary-effect actions. We discover novel problem fragments
for which such optimization is tractable, and identify certain conditions that
differentiate between tractable and intractable problems. These results are
based on exploiting both structural and syntactic characteristics of planning
problems. Specifically, following Brafman and Domshlak (2003), we relate the
complexity of planning and the topology of the causal graph. The main results
correspond to tractability of cost-optimal planning for propositional problems
with polytree causal graphs that either have O(1)-bounded in-degree, or are
induced by actions having at most one prevail condition each. Almost all our
tractability results are based on a constructive proof technique that connects
between certain tools from planning and tractable constraint optimization, and
we believe this technique is of interest on its own due to a clear evidence for
its robustness
