Data Entry: Please note that the research database will be replaced by UNIverse by the end of October 2023. Please enter your data into the system https://universe-intern.unibas.ch. Thanks
Abstraction Heuristics, Cost Partitioning and Network Flows
Book title (Conference Proceedings)
Proceedings of the 27th International Conference on Automated Planning and Scheduling (ICAPS 2017)
Place of Conference
Pittsburgh, Pennsylvania, USA
Publisher
AAAI Press
Abstract
Cost partitioning is a well-known technique to make admissible heuristics for classical planning additive. The optimal cost partitioning of explicit-state abstraction heuristics can be computed in polynomial time with a linear program, but the size of the model is often prohibitive. We study this model from a dual perspective and develop several simplification rules to reduce its size. We use these rules to answer open questions about extensions of the state equation heuristic and their relation to cost partitioning.