Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • 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
A Multi-parameter Complexity Analysis of Cost-optimal and Net-benefit Planning
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)
2016 (engelsk)Inngår i: Twenty-Sixth International Conference on Automated Planning and Scheduling King's College, London June 12, 2016 – June 17, 2016 / [ed] Amanda Coles, Andrew Coles, Stefan Edelkamp, Daniele Magazzeni, Scott Sanner, AAAI Press, 2016, s. 2-10Konferansepaper, Publicerat paper (Fagfellevurdert)
Abstract [en]

Aghighi and Bäckström have previously studied cost-optimal planning (COP) and net-benefit planning (NBP) for three action cost domains: the positive integers (Z_+), the non-negative integers (Z_0) and the positive rationals (Q_+). These were indistinguishable under standard complexity analysis for both problems, but separated for COP using parameterised complexity analysis. With the plan cost, k, as parameter, COP was W[2]-complete for Z_+, but para-NP-hard for both Z_0 and Q_+, i.e. presumably much harder. NBP was para-NP-hard for all three domains, thus remaining unseparable. We continue by considering combinations with several additional parameters and also the non-negative rationals (Q_0). Examples of new parameters are the plan length, l, and the largest denominator of the action costs, d. Our findings include: (1) COP remains W[2]-hard for all domains, even if combining all parameters; (2) COP for Z_0 is in W[2] for the combined parameter {k,l}; (3) COP for Q_+ is in W[2] for {k,d} and (4) COP for Q_0 is in W[2] for {k,d,l}. For NBP we consider further additional parameters, where the most crucial one for reducing complexity is the sum of variable utilities. Our results help to understand the previous results, eg. the separation between Z_+ and Q_+ for COP, and to refine the previous connections with empirical findings.

sted, utgiver, år, opplag, sider
AAAI Press, 2016. s. 2-10
Emneord [en]
cost-optimal planning, parameterised complexity, numeric domains
HSV kategori
Identifikatorer
URN: urn:nbn:se:liu:diva-136278ISBN: 9781577357575 (tryckt)OAI: oai:DiVA.org:liu-136278DiVA, id: diva2:1087081
Konferanse
Twenty-Sixth International Conference on Automated Planning and Scheduling (ICAPS-16), London, UK, June 12–17, 2016
Tilgjengelig fra: 2017-04-05 Laget: 2017-04-05 Sist oppdatert: 2019-05-08bibliografisk 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: 2017-09-01bibliografisk kontrollert

Open Access i DiVA

A Multi-parameter Complexity Analysis of Cost-optimal and Net-benefit Planning(572 kB)2 nedlastinger
Filinformasjon
Fil FULLTEXT02.pdfFilstørrelse 572 kBChecksum SHA-512
e051bef9fd27dc2b5da1598ac56ecbebaa2ab08823ada79b7132be04bb45234f1c4d61eb969f37c4396a059e7ac07db6b9b7e32913e5e1e06e947d72a4f4e926
Type fulltextMimetype application/pdf

Andre lenker

Link to the complete proceedings

Søk i DiVA

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

Søk utenfor DiVA

GoogleGoogle Scholar
Totalt: 2 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: 936 treff
RefereraExporteraLink to record
Permanent link

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