@article{Seipp_2021, title={Online Saturated Cost Partitioning for Classical Planning}, volume={31}, url={https://ojs.aaai.org/index.php/ICAPS/article/view/15976}, DOI={10.1609/icaps.v31i1.15976}, abstractNote={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.}, number={1}, journal={Proceedings of the International Conference on Automated Planning and Scheduling}, author={Seipp, Jendrik}, year={2021}, month={May}, pages={317-321} }