In

Paper abstract bibtex

Paper abstract bibtex

Aghighi and Bäckström studied cost-optimal planning (COP) and net-benefit planning (NBP) for three different number domains, the positive integers (Z+), the non-negative integers (Z0) and the positive rationals (Q+). These are indistinguishable under standard complexity analysis for both COP and NBP, but were separated for COP by using parameterised complexity analysis. Using the plan cost,k, as parameter, COP was found W[2]-complete for Z+, but para-NP-hard for both Z0 and Q+, i.e. presumably much harder. NBP was found para-NP-hard for all three domains, thus remaining unseparable. We refine their analysis by considering combinations with several additional parameters and also the non-negative rationals (Q0). Examples of new parameters are the plan length, l, and the largest denominator of the action costs, d. Some of our findings are: (1)~COP remains W[2]-hard for all domains, even if combining all parameters; (2)~COP for Z0 is in W[2] for the combined parameter ; (3)~COP for Q+ is in W[2] for the combined parameter and (4)~COP for Q0 is in W[2] for the combined parameter. For NBP we consider further additional parameters, where the most crucial one for reducing complexity is the sum of variable utilities, t. Our results help to further understand the previous results, eg. the separation between Z+ and Q+ for COP, and they also refine the previous connections with empirical findings.

@inproceedings {icaps16-111, track = {Main Track}, title = {A Multi-Parameter Complexity Analysis of Cost-Optimal and Net-Benefit Planning}, url = {http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13001}, author = {Meysam Aghighi and Christer Bäckström}, abstract = {Aghighi and Bäckström studied cost-optimal planning (COP) and net-benefit planning (NBP) for three different number domains, the positive integers (Z+), the non-negative integers (Z0) and the positive rationals (Q+). These are indistinguishable under standard complexity analysis for both COP and NBP, but were separated for COP by using parameterised complexity analysis. Using the plan cost,k, as parameter, COP was found W[2]-complete for Z+, but para-NP-hard for both Z0 and Q+, i.e. presumably much harder. NBP was found para-NP-hard for all three domains, thus remaining unseparable. We refine their analysis by considering combinations with several additional parameters and also the non-negative rationals (Q0). Examples of new parameters are the plan length, l, and the largest denominator of the action costs, d. Some of our findings are: (1)~COP remains W[2]-hard for all domains, even if combining all parameters; (2)~COP for Z0 is in W[2] for the combined parameter <k,l>; (3)~COP for Q+ is in W[2] for the combined parameter<k,d> and (4)~COP for Q0 is in W[2] for the combined parameter<k,d,l>. For NBP we consider further additional parameters, where the most crucial one for reducing complexity is the sum of variable utilities, t. Our results help to further understand the previous results, eg. the separation between Z+ and Q+ for COP, and they also refine the previous connections with empirical findings.}, keywords = {Classical planning,Complexity analysis} }

Downloads: 0