Saturated Cost Partitioning for Optimal Classical Planning

Seipp, Jendrik and Keller, Thomas and Helmert, Malte. (2020) Saturated Cost Partitioning for Optimal Classical Planning. Journal of Artificial Intelligence Research, 67. pp. 129-167.

Full text not available from this repository.

Official URL: https://edoc.unibas.ch/78717/

Downloads: Statistics Overview


Cost partitioning is a method for admissibly combining a set of admissible heuristic estimators by distributing operator costs among the heuristics. Computing an optimal cost partitioning, i.e., the operator cost distribution that maximizes the heuristic value, is often prohibitively expensive to compute. Saturated cost partitioning is an alternative that is much faster to compute and has been shown to yield high-quality heuristics. However, its greedy nature makes it highly susceptible to the order in which the heuristics are considered. We propose a greedy algorithm to generate orders and show how to use hill-climbing search to optimize a given order. Combining both techniques leads to significantly better heuristic estimates than using the best random order that is generated in the same time. Since there is often no single order that gives good guidance on the whole state space, we use the maximum of multiple orders as a heuristic that is significantly better informed than any single-order heuristic, especially when we actively search for a set of diverse orders.
Faculties and Departments:05 Faculty of Science > Departement Mathematik und Informatik > Informatik > Artificial Intelligence (Helmert)
UniBasel Contributors:Seipp, Jendrik and Keller, Thomas and Helmert, Malte
Item Type:Article, refereed
Article Subtype:Research Article
Publisher:AI Access Foundation
Note:Publication type according to Uni Basel Research Database: Journal article
Identification Number:
Last Modified:03 Nov 2021 15:51
Deposited On:03 Nov 2021 15:51

Repository Staff Only: item control page