Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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, AAAI Press, 2015Conference paper, Published 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
AAAI Press, 2015.
Series
Proceedings of the AAAI Conference on Artificial Intelligence, ISSN 2159-5399, E-ISSN 2374-3468
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-2 (print)OAI: 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: 2017-05-17
In thesis
1. Computational Complexity of some Optimization Problems in Planning
Open this publication in new window or tab >>Computational Complexity of some Optimization Problems in Planning
2017 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

Automated planning is known to be computationally hard in the general case. Propositional planning is PSPACE-complete and first-order planning is undecidable. One method for analyzing the computational complexity of planning is to study restricted subsets of planning instances, with the aim of differentiating instances with varying complexity. We use this methodology for studying the computational complexity of planning. Finding new tractable (i.e. polynomial-time solvable) problems has been a particularly important goal for researchers in the area. The reason behind this is not only to differentiate between easy and hard planning instances, but also to use polynomial-time solvable instances in order to construct better heuristic functions and improve planners. We identify a new class of tractable cost-optimal planning instances by restricting the causal graph. We study the computational complexity of oversubscription planning (such as the net-benefit problem) under various restrictions and reveal strong connections with classical planning. Inspired by this, we present a method for compiling oversubscription planning problems into the ordinary plan existence problem. We further study the parameterized complexity of cost-optimal and net-benefit planning under the same restrictions and show that the choice of numeric domain for the action costs has a great impact on the parameterized complexity. We finally consider the parameterized complexity of certain problems related to partial-order planning. In some applications, less restricted plans than total-order plans are needed. Therefore, a partial-order plan is being used instead. When dealing with partial-order plans, one important question is how to achieve optimal partial order plans, i.e. having the highest degree of freedom according to some notion of flexibility. We study several optimization problems for partial-order plans, such as finding a minimum deordering or reordering, and finding the minimum parallel execution length.

Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press, 2017. 35 p.
Series
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1854
National Category
Computer Systems
Identifiers
urn:nbn:se:liu:diva-136280 (URN)10.3384/diss.diva-136280 (DOI)978-91-7685-519-5 (ISBN)
Public defence
2017-06-16, Ada Lovelace, B-hus, Linköping University, SE-58183 Linköping, Linköping, 13:15 (English)
Opponent
Supervisors
Funder
CUGS (National Graduate School in Computer Science)
Available from: 2017-05-17 Created: 2017-04-05 Last updated: 2017-09-01Bibliographically approved

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

Total: 306 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf