---
title: "In Search of Tractability for Partial Satisfaction Planning"
authors:
  - "Michael Katz"
  - "Vitaly Mirkis"
doi: ""
url: "https://ijcai.org/proceedings/2016/447"
pdf: "https://ijcai.org/proceedings/2016/0447.pdf"
venue: "Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence"
year: 2016
pages: "3154-3159"
track: ""
keywords:
---

# In Search of Tractability for Partial Satisfaction Planning

Michael Katz, Vitaly Mirkis

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

## Abstract

The objective of partial satisfaction planning is to achieve an as valuable as possible state, tacking into account the cost of its achievement. In this work we investigate the computational complexity of restricted fragments of two variants of partial satisfaction: net-benefit and oversubscription planning. In particular, we examine restrictions on the causal graph structure and variable domain size of the planning problem, and show that even for the strictest such restrictions, optimal oversubscription planning is hard. In contrast, certain tractability results previously obtained for classical planning also apply to net-benefit planning. We then partially relax these restrictions in order to find the boundary of tractability for both variants of partial satisfaction planning. In addition, for the family of $0$-binary value functions we show a strong connection between the complexity of cost-optimal classical and optimal oversubscription planning.