---
title: "Correlation Complexity of Classical Planning Domains"
authors:
  - "Jendrik Seipp"
  - "Florian Pommerening"
  - "Gabriele Röger"
  - "Malte Helmert"
doi: ""
url: "https://ijcai.org/proceedings/2016/459"
pdf: "https://ijcai.org/proceedings/2016/0459.pdf"
venue: "Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence"
year: 2016
pages: "3242-3249"
track: ""
keywords:
---

# Correlation Complexity of Classical Planning Domains

Jendrik Seipp, Florian Pommerening, Gabriele Röger, Malte Helmert

*Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence*, pages 3242-3249.

## Abstract

We analyze how complex a heuristic function must be to directly guide a state-space search algorithm towards the goal. As a case study, we examine functions that evaluate states with a weighted sum of state features. We measure the complexity of a domain by the complexity of the required features. We analyze conditions under which the search algorithm runs in polynomial time and show complexity results for several classical planning domains.