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
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.