@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}
}

{"_id":"JWCLSW6XaYFEud9ww","bibbaseid":"aghighi-bckstrm-amultiparametercomplexityanalysisofcostoptimalandnetbenefitplanning","downloads":1,"creationDate":"2016-03-09T03:04:31.942Z","title":"A Multi-Parameter Complexity Analysis of Cost-Optimal and Net-Benefit Planning","author_short":["Aghighi, M.","Bäckström, C."],"year":null,"bibtype":"inproceedings","biburl":"icaps16.icaps-conference.org/papers.bib","bibdata":{"bibtype":"inproceedings","type":"inproceedings","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":[{"firstnames":["Meysam"],"propositions":[],"lastnames":["Aghighi"],"suffixes":[]},{"firstnames":["Christer"],"propositions":[],"lastnames":["Bäckström"],"suffixes":[]}],"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","bibtex":"@inproceedings {icaps16-111,\r\n track = {​Main Track},\r\n title = {A Multi-Parameter Complexity Analysis of Cost-Optimal and Net-Benefit Planning},\r\n url = {http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13001},\r\n author = {Meysam Aghighi and Christer Bäckström},\r\n abstract = {Aghighi and Bäckström studied cost-optimal planning (COP)\r\nand net-benefit planning (NBP) for three different number\r\ndomains, the positive integers (Z+), the non-negative\r\nintegers (Z0) and the positive rationals (Q+). These are\r\nindistinguishable under standard complexity analysis for\r\nboth COP and NBP, but were separated for COP by using\r\nparameterised complexity analysis. Using the plan cost,k, \r\nas parameter, COP was found W[2]-complete for Z+, but\r\npara-NP-hard for both Z0 and Q+, i.e. presumably much\r\nharder. NBP was found para-NP-hard for all three domains,\r\nthus remaining unseparable. We refine their analysis by\r\nconsidering combinations with several additional\r\nparameters and also the non-negative rationals (Q0).\r\nExamples of new parameters are the plan length, l, and the\r\nlargest denominator of the action costs, d. Some of our\r\nfindings are:\r\n(1)~COP remains W[2]-hard for all domains, even if combining \r\nall parameters;\r\n(2)~COP for Z0 is in W[2] for the combined parameter <k,l>;\r\n(3)~COP for Q+ is in W[2] for the combined parameter<k,d> and\r\n(4)~COP for Q0 is in W[2] for the combined parameter<k,d,l>.\r\nFor NBP we consider further additional parameters, where\r\nthe most crucial one for reducing complexity is the sum of\r\nvariable utilities, t. Our results help to further\r\nunderstand the previous results, eg. the separation\r\nbetween Z+ and Q+ for COP, and they also refine the\r\nprevious connections with empirical findings.},\r\n keywords = {Classical planning,Complexity analysis}\r\n}\r\n\r\n","author_short":["Aghighi, M.","Bäckström, C."],"key":"icaps16-111","id":"icaps16-111","bibbaseid":"aghighi-bckstrm-amultiparametercomplexityanalysisofcostoptimalandnetbenefitplanning","role":"author","urls":{"Paper":"http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13001"},"keyword":["Classical planning","Complexity analysis"],"metadata":{"authorlinks":{}},"downloads":1,"html":""},"search_terms":["multi","parameter","complexity","analysis","cost","optimal","net","benefit","planning","aghighi","bäckström"],"keywords":["classical planning","complexity analysis"],"authorIDs":[],"dataSources":["iMkx859KiXcegwsin"]}