liu.seSök publikationer i DiVA
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Complexity of state-variable planning under structural restrictions
Linköpings universitet, Institutionen för datavetenskap. Linköpings universitet, Tekniska högskolan.ORCID-id: 0000-0002-5288-3330
1995 (Engelska)Licentiatavhandling, monografi (Övrigt vetenskapligt)
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.

Ort, förlag, år, upplaga, sidor
Linköping: Univ. , 1995. , s. 114
Serie
Linköping Studies in Science and Technology. Thesis, ISSN 0280-7971 ; 478
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
URN: urn:nbn:se:liu:diva-163515Lokalt ID: LiU-Tek-Lic 1995:10ISBN: 9178715083 (tryckt)OAI: oai:DiVA.org:liu-163515DiVA, id: diva2:1392114
Tillgänglig från: 2020-02-06 Skapad: 2020-02-06 Senast uppdaterad: 2020-02-06Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Personposter BETA

Jonsson, Peter

Sök vidare i DiVA

Av författaren/redaktören
Jonsson, Peter
Av organisationen
Institutionen för datavetenskapTekniska högskolan
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetricpoäng

isbn
urn-nbn
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf