New perspectives on cost partitioning for optimal classical planning

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

Available under License CC BY-NC (Attribution-NonCommercial).


Official URL: http://edoc.unibas.ch/diss/DissB_12463

Downloads: Statistics Overview


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 well-known 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 non-negative 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.
Operator-counting 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 operator-counting 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 operator-counting 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 operator-counting and potential heuristics are closely related to cost partitioning. They offer a new look on cost-partitioned 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
Number of Pages:1 Online-Ressource (x, 202 Seiten)
Identification Number:
edoc DOI:
Last Modified:05 Apr 2018 17:36
Deposited On:12 Mar 2018 15:34

Repository Staff Only: item control page