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

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • 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
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, Published 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.
Series
Frontiers in Artificial Intelligence and Applications, ISSN 0922-6389 ; 263
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:liu:diva-112907DOI: 10.3233/978-1-61499-419-0-33ISI: 000349444700007ISBN: 978-1-61499-418-3 (print)OAI: oai:DiVA.org:liu-112907DiVA: diva2:773667
Conference
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

Authority records BETA

Bäckström, Christer

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

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 60 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • 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