About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
IJCAI 2016
Conference paper
In Search of Tractability for Partial Satisfaction Planning
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.