Cost-optimal and Net-benefit Planning--A Parameterised Complexity View
2015 (English)In: 24th International Joint Conference on Artificial Intelligence (IJCAI-15), 2015Conference paper (Refereed)
Cost-optimal planning (COP) uses action costs and asks for a minimum-cost plan. It is sometimes assumed that there is no harm in using actions with zero cost or rational cost. Classical complexity analysis does not contradict this assumption; planning is PSPACE-complete regardless of whether action costs are positive or non-negative, integer or rational. We thus apply parameterised complexity analysis to shed more light on this issue. Our main results are the following. COP is W-complete for positive integer costs, i.e. it is no harder than finding a minimum-length plan, but it is para-NPhard if the costs are non-negative integers or positive rationals. This is a very strong indication that the latter cases are substantially harder. Net-benefit planning (NBP) additionally assigns goal utilities and asks for a plan with maximum difference between its utility and its cost. NBP is para-NP-hard even when action costs and utilities are positive integers, suggesting that it is harder than COP. In addition, we also analyse a large number of subclasses, using both the PUBS restrictions and restricting the number of preconditions and effects.
Place, publisher, year, edition, pages
Transport Systems and Logistics
IdentifiersURN: urn:nbn:se:liu:diva-128181OAI: oai:DiVA.org:liu-128181DiVA: diva2:929808
24th International Joint Conference on Artificial Intelligence (IJCAI-15)
FunderCUGS (National Graduate School in Computer Science), 1054Swedish Research Council, 621- 2014-4086