liu.seSearch for publications in DiVA
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Cost-optimal and Net-benefit Planning: A Parameterised Complexity View
Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska fakulteten. (TCSLAB)
Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska fakulteten. (TCSLAB)
2015 (engelsk)Inngår i: 24th International Joint Conference on Artificial Intelligence (IJCAI-15), IJCAI-INT JOINT CONF ARTIF INTELL, ALBERT-LUDWIGS UNIV FREIBURG GEORGES-KOHLER-ALLEE, INST INFORMATIK, GEB 052, FREIBURG, D-79110, GERMANY , 2015, s. 1487-1493Konferansepaper, Publicerat paper (Fagfellevurdert)
Abstract [en]

Cost-optimal planning (COP) uses action costs and asks for a minimum-cost plan. It is sometimes assumed that there is no harm in using actions with zero cost or rational cost. Classical complexity analysis does not contradict this assumption; planning is PSPACE-complete regardless of whether action costs are positive or non-negative, integer or rational. We thus apply parameterised complexity analysis to shed more light on this issue. Our main results are the following. COP is W[2]-complete for positive integer costs, i.e. it is no harder than finding a minimum-length plan, but it is para-NPhard if the costs are non-negative integers or positive rationals. This is a very strong indication that the latter cases are substantially harder. Net-benefit planning (NBP) additionally assigns goal utilities and asks for a plan with maximum difference between its utility and its cost. NBP is para-NP-hard even when action costs and utilities are positive integers, suggesting that it is harder than COP. In addition, we also analyse a large number of subclasses, using both the PUBS restrictions and restricting the number of preconditions and effects.

sted, utgiver, år, opplag, sider
IJCAI-INT JOINT CONF ARTIF INTELL, ALBERT-LUDWIGS UNIV FREIBURG GEORGES-KOHLER-ALLEE, INST INFORMATIK, GEB 052, FREIBURG, D-79110, GERMANY , 2015. s. 1487-1493
HSV kategori
Identifikatorer
URN: urn:nbn:se:liu:diva-128181ISI: 000442637801080ISBN: 9781577357384 (tryckt)OAI: oai:DiVA.org:liu-128181DiVA, id: diva2:929808
Konferanse
24th International Joint Conference on Artificial Intelligence (IJCAI-15), Buenos Aires, Argentina, Jul 25-31, 2015
Forskningsfinansiär
CUGS (National Graduate School in Computer Science), 1054Swedish Research Council, 621- 2014-4086Tilgjengelig fra: 2016-05-20 Laget: 2016-05-20 Sist oppdatert: 2019-07-03bibliografisk kontrollert
Inngår i avhandling
1. Computational Complexity of some Optimization Problems in Planning
Åpne denne publikasjonen i ny fane eller vindu >>Computational Complexity of some Optimization Problems in Planning
2017 (engelsk)Doktoravhandling, med artikler (Annet vitenskapelig)
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.

sted, utgiver, år, opplag, sider
Linköping: Linköping University Electronic Press, 2017. s. 35
Serie
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1854
HSV kategori
Identifikatorer
urn:nbn:se:liu:diva-136280 (URN)10.3384/diss.diva-136280 (DOI)978-91-7685-519-5 (ISBN)
Disputas
2017-06-16, Ada Lovelace, B-hus, Linköping University, SE-58183 Linköping, Linköping, 13:15 (engelsk)
Opponent
Veileder
Forskningsfinansiär
CUGS (National Graduate School in Computer Science)
Tilgjengelig fra: 2017-05-17 Laget: 2017-04-05 Sist oppdatert: 2019-10-11bibliografisk kontrollert

Open Access i DiVA

fulltext(240 kB)66 nedlastinger
Filinformasjon
Fil FULLTEXT01.pdfFilstørrelse 240 kBChecksum SHA-512
3b9ee36fad84d762b989f449fb5b2b1b867aea6e420fb3cfeceed24db7bfa522af5cde92e316a605e4f31703174fbbb357479b49da4a448e738d5331b669b80d
Type fulltextMimetype application/pdf

Personposter BETA

Aghighi, MeysamBäckström, Christer

Søk i DiVA

Av forfatter/redaktør
Aghighi, MeysamBäckström, Christer
Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar
Totalt: 66 nedlastinger
Antall nedlastinger er summen av alle nedlastinger av alle fulltekster. Det kan for eksempel være tidligere versjoner som er ikke lenger tilgjengelige

isbn
urn-nbn

Altmetric

isbn
urn-nbn
Totalt: 918 treff
RefereraExporteraLink to record
Permanent link

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