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
All PSPACE-complete Planning Problems are Equal but some are more Equal than Others
Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
2011 (English)In: Proceedings, The Fourth International Symposium on Combinatorial Search (SoCS-2011) / [ed] Daniel Borrajo, Maxim Likhachev, Carlos Linares Lopez, AAAI Press, 2011, 10-17 p.Conference paper, Published paper (Refereed)
Abstract [en]

Complexity analysis of planning is problematic. Even very simple planning languages are PSPACE-complete, yet cannot model many simple problems naturally. Many languages with much more powerful features are also PSPACE-complete. It is thus difficult to separate planning languages in a useful way and to get complexity figures that better reflect reality.This paper introduces new methods for complexity analysis of planning and similar combinatorial search problems, in order to achieve more precision and complexity separations than standard methods allow. Padding instances with the solution size yields a complexity measure that is immune to this factor and reveals other causes of hardness, that are otherwise hidden. Further combining this method with limited nondeterminism improves the precision, making even finer separations possible. We demonstrate with examples how these methods can narrow the gap between theory and practice.

Place, publisher, year, edition, pages
AAAI Press, 2011. 10-17 p.
National Category
Computer Science
Identifiers
URN: urn:nbn:se:liu:diva-74505ISBN: 978-1-57735-537-3 (print)ISBN: 978-1-57735-538-0 (print)OAI: oai:DiVA.org:liu-74505DiVA: diva2:486162
Conference
Fourth Annual Symposium on Combinatorial Search (SoCS-2011), July 15–16, Barcelona, Spain
Available from: 2012-01-30 Created: 2012-01-30 Last updated: 2017-02-23Bibliographically approved

Open Access in DiVA

No full text

Authority records BETA

Bäckström, ChristerJonsson, Peter

Search in DiVA

By author/editor
Bäckström, ChristerJonsson, Peter
By organisation
TCSLAB - Theoretical Computer Science LaboratoryThe Institute of Technology
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 84 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