A Multi-Parameter Complexity Analysis of Cost-Optimal and Net-Benefit Planning. Aghighi, M. & Bäckström, C. In
A Multi-Parameter Complexity Analysis of Cost-Optimal and Net-Benefit Planning [link]Paper  abstract   bibtex   1 download  
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: 1