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

Direct link
Parameterising the Complexity of Planning by the Number of Paths in the Domain-transition Graphs
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology. (TCSLAB)
Number of Authors: 1
2014 (English)In: Proceedings of the 21st European Conference on Artificial Intelligence (ECAI-14), IOS Press, 2014, 33-38 p.Conference paper (Refereed)
Abstract [en]

We apply the theory of parameterised complexity to planning, using the concept of fixed-parameter tractability (fpt) which is more relaxed than the usual tractability concept. The parameter we focus on is the maximal number of paths in the domain-transition graphs, and we show that for this parameter, optimal planning is fpt for planning instances with polytree causal graphs and acyclic domain-transition graphs. If this parameter is combined with the additional parameters of domain size for the variables and the treewidth of the causal graph, then planning is fpt also for instances with arbitrary causal graphs. Furthermore, all these parameters are fpt to test in advance. These results also imply that delete-relaxed planning is fpt, even in its recent generalisation to non-binary variables.

Place, publisher, year, edition, pages
IOS Press, 2014. 33-38 p.
, Frontiers in Artificial Intelligence and Applications, ISSN 0922-6389 ; 263
National Category
Computer and Information Science
URN: urn:nbn:se:liu:diva-112907DOI: 10.3233/978-1-61499-419-0-33ISI: 000349444700007ISBN: 978-1-61499-418-3OAI: diva2:773667
21st European Conference on Artificial Intelligence (ECAI-14)
Available from: 2014-12-19 Created: 2014-12-19 Last updated: 2016-06-22

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Bäckström, Christer
By organisation
Software and SystemsThe Institute of Technology
Computer and Information 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

Altmetric score

Total: 51 hits
ReferencesLink to record
Permanent link

Direct link