Christer Bäckström

I am an associate professor at TCSLAB (the Theoretical Computer Science Lab) at the Department of Computer and Information Science at Linköping University, Sweden.

Email: christer.backstrom@liu.se


Recent Publications

Christer Bäckström, Peter Jonsson and Sebastian Ordyniak
Novel Structural Parameters for Acyclic Planning Using Tree Embeddings
In proc. 27th International Joint Conference on Artificial Intelligence (IJCAI-2018), Stockholm, Sweden, Jul. 2018, pp. 4653-4659. (link)

Christer Bäckström, Peter Jonsson and Sebastian Ordyniak
A Refined Understanding of Cost-optimal Planning with Polytree Causal Graphs
In proc. 11th Annual Symposium on Combinatorial Search (SoCS-2018), Jul. 2018, Stockholm, Sweden, pp. 19-27. Best Paper Award. (pdf)

Christer Bäckström and Peter Jonsson.
Time and Space Bounds for Planning
Journal of Artificial Intelligence Research, vol. 60, 2017, pp. 595-638 (link)

Meysam Aghighi and Christer Bäckström.
Plan Reordering and Parallel Execution -- A Parameterized Complexity View
In proc. 31st AAAI Conference on Artificial Intelligence (AAAI-2017), San Fransisco, CA, USA, Feb. 2017, pp. 3540-3546. (link)

Meysam Aghighi, Christer Bäckström, Peter Jonsson and Simon Ståhlberg.
Refining complexity analyses in planning by exploiting the exponential time hypothesis
Annals of Mathematics and Artificial Intelligence, 78(2): 157-175 (2016). (link)

Meysam Aghighi, Christer Bäckström, Peter Jonsson and Simon Ståhlberg.
Analysing Approximability and Heuristics in Planning Using the Exponential-time Hypothesis
In proc. 22nd European Conference on Artificial Intelligence (ECAI-2016), the Hague, Holland, Aug. 2016, pp. 184-192. (link)

Christer Bäckström and Peter Jonsson.
Upper and Lower Time and Space Bounds for Planning
In proc. 22nd European Conference on Artificial Intelligence (ECAI-2016), the Hague, Holland, Aug. 2016, pp. 716-724. (link)

Meysam Aghighi and Christer Bäckström.
A Multi-parameter Complexity Analysis of Cost-optimal and Net-benefit Planning
In proc. 26th International Conference on Automated Planning and Scheduling (ICAPS-2016), London, UK, Jun. 2016, pp. 2-10. (pdf)

Meysam Aghighi and Christer Bäckström.
Cost-optimal and Net-benefit Planning--A Parameterised Complexity View
In proc. 24th International Joint Conference on Artificial Intelligence (IJCAI-2015), Buenos Aires, Argentina, Jul. 2015, pp. 1487-1493. (pdf)

Christer Bäckström, Peter Jonsson, Sebastian Ordyniak and Stefan Szeider.
A Complete Parameterized Complexity Analysis of Bounded Planning
Journal of Computer and System Science, 81(7): 1311-1332 (2015). (link)

Christer Bäckström.
Some Fixed Parameter Tractability Results for Planning with Non-acyclic Domain-transition Graphs
In proc. 29th AAAI Conference on Artificial Intelligence (AAAI-2015), Austin, TX, USA, Jan. 2015. (pdf)

Christer Bäckström, Anders Jonsson and Peter Jonsson.
Automaton Plans
Journal of Artificial Intelligence Research, vol. 51, 2014, pp. 255-291. (pdf)

Christer Bäckström.
Parameterising the Complexity of Planning by the Number of Paths in the Domain-transition Graphs
In proc. 21st European Conference on Artificial Intelligence (ECAI-14), Prague, Czech Republic, Aug. 2014, pp. 33-38. (pdf)

Christer Bäckström and Peter Jonsson.
Bridging the Gap Between Refinement and Heuristics in Abstraction
In proc. 23rd International Joint Conference on Artificial Intelligence (IJCAI-2013), Beijing, China, Aug. 2013, pp. 2261-2267. (pdf)

Christer Bäckström and Peter Jonsson.
A Refined View of Causal Graphs and Component Sizes: SP-closed Graph Classes and Beyond
Journal of Artificial Intelligence Research, vol. 47, 2013, pp. 575-611. (pdf)

Christer Bäckström, Peter Jonsson and Simon Ståhlberg
Fast Detection of Unsolvable Planning Instances Using Local Consistency
In proc. 6th International Symposium on Combinatorial Search (SoCS-13) Leavenworth, WA, USA, July 2013, pp. 29-37. (pdf)

Christer Bäckström, Peter Jonsson, Sebastian Ordyniak and Stefan Szeider.
Parameterized Complexity and Kernel Bounds for Hard Planning Problems
In proc. 8th International Conference on Algorithms and Complexity (CIAC-13), Barcelona, Spain, May, 2013, pp. 13-24. (pdf)

Christer Bäckström, Anders Jonsson and Peter Jonsson.
Macros, Reactive Plans and Compact Representations
In proc. 20th European Conference on Artificial Intelligence (ECAI-12), Montpellier, France, Aug. 2012, pp. 85-90. (pdf)

Christer Bäckström, Anders Jonsson and Peter Jonsson.
From Macro Plans to Automata Plans
In proc. 20th European Conference on Artificial Intelligence (ECAI-12), Montpellier, France, Aug. 2012, pp. 91-96. (pdf)

Christer Bäckström and Peter Jonsson.
Abstracting Abstraction in Search II: Complexity Analysis
In proc. 5th International Symposium on Combinatorial Search (SoCS-12) Niagara Falls, ON, Canada, July 2012, pp. 10-17. (pdf)

Christer Bäckström, Yue Chen, Peter Jonsson, Sebastian Ordyniak and Stefan Szeider.
The Complexity of Planning Revisited--A Parameterized Analysis
In proc. 26th AAAI Conference on Artificial Intelligence (AAAI-12) Toronto, ON, Canada, July 2012, 1735-1741. (pdf)

Christer Bäckström and Peter Jonsson.
Algorithms and Limits for Compact Plan Representations
Journal of Artificial Intelligence Research, vol. 44, 2012, pp. 141-177. (pdf)

Christer Bäckström and Peter Jonsson.
Abstracting Abstraction in Search with Applications to Planning
In proc. 13th International Conference on Principles of Knowledge Representation and Reasoning (KR-12) Rome, Italy, June 2012, 446-456 (pdf)

Christer Bäckström and Peter Jonsson.
All PSPACE-complete Planning Problems are Equal but some are more Equal than Others
In proc. 4th International Symposium on Combinatorial Search (SoCS-11) Castell de Cardona, Barcelona, Spain, July 2011, pp. 10-17 . Best paper award. (pdf)

Christer Bäckström and Peter Jonsson.
Limits for Compact Representations of Plans
In proc. 21st International Conference on Automated Planning and Scheduling (ICAPS-11), Freiburg, Germany, June 2011, pp. 18-25 (pdf)



  • Old Publications

    1
    Peter Jonsson, Patrik Haslum, and Christer Bäckström. Towards efficient universal planning: A randomized approach. Artif. Intell., 117(1):1--29, 2000. (pdf)

    2
    Inger Klein, Peter Jonsson, and Christer Bäckström. Efficient planning for a miniature assembly line. Artificial Intelligence in Engineering, 13(1):69--81, 1999.

    3
    Peter Jonsson, Thomas Drakengren, and Christer Bäckström. Computational complexity of relating time points with intervals. Artif. Intell., 109(1-2):273--295, 1999. (pdf)

    4
    Peter Jonsson and Christer Bäckström. State-variable planning under structural restrictions: Algorithms and complexity. Artificial Intelligence, 100(1--2):125--176, 1998. (pdf)

    5
    Peter Jonsson and Christer Bäckström. A unifying approach to temporal constraint reasoning. Artificial Intelligence, 102(1):143--155, 1998.

    6
    Peter Jonsson and Christer Bäckström. Tractable plan existence does not imply tractable plan generation. Annals of Mathematics and Artificial Intelligence, 22(3,4):281--296, 1998. (pdf)

    7
    Christer Bäckström. Computational aspects of reordering plans. Journal of Artificial Intelligence Research, 9:99--137, 1998. (pdf)

    8
    Peter Jonsson and Christer Bäckström. On the size of reactive plans. In Proceedings of the 13th (US) National Conference on Artificial Intelligence (AAAI-96), pages 1182--1187, Portland, OR, USA, 1996. American Association for Artificial Intelligence. (pdf)

    9
    Peter Jonsson and Christer Bäckström. A linear-programming approach to temporal reasoning. In Proceedings of the 13th (US) National Conference on Artificial Intelligence (AAAI-96), pages 1235--1240, Portland, OR, USA, 1996. American Association for Artificial Intelligence. (pdf)

    10
    Peter Jonsson, Thomas Drakengren, and Christer Bäckström. Tractable subclasses of the point-interval algebra: A complete classification. In J. Doyle and L. Aiello, editors, Proceedings of the 5th International Conference on Principles on Knowledge Representation and Reasoning (KR-96), pages 352--363, Cambridge, MA, USA, 1996. Morgan Kaufmann. (pdf)

    11
    Peter Jonsson and Christer Bäckström. Tractable plan existence does not imply tractable plan generation. In 4th International Symposium of AI and Mathematics, Ft. Lauderdale, FL., USA, 1996. (pdf)

    12
    Inger Klein, Peter Jonsson, and Christer Bäckström. Automatic synthesis of control programs in polynomial time for an assembly line. In Proceedings of the IEEE Conference on Decision and Control (CDC-96), Kobe, Japan, 1996. (pdf)

    13
    Christer Bäckström. Expressive equivalence of planning formalisms. Artificial Intelligence, 76(1--2):17--34, 1995. ARTINT 1234. (pdf)

    14
    Christer Bäckström and Bernhard Nebel. Complexity results for SAS planning. Computational Intelligence, 11(4):625--655, 1995. (pdf)

    15
    Christer Bäckström and Peter Jonsson. Planning with abstraction hierarchies can be exponentially less efficient. In Chris Mellish, editor, Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI-95), pages 1599--1604, Montréal, PQ, Canada, 1995. Morgan Kaufmann. (pdf)

    16
    Christer Bäckström. Five years of tractable planning. In Malik Ghallab and Alfredo Milani, editors, New Directions in AI Planning: EWSP'95---3rd European Workshop on Planning, Frontiers in AI and Applications, pages 19--33, Assisi, Italy, 1995. IOS Press. (Invited paper). (pdf)

    17
    Peter Jonsson and Christer Bäckström. Incremental planning. In Malik Ghallab and Alfredo Milani, editors, New Directions in AI Planning: EWSP'95---3rd European Workshop on Planning, Frontiers in AI and Applications, pages 79--90, Assisi, Italy, 1995. IOS Press. (pdf)

    18
    Inger Klein, Peter Jonsson, and Christer Bäckström. Tractable planning for an assembly line. In Malik Ghallab and Alfredo Milani, editors, New Directions in AI Planning: EWSP'95---3rd European Workshop on Planning, Frontiers in AI and Applications, pages 313--324, Assisi, Italy, 1995. IOS Press. (pdf)

    19
    Christer Bäckström and Peter Jonsson. Planning with abstraction hierarchies can be exponentially less efficient. In Alon Levy and Pandurang Nayak, editors, Proceedings of the Symposium on Abstraction, Reformulation and Approximation, SARA-95, Ville d'Esterel, PQ, Canada, 1995. (Same paper as IJCAI'95).

    20
    Bernhard Nebel and Christer Bäckström. On the computational complexity of temporal projection, planning and plan validation. Artificial Intelligence, 66(1):125--160, 1994. ARTINT 1063. (pdf)

    21
    Peter Jonsson and Christer Bäckström. Tractable planning with state variables by exploiting structural restrictions. In Proceedings of the 12th (US) National Conference on Artificial Intelligence (AAAI-94), pages 998--1003, Seattle, WA, USA, 1994. American Association for Artificial Intelligence. (pdf)

    22
    Christer Bäckström. Planning using transformation between equivalent formalisms: A case study of efficiency. In David Wilkins, editor, Comparative Analysis of AI Planning Systems, 1994. (AAAI-94 Workshop). (pdf)

    23
    Christer Bäckström. Executing parallel plans faster by adding actions. In Anthony G. Cohn, editor, Proceedings of the 11th European Conference on Artificial Intelligence (ECAI-94), pages 615--619, Amsterdam, Netherlands, 1994. Wiley. (pdf)

    24
    Peter Jonsson and Christer Bäckström. Complexity results for state-variable planning under mixed syntactical and structural restrictions. In Philippe Jorrand, editor, Proceedings of the 6th International Conference on Artificial Intelligence: Methodology, Systems, Applications (AIMSA-94), Sofia, Bulgaria, 1994. World Scientific Publishing. (pdf)

    25
    Christer Bäckström and Bernhard Nebel. Complexity results for SAS planning. In Ruzena Bajcsy, editor, Proceedings of the 13th International Joint Conference on Artificial Intelligence (IJCAI-93), pages 1430--1435, Chambéry, France, 1993. Morgan Kaufmann. (pdf)

    26
    Christer Bäckström. Finding least constrained plans and optimal parallel executions is harder than we thought. In Christer Bäckström and Erik Sandewall, editors, Current Trends in AI Planning: EWSP'93---2nd European Workshop on Planning, pages 46--59, Vadstena, Sweden, 1993. IOS Press. (pdf)

    27
    Christer Bäckström. Tractable planning problems: A challenge for deductive planning. In Susanne Biundo and Richard Waldinger, editors, Deductive Approaches to Plan Generation and Plan Recognition, page 8, Schloss Dagstuhl, Wadern, Germany, 1993. Internationale Begegnungs- und Forschungszentrum für Informatik (IBFI). (All talks invited. Only abstracts published.).

    28
    Bernhard Nebel and Christer Bäckström. On the computational complexity of temporal projection and plan validation. In Proceedings of the 10th (US) National Conference on Artificial Intelligence (AAAI-92), pages 748--753, San Jos'e, CA, USA, 1992. (pdf)

    29
    Christer Bäckström and Bernhard Nebel. On the computational complexity of planning and story understanding. In Bernd Neumann, editor, Proceedings of the 10th European Conference on Artificial Intelligence (ECAI-92), pages 349--353, Vienna, Austria, 1992. Wiley. (pdf)

    30
    Christer Bäckström. Uncertainty and parallelism in action structures. In Gerd Grosse, editor, Beyond Sequential Planning, Vienna, Austria, 1992. (ECAI-92 Workshop).

    31
    Christer Bäckström and Inger Klein. Planning in polynomial time: The SAS-PUBS class. Computational Intelligence, 7(3):181--197, 1991. (pdf)

    32
    Christer Bäckström and Inger Klein. Parallel non-binary planning in polynomial time. In Ray Reiter and John Mylopoulos, editors, Proceedings of the 12th International Joint Conference on Artificial Intelligence (IJCAI-91), pages 268--273, Sydney, Australia, 1991. Morgan Kaufmann. (pdf)

    33
    Inger Klein and Christer Bäckström. On the planning problem in sequential control. In Proceedings of the 30th IEEE Conference on Decision and Control (CDC-91), pages 1819--1823, Brighton, UK, 1991. (pdf)

    34
    Christer Bäckström. Logical modelling of simplified geometrical objects and mechanical assembly processes. In Su-Shing Chen, editor, Advances in Spatial Reasoning, volume 1, pages 35--62, Norwood, NJ, 1990. Ablex.

    35
    Christer Bäckström and Inger Klein. Planning in polynomial time: Short paper. In Mary L Emrich et al., editors, Methodologies for Intelligent systems: Selected Papers, pages 125--129. International Center for the Application of Information Technology, Knoxville, TN, USA, 1990. Paper presented at the ISMIS'90 conference.

    36
    Christer Bäckström and Inger Klein. Planning in polynomial time. In G Gottlob and W Nejdl, editors, Expert Systems in Engineering: Principles and Applications. International Workshop, volume 462 of Lecture Notes in Artificial Intelligence, pages 103--118, Vienna, Austria, 1990. Springer.

    37
    Christer Bäckström. A representation of coordinated actions characterized by interval valued conditions. In Zbigniew W Ras and Lorenza Saitta, editors, Proceedings of the 3rd International Symposium on Methodologies for Intelligent systems (ISMIS-88), pages 220--229, Torino, Italy, 1988. North-Holland.

    38
    Christer Bäckström. Action structures with implicit coordination. In Tim O'Shea and Vasil Sgurev, editors, Proceedings of the 3rd International Conference on Artificial Intelligence: Methodology, Systems, Applications (AIMSA-88), pages 103--110, Varna, Bulgaria, 1988. North-Holland.

    39
    Christer Bäckström. A representation of coordinated actions. In Thore Danielsen, editor, Proceedings of the 1st Scandinavian Conference on Artificial Intelligence (SCAI-88), pages 205--220, Tromsø, Norway, 1988. IOS Press.

    40
    Christer Bäckström. Static and dynamic logical modelling of mechanical assembly processes in a simplified geometrical environment. In Avi Kak and Su-Shing Chen, editors, Spatial Reasoning and Multi-Sensor Fusion, Proceedings of the 1987 Workshop, St. Charles, IL, USA, 1987. Morgan Kaufmann.