liu.seSearch for publications in DiVA
Change search
Link to record
Permanent link

Direct link
BETA
Bäckström, Christer
Alternative names
Publications (10 of 37) Show all publications
Aghighi, M. & Bäckström, C. (2016). A Multi-parameter Complexity Analysis of Cost-optimal and Net-benefit Planning. In: Amanda Coles, Andrew Coles, Stefan Edelkamp, Daniele Magazzeni, Scott Sanner (Ed.), Twenty-Sixth International Conference on Automated Planning and Scheduling King's College, London June 12, 2016 – June 17, 2016: . Paper presented at Twenty-Sixth International Conference on Automated Planning and Scheduling (ICAPS-16), London, UK, June 12–17, 2016 (pp. 2-10). AAAI Press
Open this publication in new window or tab >>A Multi-parameter Complexity Analysis of Cost-optimal and Net-benefit Planning
2016 (English)In: 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, p. 2-10Conference paper, Published paper (Refereed)
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.

Place, publisher, year, edition, pages
AAAI Press, 2016
Keywords
cost-optimal planning, parameterised complexity, numeric domains
National Category
Computer Systems
Identifiers
urn:nbn:se:liu:diva-136278 (URN)9781577357575 (ISBN)
Conference
Twenty-Sixth International Conference on Automated Planning and Scheduling (ICAPS-16), London, UK, June 12–17, 2016
Available from: 2017-04-05 Created: 2017-04-05 Last updated: 2019-05-08Bibliographically approved
Bäckström, C., Jonsson, P., Ordyniak, S. & Szeider, S. (2015). A complete parameterized complexity analysis of bounded planning. Journal of computer and system sciences (Print), 81(7), 1311-1332
Open this publication in new window or tab >>A complete parameterized complexity analysis of bounded planning
2015 (English)In: Journal of computer and system sciences (Print), ISSN 0022-0000, E-ISSN 1090-2724, Vol. 81, no 7, p. 1311-1332Article in journal (Refereed) Published
Abstract [en]

The propositional planning problem is a notoriously difficult computational problem, which remains hard even under strong syntactical and structural restrictions. Given its difficulty it becomes natural to study planning in the context of parameterized complexity. In this paper we continue the work initiated by Downey, Fellows and Stege on the parameterized complexity of planning with respect to the parameter "length of the solution plan." We provide a complete classification of the parameterized complexity of the planning problem under two of the most prominent syntactical restrictions, i.e., the so called PUBS restrictions introduced by Backstrom and Nebel and restrictions on the number of preconditions and effects as introduced by Bylander. We also determine which of the considered fixed-parameter tractable problems admit a polynomial kernel and which do not. (C) 2015 Elsevier Inc. All rights reserved.

Place, publisher, year, edition, pages
Elsevier, 2015
Keywords
Complexity of automated planning; Parameterized complexity; Kernelization
National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:liu:diva-120202 (URN)10.1016/j.jcss.2015.04.002 (DOI)000356644600014 ()
Note

Funding Agencies|European Research Council [239962]; Employment of Newly Graduated Doctors of Science for Scientific Excellence [CZ.1.07/2.3.00/30.0009]; Austrian Science Fund [P 26200]

Available from: 2015-07-21 Created: 2015-07-20 Last updated: 2018-01-11
Aghighi, M. & Bäckström, C. (2015). Cost-optimal and Net-benefit Planning: A Parameterised Complexity View. In: 24th International Joint Conference on Artificial Intelligence (IJCAI-15): . Paper presented at 24th International Joint Conference on Artificial Intelligence (IJCAI-15), Buenos Aires, Argentina, Jul 25-31, 2015 (pp. 1487-1493). IJCAI-INT JOINT CONF ARTIF INTELL, ALBERT-LUDWIGS UNIV FREIBURG GEORGES-KOHLER-ALLEE, INST INFORMATIK, GEB 052, FREIBURG, D-79110, GERMANY
Open this publication in new window or tab >>Cost-optimal and Net-benefit Planning: A Parameterised Complexity View
2015 (English)In: 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, p. 1487-1493Conference paper, Published paper (Refereed)
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.

Place, publisher, year, edition, pages
IJCAI-INT JOINT CONF ARTIF INTELL, ALBERT-LUDWIGS UNIV FREIBURG GEORGES-KOHLER-ALLEE, INST INFORMATIK, GEB 052, FREIBURG, D-79110, GERMANY, 2015
National Category
Transport Systems and Logistics
Identifiers
urn:nbn:se:liu:diva-128181 (URN)000442637801080 ()9781577357384 (ISBN)
Conference
24th International Joint Conference on Artificial Intelligence (IJCAI-15), Buenos Aires, Argentina, Jul 25-31, 2015
Funder
CUGS (National Graduate School in Computer Science), 1054Swedish Research Council, 621- 2014-4086
Available from: 2016-05-20 Created: 2016-05-20 Last updated: 2019-07-03Bibliographically approved
Bäckström, C. (2015). Some Fixed Parameter Tractability Results for Planning with Non-Acyclic Domain-Transition Graphs. In: Twenty-Ninth AAAI Conference on Artificial Intelligence (AAAI-2015): . Paper presented at Twenty-Ninth AAAI Conference on Artificial Intelligence (AAAI-2015). AAAI Press
Open this publication in new window or tab >>Some Fixed Parameter Tractability Results for Planning with Non-Acyclic Domain-Transition Graphs
2015 (English)In: Twenty-Ninth AAAI Conference on Artificial Intelligence (AAAI-2015), AAAI Press, 2015Conference paper, Published paper (Refereed)
Abstract [en]

Bäckström studied the parameterised complexity of planning when the domain-transition graphs (DTGs) are acyclic. He used the parameters d (domain size), k (number of paths in the DTGs) and w (treewidth of the causal graph), and showed that planning is fixed-parameter tractable (fpt) in these parameters, and fpt in only parameter k if the causal graph is a polytree. We continue this work by considering some additional cases of non-acyclic DTGs. In particular, we consider the case where each strongly connected component (SCC) in a DTG must be a simple cycle, and we show that planning is fpt for this case if the causal graph is a polytree. This is done by first preprocessing the instance to construct an equivalent abstraction and then apply B¨ackstr¨oms technique to this abstraction. We use the parameters d and k, reinterpreting this as the number of paths in the condensation of a DTG, and the two new parameters c (the number of contracted cycles along a path) and pmax (an upper bound for walking around cycles, when not unbounded).

Place, publisher, year, edition, pages
AAAI Press, 2015
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-129207 (URN)978-1-57735-698-1 (ISBN)
Conference
Twenty-Ninth AAAI Conference on Artificial Intelligence (AAAI-2015)
Available from: 2016-06-13 Created: 2016-06-13 Last updated: 2018-01-10
Bäckström, C., Jonsson, A. & Jonsson, P. (2014). Automaton Plans. The journal of artificial intelligence research, 51, 255-291
Open this publication in new window or tab >>Automaton Plans
2014 (English)In: The journal of artificial intelligence research, ISSN 1076-9757, E-ISSN 1943-5037, Vol. 51, p. 255-291Article in journal (Refereed) Published
Abstract [en]

Macros have long been used in planning to represent subsequences of operators. Macros can be used in place of individual operators during search, sometimes reducing the effort required to find a plan to the goal. Another use of macros is to compactly represent long plans. In this paper we introduce a novel solution concept called automaton plans in which plans are represented using hierarchies of automata. Automaton plans can be viewed as an extension of macros that enables parameterization and branching. We provide several examples that illustrate how automaton plans can be useful, both as a compact representation of exponentially long plans and as an alternative to sequential solutions in benchmark domains such as LOGISTICS and GRID. We also compare automaton plans to other compact plan representations from the literature, and find that automaton plans are strictly more expressive than macros, but strictly less expressive than HTNs and certain representations allowing efficient sequential access to the operators of the plan.

Place, publisher, year, edition, pages
AI ACCESS FOUNDATION, 2014
National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:liu:diva-112193 (URN)10.1613/jair.4391 (DOI)000343090300001 ()
Available from: 2014-11-18 Created: 2014-11-18 Last updated: 2018-01-11
Bäckström, C. (2014). Parameterising the Complexity of Planning by the Number of Paths in the Domain-transition Graphs. In: Proceedings of the 21st European Conference on Artificial Intelligence (ECAI-14): . Paper presented at 21st European Conference on Artificial Intelligence (ECAI-14) (pp. 33-38). IOS Press
Open this publication in new window or tab >>Parameterising the Complexity of Planning by the Number of Paths in the Domain-transition Graphs
2014 (English)In: Proceedings of the 21st European Conference on Artificial Intelligence (ECAI-14), IOS Press, 2014, p. 33-38Conference paper, Published paper (Refereed)
Abstract [en]

We apply the theory of parameterised complexity to planning, using the concept of fixed-parameter tractability (fpt) which is more relaxed than the usual tractability concept. The parameter we focus on is the maximal number of paths in the domain-transition graphs, and we show that for this parameter, optimal planning is fpt for planning instances with polytree causal graphs and acyclic domain-transition graphs. If this parameter is combined with the additional parameters of domain size for the variables and the treewidth of the causal graph, then planning is fpt also for instances with arbitrary causal graphs. Furthermore, all these parameters are fpt to test in advance. These results also imply that delete-relaxed planning is fpt, even in its recent generalisation to non-binary variables.

Place, publisher, year, edition, pages
IOS Press, 2014
Series
Frontiers in Artificial Intelligence and Applications, ISSN 0922-6389 ; 263
National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:liu:diva-112907 (URN)10.3233/978-1-61499-419-0-33 (DOI)000349444700007 ()978-1-61499-418-3 (ISBN)
Conference
21st European Conference on Artificial Intelligence (ECAI-14)
Available from: 2014-12-19 Created: 2014-12-19 Last updated: 2018-01-11
Bäckström, C. & Jonsson, P. (2013). A Refined View of Causal Graphs and Component Sizes: SP-Closed Graph Classes and Beyond. The journal of artificial intelligence research, 47, 575-611
Open this publication in new window or tab >>A Refined View of Causal Graphs and Component Sizes: SP-Closed Graph Classes and Beyond
2013 (English)In: The journal of artificial intelligence research, ISSN 1076-9757, E-ISSN 1943-5037, Vol. 47, p. 575-611Article in journal (Refereed) Published
Abstract [en]

The causal graph of a planning instance is an important tool for planning both in practice and in theory. The theoretical studies of causal graphs have largely analysed the computational complexity of planning for instances where the causal graph has a certain structure, often in combination with other parameters like the domain size of the variables. Chen and Giménez ignored even the structure and considered only the size of the weakly connected components. They proved that planning is tractable if the components are bounded by a constant and otherwise intractable. Their intractability result was, however, conditioned by an assumption from parameterised complexity theory that has no known useful relationship with the standard complexity classes. We approach the same problem from the perspective of standard complexity classes, and prove that planning is NP-hard for classes with unbounded components under an additional restriction we refer to as SP-closed. We then argue that most NP-hardness theorems for causal graphs are difficult to apply and, thus, prove a more general result; even if the component sizes grow slowly and the class is not densely populated with graphs, planning still cannot be tractable unless the polynomial hierachy collapses. Both these results still hold when restricted to the class of acyclic causal graphs. We finally give a partial characterization of the borderline between NP-hard and NP-intermediate classes, giving further insight into the problem.

Place, publisher, year, edition, pages
AAAI Press, 2013
National Category
Engineering and Technology
Identifiers
urn:nbn:se:liu:diva-96717 (URN)10.1613/jair.3968 (DOI)000322433700001 ()
Available from: 2013-08-23 Created: 2013-08-23 Last updated: 2017-12-06
Bäckström, C. & Jonsson, P. (2013). Bridging the Gap Between Refinement and Heuristics in Abstraction. In: IJCAI'13 Proceedings of the Twenty-Third international joint conference on Artificial Intelligence: . Paper presented at 23rd International Joint Conference on Artificial Intelligence (IJCAI-2013), (pp. 2261-2267). AAAI Press
Open this publication in new window or tab >>Bridging the Gap Between Refinement and Heuristics in Abstraction
2013 (English)In: IJCAI'13 Proceedings of the Twenty-Third international joint conference on Artificial Intelligence, AAAI Press, 2013, p. 2261-2267Conference paper, Published paper (Refereed)
Abstract [en]

There are two major uses of abstraction in planning and search: refinement (where abstract solutions are extended into concrete solutions) and heuristics (where abstract solutions are used to compute heuristics for the original search space). These two approaches are usually viewed as unrelated in the literature. It is reasonable to believe, though, that they are related, since they are both intrinsically based on the structure of abstract search spaces. We take the first steps towards formally investigating their relationships, employing our recently introduced framework for analysing and comparing abstraction methods. By adding some mechanisms for expressing metric properties, we can capture concepts like admissibility and consistency of heuristics. We present an extensive study of how such metric properties relate to the properties in the original framework, revealing a number of connections between the refinement and heuristic approaches. This also provides new insights into, for example, Valtorta's theorem and spurious states.

Place, publisher, year, edition, pages
AAAI Press, 2013
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-102661 (URN)978-1-57735-633-2 (ISBN)
Conference
23rd International Joint Conference on Artificial Intelligence (IJCAI-2013),
Available from: 2013-12-18 Created: 2013-12-18 Last updated: 2018-01-11Bibliographically approved
Bäckström, C., Jonsson, P. & Ståhlberg, S. (2013). Fast Detection of Unsolvable Planning Instances Using Local Consistency. In: Proceedings of the Sixth International Symposium on Combinatorial Search: . Paper presented at 6th Annual Symposium on Combinatorial Search (SoCS-2013), 11-13 July 2013, Leavenworth, WA, USA (pp. 29-37). AAAI Press
Open this publication in new window or tab >>Fast Detection of Unsolvable Planning Instances Using Local Consistency
2013 (English)In: Proceedings of the Sixth International Symposium on Combinatorial Search, AAAI Press, 2013, p. 29-37Conference paper, Published paper (Refereed)
Abstract [en]

There has been a tremendous advance in domain-independent planning over the past decades, and planners have become increasingly efficient at finding plans. However, this has not been paired by any corresponding improvement in detecting unsolvable instances. Such instances are obviously important but largely neglected in planning. In other areas, such as constraint solving and model checking, much effort has been spent on devising methods for detecting unsolvability. We introduce a method for detecting unsolvable planning instances that is loosely based on consistency checking in constraint programming. Our method balances completeness against efficiency through a parameter k: the algorithm identifies more unsolvable instances but takes more time for increasing values of k. We present empirical data for our algorithm and some standard planners on a number of unsolvable instances, demonstrating that our method can be very efficient where the planners fail to detect unsolvability within reasonable resource bounds. We observe that planners based on the h^m heuristic or pattern databases are better than other planners for detecting unsolvability. This is not a coincidence since there are similarities (but also significant differences) between our algorithm and these two heuristic methods.

Place, publisher, year, edition, pages
AAAI Press, 2013
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-102667 (URN)978-1-57735-632-5 (ISBN)
Conference
6th Annual Symposium on Combinatorial Search (SoCS-2013), 11-13 July 2013, Leavenworth, WA, USA
Available from: 2013-12-18 Created: 2013-12-18 Last updated: 2018-01-11Bibliographically approved
Bäckström, C., Jonsson, P., Ordyniak, S. & Szeider, S. (2013). Parameterized Complexity and Kernel Bounds for Hard Planning Problems. In: Paul G. Spirakis & Maria Serna (Ed.), Algorithms and Complexity: 8th International Conference, CIAC 2013, Barcelona, Spain, May 22-24, 2013. Proceedings. Paper presented at 8th International Conference, CIAC 2013, Barcelona, Spain, May 22-24, 2013 (pp. 13-24). Springer Berlin/Heidelberg
Open this publication in new window or tab >>Parameterized Complexity and Kernel Bounds for Hard Planning Problems
2013 (English)In: Algorithms and Complexity: 8th International Conference, CIAC 2013, Barcelona, Spain, May 22-24, 2013. Proceedings / [ed] Paul G. Spirakis & Maria Serna, Springer Berlin/Heidelberg, 2013, p. 13-24Conference paper, Published paper (Refereed)
Abstract [en]

The propositional planning problem is a notoriously difficult computational problem. Downey et al. (1999) initiated the parameterized analysis of planning (with plan length as the parameter) and Bäckström et al. (2012) picked up this line of research and provided an extensive parameterized analysis under various restrictions, leaving open only one stubborn case. We continue this work and provide a full classification. In particular, we show that the case when actions have no preconditions and at most e postconditions is fixed-parameter tractable if e ≤ 2 and W[1]-complete otherwise. We show fixed-parameter tractability by a reduction to a variant of the Steiner Tree problem; this problem has been shown fixed-parameter tractable by Guo et al. (2007). If a problem is fixed-parameter tractable, then it admits a polynomial-time self-reduction to instances whose input size is bounded by a function of the parameter, called the kernel. For some problems, this function is even polynomial which has desirable computational implications. Recent research in parameterized complexity has focused on classifying fixed-parameter tractable problems on whether they admit polynomial kernels or not. We revisit all the previously obtained restrictions of planning that are fixed-parameter tractable and show that none of them admits a polynomial kernel unless the polynomial hierarchy collapses to its third level.

Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2013
Series
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 7878
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-102659 (URN)10.1007/978-3-642-38233-8_2 (DOI)978-3-642-38232-1 (ISBN)978-3-642-38233-8 (ISBN)
Conference
8th International Conference, CIAC 2013, Barcelona, Spain, May 22-24, 2013
Available from: 2013-12-18 Created: 2013-12-18 Last updated: 2018-01-30Bibliographically approved
Organisations

Search in DiVA

Show all publications