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
Algorithms and Limits for Compact Plan Representations
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)
2012 (English)In: The journal of artificial intelligence research, ISSN 1076-9757, E-ISSN 1943-5037, Vol. 44, 141-177 p.Article in journal (Refereed) Published
Abstract [en]

Compact representations of objects is a common concept in computer science. Automated planning can be viewed as a case of this concept: a planning instance is a compact implicit representation of a graph and the problem is to find a path (a plan) in this graph. While the graphs themselves are represented compactly as planning instances, the paths are usually represented explicitly as sequences of actions. Some cases are known where the plans always have compact representations, for example, using macros. We show that these results do not extend to the general case, by proving a number of bounds for compact representations of plans under various criteria, like efficient sequential or random access of actions. In addition to this, we show that our results have consequences for what can be gained from reformulating planning into some other problem. As a contrast to this we also prove a number of positive results, demonstrating restricted cases where plans do have useful compact representations, as well as proving that macro plans have favourable access properties. Our results are finally discussed in relation to other relevant contexts.

Place, publisher, year, edition, pages
Association for the Advancement of Artificial Intelligence / AI Access Foundation , 2012. Vol. 44, 141-177 p.
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:liu:diva-78591DOI: 10.1613/jair.3534ISI: 000304405200001OAI: oai:DiVA.org:liu-78591DiVA: diva2:534129
Available from: 2012-06-15 Created: 2012-06-15 Last updated: 2017-12-07

Open Access in DiVA

fulltext(408 kB)200 downloads
File information
File name FULLTEXT01.pdfFile size 408 kBChecksum SHA-512
e16e2e5e802b8e7210b0457ed30ac41e0abc6d0d45ec6a695c0e9704f6177ec3563aae15f15f62abe8659937ff67e838bf4095c53f22555b37929c036d5e87d5
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Bäckström, ChristerJonsson, Peter
By organisation
Software and SystemsThe Institute of Technology
In the same journal
The journal of artificial intelligence research
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
Total: 200 downloads
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

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 116 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