Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • 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
Oversubscription planning: Complexity and compilability
Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska högskolan.
Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska högskolan.
2014 (Engelska)Ingår i: Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, AI Access Foundation , 2014, Vol. 3, 2221-2227 s.Konferensbidrag, Publicerat paper (Refereegranskat)
Abstract [en]

Many real-world planning problems are oversubscription problems where all goals are not simultaneously achievable and the planner needs to find a feasible subset. We present complexity results for the so-called partial satisfaction and net benefit problems under various restrictions; this extends previous work by van den Briel et al. Our results reveal strong connections between these problems and with classical planning. We also present a method for efficiently compiling oversubscription problems into the ordinary plan existence problem; this can be viewed as a continuation of earlier work by Keyder and Geffner.

Ort, förlag, år, upplaga, sidor
AI Access Foundation , 2014. Vol. 3, 2221-2227 s.
Nationell ämneskategori
Data- och informationsvetenskap
Identifikatorer
URN: urn:nbn:se:liu:diva-116727Scopus ID: 2-s2.0-84908192348ISBN: 9781577356790 (tryckt)OAI: oai:DiVA.org:liu-116727DiVA: diva2:801501
Konferens
28th AAAI Conference on Artificial Intelligence, AAAI 2014, 26th Innovative Applications of Artificial Intelligence Conference, IAAI 2014 and the 5th Symposium on Educational Advances in Artificial Intelligence, EAAI 2014
Tillgänglig från: 2015-04-09 Skapad: 2015-04-02 Senast uppdaterad: 2017-05-17
Ingår i avhandling
1. Computational Complexity of some Optimization Problems in Planning
Öppna denna publikation i ny flik eller fönster >>Computational Complexity of some Optimization Problems in Planning
2017 (Engelska)Doktorsavhandling, sammanläggning (Övrigt vetenskapligt)
Abstract [en]

Automated planning is known to be computationally hard in the general case. Propositional planning is PSPACE-complete and first-order planning is undecidable. One method for analyzing the computational complexity of planning is to study restricted subsets of planning instances, with the aim of differentiating instances with varying complexity. We use this methodology for studying the computational complexity of planning. Finding new tractable (i.e. polynomial-time solvable) problems has been a particularly important goal for researchers in the area. The reason behind this is not only to differentiate between easy and hard planning instances, but also to use polynomial-time solvable instances in order to construct better heuristic functions and improve planners. We identify a new class of tractable cost-optimal planning instances by restricting the causal graph. We study the computational complexity of oversubscription planning (such as the net-benefit problem) under various restrictions and reveal strong connections with classical planning. Inspired by this, we present a method for compiling oversubscription planning problems into the ordinary plan existence problem. We further study the parameterized complexity of cost-optimal and net-benefit planning under the same restrictions and show that the choice of numeric domain for the action costs has a great impact on the parameterized complexity. We finally consider the parameterized complexity of certain problems related to partial-order planning. In some applications, less restricted plans than total-order plans are needed. Therefore, a partial-order plan is being used instead. When dealing with partial-order plans, one important question is how to achieve optimal partial order plans, i.e. having the highest degree of freedom according to some notion of flexibility. We study several optimization problems for partial-order plans, such as finding a minimum deordering or reordering, and finding the minimum parallel execution length.

Ort, förlag, år, upplaga, sidor
Linköping: Linköping University Electronic Press, 2017. 35 s.
Serie
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1854
Nationell ämneskategori
Datorsystem
Identifikatorer
urn:nbn:se:liu:diva-136280 (URN)10.3384/diss.diva-136280 (DOI)978-91-7685-519-5 (ISBN)
Disputation
2017-06-16, Ada Lovelace, B-hus, Linköping University, SE-58183 Linköping, Linköping, 13:15 (Engelska)
Opponent
Handledare
Forskningsfinansiär
CUGS (National Graduate School in Computer Science)
Tillgänglig från: 2017-05-17 Skapad: 2017-04-05 Senast uppdaterad: 2017-09-01Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas

Scopus

Sök vidare i DiVA

Av författaren/redaktören
Aghighi, MeysamJonsson, Peter
Av organisationen
Programvara och systemTekniska högskolan
Data- och informationsvetenskap

Sök vidare utanför DiVA

GoogleGoogle Scholar

Totalt: 239 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • 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