A Refined Understanding of Cost-optimal Planning with Polytree Causal Graphs

A Refined Understanding of Cost-optimal Planning with Polytree Causal Graphs

Christer Bäckström, Peter Jonsson, Sebastian Ordyniak

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence
Best Sister Conferences. Pages 6126-6130. https://doi.org/10.24963/ijcai.2019/848

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 Ståhlberg. We continue this line of research 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.
Keywords:
Planning and Scheduling: Planning and Scheduling
Planning and Scheduling: Planning Algorithms
Planning and Scheduling: Theoretical Foundations of Planning