Search: id:"swepub:oai:DiVA.org:liu-128181" >
Cost-optimal and Ne...
Cost-optimal and Net-benefit Planning : A Parameterised Complexity View
-
- Aghighi, Meysam, 1988- (author)
- Linköpings universitet,Programvara och system,Tekniska fakulteten,TCSLAB
-
- Bäckström, Christer (author)
- Linköpings universitet,Programvara och system,Tekniska fakulteten,TCSLAB
-
(creator_code:org_t)
- IJCAI-INT JOINT CONF ARTIF INTELL, ALBERT-LUDWIGS UNIV FREIBURG GEORGES-KOHLER-ALLEE, INST INFORMATIK, GEB 052, FREIBURG, D-79110, GERMANY, 2015
- 2015
- English.
-
In: 24th International Joint Conference on Artificial Intelligence (IJCAI-15). - : IJCAI-INT JOINT CONF ARTIF INTELL, ALBERT-LUDWIGS UNIV FREIBURG GEORGES-KOHLER-ALLEE, INST INFORMATIK, GEB 052, FREIBURG, D-79110, GERMANY. - 9781577357384 ; , s. 1487-1493
- Related links:
-
https://liu.diva-por... (primary) (Raw object)
-
show more...
-
https://urn.kb.se/re...
-
show less...
Abstract
Subject headings
Close
- 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[2]-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.
Subject headings
- TEKNIK OCH TEKNOLOGIER -- Samhällsbyggnadsteknik -- Transportteknik och logistik (hsv//swe)
- ENGINEERING AND TECHNOLOGY -- Civil Engineering -- Transport Systems and Logistics (hsv//eng)
Publication and Content Type
- ref (subject category)
- kon (subject category)
Find in a library
To the university's database