edoc

Narrowing the Gap Between Saturated and Optimal Cost Partitioning for Classical Planning

Seipp, Jendrik and Keller, Thomas and Helmert, Malte. (2017) Narrowing the Gap Between Saturated and Optimal Cost Partitioning for Classical Planning. In: Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI 2017). pp. 3651-3657.

[img] PDF - Published Version
684Kb

Official URL: http://edoc.unibas.ch/54745/

Downloads: Statistics Overview

Abstract

In classical planning, cost partitioning is a method for admissibly combining a set of heuristic estimators by distributing operator costs among the heuristics. An optimal cost partitioning is often prohibitively expensive to compute. Saturated cost partitioning is an alternative that is much faster to compute and has been shown to offer high-quality heuristic guidance on Cartesian abstractions. However, its greedy nature makes it highly susceptible to the order in which the heuristics are considered. We show that searching in the space of orders leads to significantly better heuristic estimates than with previously considered orders. Moreover, using multiple orders leads to a heuristic that is significantly better informed than any single-order heuristic. In experiments with Cartesian abstractions, the resulting heuristic approximates the optimal cost partitioning very closely.
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:Conference or Workshop Item, refereed
Conference or workshop item Subtype:Conference Paper
Publisher:AAAI Press
Series Name:Proceedings of the ... AAAI Conference on Artificial Intelligence
ISSN:2159-5399
e-ISSN:2374-3468
Note:Publication type according to Uni Basel Research Database: Conference paper
Language:English
Last Modified:05 Apr 2017 11:46
Deposited On:05 Apr 2017 10:53

Repository Staff Only: item control page