Correlation Complexity of Classical Planning Domains
Authors: Jendrik Seipp, Florian Pommerening, Gabriele Röger, Malte Helmert
IJCAI 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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. We now begin our case studies of planning domains. Towards this end, we first establish some general properties of potential heuristics, concluding in two criteria to show that a task has correlation complexity at least 2. We next show that the algorithm terminates by returning a plan (rather than failing or not terminating). Because h is descending, an improving state is always found inside the for loop, so the while loop never fails. Moreover, the while loop must finish with a bounded number of iterations because h(s) decreases in every iteration and hence the sequence of expanded states never repeats. This proves that the algorithm terminates and also establishes the stated bound on L. (Note that h(s) is an integer and hence must decrease by at least 1 in every iteration.) |
| Researcher Affiliation | Academia | University of Basel Basel, Switzerland {jendrik.seipp,florian.pommerening,gabriele.roeger,malte.helmert}@unibas.ch |
| Pseudocode | Yes | Algorithm 1 Simple hill-climbing. |
| Open Source Code | No | The paper does not include an unambiguous statement that the authors are releasing source code for the methodology described in this paper, nor does it provide a direct link to a code repository. |
| Open Datasets | No | The paper is theoretical and uses classical planning domains as case studies for analytical proofs rather than empirical datasets for training or evaluation. Therefore, it does not mention public datasets or provide access information. |
| Dataset Splits | No | The paper is theoretical and does not describe empirical experiments that would involve dataset splits for training, validation, or testing. Therefore, no such split information is provided. |
| Hardware Specification | No | The paper is theoretical and does not describe empirical experiments that would require specific hardware. Therefore, no hardware specifications are provided. |
| Software Dependencies | No | The paper is theoretical and does not describe empirical experiments that would require specific software dependencies with version numbers. Therefore, no such details are provided. |
| Experiment Setup | No | The paper is theoretical and focuses on mathematical analysis and proofs, not empirical experiments. Therefore, it does not provide details about experimental setup, hyperparameters, or system-level training settings. |