Cost-Optimal and Net-Benefit Planning — A Parameterised Complexity View
Authors: Meysam Aghighi, Christer Bäckström
IJCAI 2015 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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. |
| Researcher Affiliation | Academia | Meysam Aghighi and Christer B ackstr om Link oping University, Link oping, Sweden meysam.aghighi@liu.se christer.backstrom@liu.se |
| Pseudocode | No | The paper includes 'Construction' sections (e.g., Construction 4, Construction 13) that describe how instances are built for proofs, but these are prose descriptions and not formatted as pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any statement or link regarding the release of open-source code for the methodology described. |
| Open Datasets | No | This is a theoretical paper focused on complexity analysis and does not involve training models on datasets. |
| Dataset Splits | No | This is a theoretical paper focused on complexity analysis and does not involve dataset splits for validation. |
| Hardware Specification | No | This is a theoretical paper focused on complexity analysis and does not describe any experiments that would require hardware specifications. |
| Software Dependencies | No | This is a theoretical paper focused on complexity analysis and does not describe any experiments that would require specific software dependencies with version numbers. |
| Experiment Setup | No | This is a theoretical paper focused on complexity analysis and does not describe any experimental setup details or hyperparameters. |