Publication
IJCAI 2016
Conference paper

In Search of Tractability for Partial Satisfaction Planning

Download paper

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.

Date

Publication

IJCAI 2016

Authors

Topics

Share