Pommerening, Florian. New perspectives on cost partitioning for optimal classical planning. 2017, Doctoral Thesis, University of Basel, Faculty of Science.

PDF
Available under License CC BYNC (AttributionNonCommercial). 3379Kb 
Official URL: http://edoc.unibas.ch/diss/DissB_12463
Downloads: Statistics Overview
Abstract
Admissible heuristics are the main ingredient when solving classical planning tasks optimally with heuristic search. There are many such heuristics, and each has its own strengths and weaknesses. As higher admissible heuristic values are more accurate, the maximum over several admissible heuristics dominates each individual one. Operator cost partitioning is a wellknown technique to combine admissible heuristics in a way that dominates their maximum and remains admissible. But are there better options to combine the heuristics? We make three main contributions towards this question:
Extensions to the cost partitioning framework can produce higher estimates from the same set of heuristics. Cost partitioning traditionally uses nonnegative cost functions. We prove that this restriction is not necessary, and that allowing negative values as well makes the framework more powerful: the resulting heuristic values can be exponentially higher, and unsolvability can be detected even if all component heuristics have a finite value. We also generalize operator cost partitioning to transition cost partitioning, which can differentiate between different contexts in which an operator is used.
Operatorcounting heuristics reason about the number of times each operator is used in a plan. Many existing heuristics can be expressed in this framework, which gives new theoretical insight into their relationship. Different operatorcounting heuristics can be easily combined within the framework in a way that dominates their maximum.
Potential heuristics compute a heuristic value as a weighted sum over state features and are a fast alternative to operatorcounting heuristics. Admissible and consistent potential heuristics for certain feature sets can be described in a compact way which means that the best heuristic from this class can be extracted in polynomial time.
Both operatorcounting and potential heuristics are closely related to cost partitioning. They offer a new look on costpartitioned heuristics and already sparked research beyond their use as classical planning heuristics.
Extensions to the cost partitioning framework can produce higher estimates from the same set of heuristics. Cost partitioning traditionally uses nonnegative cost functions. We prove that this restriction is not necessary, and that allowing negative values as well makes the framework more powerful: the resulting heuristic values can be exponentially higher, and unsolvability can be detected even if all component heuristics have a finite value. We also generalize operator cost partitioning to transition cost partitioning, which can differentiate between different contexts in which an operator is used.
Operatorcounting heuristics reason about the number of times each operator is used in a plan. Many existing heuristics can be expressed in this framework, which gives new theoretical insight into their relationship. Different operatorcounting heuristics can be easily combined within the framework in a way that dominates their maximum.
Potential heuristics compute a heuristic value as a weighted sum over state features and are a fast alternative to operatorcounting heuristics. Admissible and consistent potential heuristics for certain feature sets can be described in a compact way which means that the best heuristic from this class can be extracted in polynomial time.
Both operatorcounting and potential heuristics are closely related to cost partitioning. They offer a new look on costpartitioned heuristics and already sparked research beyond their use as classical planning heuristics.
Advisors:  Helmert, Malte and Beck, Christopher 

Faculties and Departments:  05 Faculty of Science > Departement Mathematik und Informatik > Informatik > Artificial Intelligence (Helmert) 
UniBasel Contributors:  Pommerening, Florian and Helmert, Malte 
Item Type:  Thesis 
Thesis Subtype:  Doctoral Thesis 
Thesis no:  12463 
Thesis status:  Complete 
Bibsysno:  Link to catalogue 
Number of Pages:  1 OnlineRessource (x, 202 Seiten) 
Language:  English 
Identification Number: 

Last Modified:  05 Apr 2018 17:36 
Deposited On:  12 Mar 2018 15:34 
Repository Staff Only: item control page