Online Saturated Cost Partitioning for Classical Planning

Authors

  • Jendrik Seipp Linköping University, Sweden University of Basel, Switzerland

DOI:

https://doi.org/10.1609/icaps.v31i1.15976

Keywords:

Classical Planning Techniques And Analysis

Abstract

Cost partitioning is a general method for admissibly summing up heuristic estimates for optimal state-space search. Most cost partitioning algorithms can optimize the resulting cost-partitioned heuristic for a specific state. Since computing a new cost-partitioned heuristic for each evaluated state is usually too expensive in practice, the strongest planners based on cost partitioning over abstraction heuristics precompute a set of cost-partitioned heuristics before the search and maximize over their estimates during the search. This makes state evaluations very fast, but since there is no better termination criterion than a time limit, it requires a long precomputation phase, even for the simplest planning tasks. A prototypical example for this is the Scorpion planner which computes saturated cost partitionings over abstraction heuristics offline before the search. Using Scorpion as a case study, we show that by incrementally extending the set of cost-partitioned heuristics online during the search, we drastically speed up the planning process and even often solve more tasks.

Downloads

Published

2021-05-17

How to Cite

Seipp, J. (2021). Online Saturated Cost Partitioning for Classical Planning. Proceedings of the International Conference on Automated Planning and Scheduling, 31(1), 317-321. https://doi.org/10.1609/icaps.v31i1.15976