Fixed-Parameter Tractable Reductions to SAT for Planning

de Haan, Ronald; Kronegger, Martin; Pfandler, Andreas

Fixed-Parameter Tractable Reductions to SAT for Planning

Ronald de Haan, Martin Kronegger, Andreas Pfandler

Download BibTeX Cite

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Special Track on Knowledge Representation and Reasoning. Pages 2897-2902.

Abstract

Planning is an important AI task that gives rise to many hard problems. In order to come up with efficient algorithms for this setting, it is important to understand the sources of complexity. For planning problems that are beyond NP, identifying fragments that allow an efficient reduction to SAT can be a feasible approach due to the great performance of modern SAT solvers. In this paper, we use the framework of parameterized complexity theory to obtain a more fine-grained complexity analysis of natural planning problems beyond NP. With this analysis we are able to point out several variants of planning where the structure in the input makes encodings into SAT feasible. We complement these positive results with some hardness results and a new machine characterization for the intractability class exists * for allk-W[P].

Ronald de Haan, Martin Kronegger, and Andreas Pfandler. 2015. Fixed-Parameter Tractable Reductions to SAT for Planning. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15. IJCAI, 2897–2902. https://ijcai.org/proceedings/2015/410

@inproceedings{ijcai2015p410,
  title     = {Fixed-Parameter Tractable Reductions to SAT for Planning},
  author    = {de Haan, Ronald and Kronegger, Martin and Pfandler, Andreas},
  booktitle = {Proceedings of the Twenty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-15}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Qiang Yang and Michael Wooldridge},
  pages     = {2897--2902},
  year      = {2015},
  month     = {7},
  note      = {Special Track on Knowledge Representation and Reasoning},
  url       = {https://ijcai.org/proceedings/2015/410},
}

TY  - CPAPER
TI  - Fixed-Parameter Tractable Reductions to SAT for Planning
AU  - de Haan, Ronald
AU  - Kronegger, Martin
AU  - Pfandler, Andreas
T2  - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2015
SP  - 2897
EP  - 2902
UR  - https://ijcai.org/proceedings/2015/410
ER  -