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

Direct link
Some Fixed Parameter Tractability Results for Planning with Non-Acyclic Domain-Transition Graphs
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering. (TCSLAB)
Number of Authors: 1
2015 (English)In: Twenty-Ninth AAAI Conference on Artificial Intelligence (AAAI-2015), 2015Conference paper (Refereed)
Abstract [en]

Bäckström studied the parameterised complexity of planning when the domain-transition graphs (DTGs) are acyclic. He used the parameters d (domain size), k (number of paths in the DTGs) and w (treewidth of the causal graph), and showed that planning is fixed-parameter tractable (fpt) in these parameters, and fpt in only parameter k if the causal graph is a polytree. We continue this work by considering some additional cases of non-acyclic DTGs. In particular, we consider the case where each strongly connected component (SCC) in a DTG must be a simple cycle, and we show that planning is fpt for this case if the causal graph is a polytree. This is done by first preprocessing the instance to construct an equivalent abstraction and then apply B¨ackstr¨oms technique to this abstraction. We use the parameters d and k, reinterpreting this as the number of paths in the condensation of a DTG, and the two new parameters c (the number of contracted cycles along a path) and pmax (an upper bound for walking around cycles, when not unbounded).

Place, publisher, year, edition, pages
National Category
Computer Science
URN: urn:nbn:se:liu:diva-129207ISBN: 978-1-57735-698-1OAI: diva2:936187
Twenty-Ninth AAAI Conference on Artificial Intelligence (AAAI-2015)
Available from: 2016-06-13 Created: 2016-06-13 Last updated: 2016-06-23

Open Access in DiVA

No full text

Other links

Search in DiVA

By author/editor
Bäckström, Christer
By organisation
Software and SystemsFaculty of Science & Engineering
Computer Science

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: 3 hits
ReferencesLink to record
Permanent link

Direct link