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
Complexity of state-variable planning under structural restrictions
Linköping University, Department of Computer and Information Science. Linköping University, The Institute of Technology.ORCID iD: 0000-0002-5288-3330
1995 (English)Licentiate thesis, monograph (Other academic)
Abstract [en]

Computationally tractable planning problems reported in the literature have almost exclusively been defined by syntactical restrictions. To better exploit the inherent structure in problems, it is probably necessary to study also structural restrictions on the underlying state-transition graph. Such restrictions are typically hard to test since this graph is of exponential size. We propose an intermediate approach, using a state variable model for planning and defining restrictions on the state-transition graph for each state variable in isolation. We identify such restrictions which are tractable to test and we present a planning algorithm which is correct and runs in polynomial time under these restrictions.Moreover, we present an exhaustive map over the complexity results for planning under all combinations of four previously studied syntactical restrictions and our five new structural restrictions. This complexity map considers both the bounded and unbounded plan generation problem. Finally, we extend a provably correct, polynomial-time planner to plan for a miniature assembly line, which assembles toy cars. Although somewhat limited, this process has many similarities with real industrial processes.

Place, publisher, year, edition, pages
Linköping: Univ. , 1995. , p. 114
Series
Linköping Studies in Science and Technology. Thesis, ISSN 0280-7971 ; 478
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:liu:diva-163515Local ID: LiU-Tek-Lic 1995:10ISBN: 9178715083 (print)OAI: oai:DiVA.org:liu-163515DiVA, id: diva2:1392114
Available from: 2020-02-06 Created: 2020-02-06 Last updated: 2020-02-06Bibliographically approved

Open Access in DiVA

No full text in DiVA

Search in DiVA

By author/editor
Jonsson, Peter
By organisation
Department of Computer and Information ScienceThe Institute of Technology
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
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