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
Computational Complexity of some Optimization Problems in Planning
Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska fakulteten. (TCSLAB)
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: urn:nbn:se:liu:diva-136280DOI: 10.3384/diss.diva-136280ISBN: 978-91-7685-519-5 (tryckt)OAI: oai:DiVA.org:liu-136280DiVA, id: diva2:1087096
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
Delarbeid
1. Oversubscription planning: Complexity and compilability
Åpne denne publikasjonen i ny fane eller vindu >>Oversubscription planning: Complexity and compilability
2014 (engelsk)Inngår i: Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, AI Access Foundation , 2014, Vol. 3, s. 2221-2227Konferansepaper, Publicerat paper (Fagfellevurdert)
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.

sted, utgiver, år, opplag, sider
AI Access Foundation, 2014
HSV kategori
Identifikatorer
urn:nbn:se:liu:diva-116727 (URN)2-s2.0-84908192348 (Scopus ID)9781577356790 (ISBN)
Konferanse
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
Tilgjengelig fra: 2015-04-09 Laget: 2015-04-02 Sist oppdatert: 2018-01-11
2. Tractable Cost-Optimal Planning over Restricted Polytree Causal Graphs
Åpne denne publikasjonen i ny fane eller vindu >>Tractable Cost-Optimal Planning over Restricted Polytree Causal Graphs
2015 (engelsk)Inngår i: Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, AAAI Press, 2015Konferansepaper, Publicerat paper (Fagfellevurdert)
Abstract [en]

Causal graphs are widely used to analyze the complexity of planning problems. Many tractable classes have been identified with their aid and state-of-the-art heuristics have been derived by exploiting such classes. In particular, Katz and Keyder have studied causal graphs that are hourglasses (which is a generalization of forks and inverted-forks) and shown that the corresponding cost-optimal planning problem is tractable under certain restrictions. We continue this work by studying polytrees (which is a generalization of hourglasses) under similar restrictions. We prove tractability of cost-optimal planning by providing an algorithm based on a novel notion of variable isomorphism. Our algorithm also sheds light on the k-consistency procedure for identifying unsolvable planning instances. We speculate that this may, at least partially, explain why merge-and-shrink heuristics have been successful for recognizing unsolvable instances.

sted, utgiver, år, opplag, sider
AAAI Press, 2015
Serie
Proceedings of the AAAI Conference on Artificial Intelligence, ISSN 2159-5399, E-ISSN 2374-3468
Emneord
automated planning, causal graph, polynomial-time algorithm, cost-optimal planning, polytree
HSV kategori
Identifikatorer
urn:nbn:se:liu:diva-118729 (URN)978-1-57735-703-2 (ISBN)
Konferanse
29th AAAI Conference on Artificial Intelligence (AAAI-15), January 25–30, Austin, TX, USA
Forskningsfinansiär
CUGS (National Graduate School in Computer Science)
Tilgjengelig fra: 2015-06-03 Laget: 2015-06-03 Sist oppdatert: 2017-05-17
3. Cost-optimal and Net-benefit Planning: A Parameterised Complexity View
Åpne denne publikasjonen i ny fane eller vindu >>Cost-optimal and Net-benefit Planning: A Parameterised Complexity View
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
HSV kategori
Identifikatorer
urn:nbn:se:liu:diva-128181 (URN)000442637801080 ()9781577357384 (ISBN)
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-4086
Tilgjengelig fra: 2016-05-20 Laget: 2016-05-20 Sist oppdatert: 2019-07-03bibliografisk kontrollert
4. A Multi-parameter Complexity Analysis of Cost-optimal and Net-benefit Planning
Åpne denne publikasjonen i ny fane eller vindu >>A Multi-parameter Complexity Analysis of Cost-optimal and Net-benefit Planning
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
Emneord
cost-optimal planning, parameterised complexity, numeric domains
HSV kategori
Identifikatorer
urn:nbn:se:liu:diva-136278 (URN)9781577357575 (ISBN)
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
5. Plan Reordering and Parallel Execution -- A Parameterized Complexity View
Åpne denne publikasjonen i ny fane eller vindu >>Plan Reordering and Parallel Execution -- A Parameterized Complexity View
2017 (engelsk)Konferansepaper, Publicerat paper (Fagfellevurdert)
Abstract [en]

Bäckström has previously studied a number of optimization problems for partial-order plans, like finding a minimum deordering (MCD) or reordering (MCR), and finding the minimum parallel execution length (PPL), which are all NP-complete. We revisit these problems, but applying parameterized complexity analysis rather than standard complexity analysis. We consider various parameters, including both the original and desired size of the plan order, as well as its width and height. Our findings include that MCD and MCR are W[2]-hard and in W[P] when parameterized with the desired order size, and MCD is fixed-parameter tractable (fpt) when parameterized with the original order size. Problem PPL is fpt if parameterized with the size of the non-concurrency relation, but para-NP-hard in most other cases. We also consider this problem when the number (k) of agents, or processors, is restricted, finding that this number is a crucial parameter; this problem is fixed-parameter tractable with the order size, the parallel execution length and k as parameter, but para-NP-hard without k as parameter.

sted, utgiver, år, opplag, sider
AAAI Press, 2017
Emneord
Partially ordered plan, Parameterized complexity, Complexity of planning, Plan reordering, Parallel plan execution
HSV kategori
Identifikatorer
urn:nbn:se:liu:diva-136279 (URN)
Konferanse
Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17)
Tilgjengelig fra: 2017-04-05 Laget: 2017-04-05 Sist oppdatert: 2017-05-17bibliografisk kontrollert

Open Access i DiVA

omslag(79 kB)45 nedlastinger
Filinformasjon
Fil COVER01.pdfFilstørrelse 79 kBChecksum SHA-512
004ed6f8dfa766c973f60f0bc2428043eb0033c8c71c966d3fef6155569ed5fd85b7037718726ab6e135db49f58c48b82c1b307d0274b25334da8c93706130a5
Type coverMimetype application/pdf
fulltext(574 kB)374 nedlastinger
Filinformasjon
Fil FULLTEXT03.pdfFilstørrelse 574 kBChecksum SHA-512
24d982905e0d1c0f2b9766f1b13101013d8edfc96abc4017b0865b39505745748c39a9dcf67573b0e9ce68f36117d22dbe350284d81a8c1cd5991178e6b49349
Type fulltextMimetype application/pdf
Bestill online >>

Andre lenker

Forlagets fulltekst

Søk i DiVA

Av forfatter/redaktør
Aghighi, Meysam
Av organisasjonen

Søk utenfor DiVA

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

doi
isbn
urn-nbn

Altmetric

doi
isbn
urn-nbn
Totalt: 4776 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