Novel Structural Parameters for Acyclic Planning Using Tree Embeddings

Novel Structural Parameters for Acyclic Planning Using Tree Embeddings

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

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 4653-4659. https://doi.org/10.24963/ijcai.2018/647

We introduce two novel structural parameters for acyclic planning (planning restricted to instances with acyclic causal graphs): up-depth and down-depth. We show that cost-optimal acyclic planning restricted to instances with bounded domain size and bounded up- or down-depth can be solved in polynomial time. For example, many of the tractable subclasses based on polytrees are covered by our result. We analyze the parameterized complexity of planning with bounded up- and down-depth: in a certain sense, down-depth has better computational properties than up-depth. Finally, we show that computing up- and down-depth are fixed-parameter tractable problems, just as many other structural parameters that are used in computer science. We view our results as a natural step towards understanding the complexity of acyclic planning with bounded treewidth and other parameters.
Keywords:
Planning and Scheduling: Planning Algorithms
Planning and Scheduling: Theoretical Foundations of Planning