liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
Tractable Cost-Optimal Planning over Restricted Polytree Causal Graphs
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology. (TCSLAB)
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology. (TCSLAB)
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology. (TCSLAB)
2015 (English)In: Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015Conference paper (Refereed)
Abstract [en]

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.

Place, publisher, year, edition, pages
2015.
Keyword [en]
automated planning, causal graph, polynomial-time algorithm, cost-optimal planning, polytree
National Category
Computer Systems
Identifiers
URN: urn:nbn:se:liu:diva-118729ISBN: 978-1-57735-703-2OAI: oai:DiVA.org:liu-118729DiVA: diva2:816591
Conference
29th AAAI Conference on Artificial Intelligence (AAAI-15), January 25–30, Austin, TX, USA
Funder
CUGS (National Graduate School in Computer Science)
Available from: 2015-06-03 Created: 2015-06-03 Last updated: 2015-06-05

Open Access in DiVA

No full text

Other links

http://www.aaai.org/ocs/index.php/AAAI/AAAI15/paper/view/9650

Search in DiVA

By author/editor
Aghighi, MeysamJonsson, PeterStåhlberg, Simon
By organisation
Software and SystemsThe Institute of Technology
Computer Systems

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 149 hits
ReferencesLink to record
Permanent link

Direct link