Tractable Cost-Optimal Planning over Restricted Polytree Causal Graphs

Authors

  • Meysam Aghighi Linköping University
  • Peter Jonsson Linköping University
  • Simon Ståhlberg Linköping University

DOI:

https://doi.org/10.1609/aaai.v29i1.9650

Keywords:

automated planning, causal graph, polynomial-time algorithm, cost-optimal planning, polytree

Abstract

Causal graphs are widely used to analyze the complexity of planning problems. Many tractable classes have been identified with their aid and state-of-the-art heuristics have been derived by exploiting such classes. In particular, Katz and Keyder have studied causal graphs that are hourglasses (which is a generalization of forks and inverted-forks) and shown that the corresponding cost-optimal planning problem is tractable under certain restrictions. We continue this work by studying polytrees (which is a generalization of hourglasses) under similar restrictions. We prove tractability of cost-optimal planning by providing an algorithm based on a novel notion of variable isomorphism. Our algorithm also sheds light on the k-consistency procedure for identifying unsolvable planning instances. We speculate that this may, at least partially, explain why merge-and-shrink heuristics have been successful for recognizing unsolvable instances.

Downloads

Published

2015-03-04

How to Cite

Aghighi, M., Jonsson, P., & Ståhlberg, S. (2015). Tractable Cost-Optimal Planning over Restricted Polytree Causal Graphs. Proceedings of the AAAI Conference on Artificial Intelligence, 29(1). https://doi.org/10.1609/aaai.v29i1.9650