---
title: "Cost-Optimal and Net-Benefit Planning - A Parameterised Complexity View"
authors:
  - "Meysam Aghighi"
  - "Christer Bäckström"
doi: ""
url: "https://ijcai.org/proceedings/2015/213"
pdf: "https://ijcai.org/proceedings/2015/0213.pdf"
venue: "Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence"
year: 2015
pages: "1487-1492"
track: "Main Track"
keywords:
---

# Cost-Optimal and Net-Benefit Planning - A Parameterised Complexity View

Meysam Aghighi, Christer Bäckström

*Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence*, pages 1487-1492.

## Abstract

Cost-optimal planning (COP) uses action costs and asks for a minimum-cost plan. It is sometimes assumed that there is no harm in using actions with zero cost or rational cost. Classical complexity analysis does not contradict this assumption; planning is PSPACE-complete regardless of whether action costs are positive or non-negative, integer or rational. We thus apply parameterised complexity analysis to shed more light on this issue. Our main results are the following. COP is [W2]-complete for positive integer costs, i.e. it is no harder than finding a minimum-length plan, but it is paraNP-hard 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 paraNP-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.