Abstract
Complexity analysis based on the causal graphs of
planning instances is a highly important research
area. In particular, tractability results have led to
new methods for constructing domain-independent
heuristics. Important early examples of such results were presented by, for instance, Brafman &
Domshlak and Katz & Keyder. More general results based on polytrees and bounding certain parameters were subsequently derived by Aghighi et
al. and Stahlberg. We continue this line of re- ?
search by analyzing cost-optimal planning for instances with a polytree causal graph, bounded domain size and bounded depth. We show that no further restrictions are necessary for tractability, thus
generalizing the previous results. Our approach is
based on a novel method of closely analysing optimal plans: we recursively decompose the causal
graph in a way that allows for bounding the number
of variable changes as a function of the depth, using
a reording argument and a comparison with prefix
trees of known size. We then transform the planning instances into tree-structured constraint satisfaction instances