AAAI Publications, Twenty-Ninth AAAI Conference on Artificial Intelligence

Font Size: 
From Non-Negative to General Operator Cost Partitioning
Florian Pommerening, Malte Helmert, Gabriele Röger, Jendrik Seipp

Last modified: 2015-03-04


Operator cost partitioning is a well-known technique to make admissible heuristics additive by distributing the operator costs among individual heuristics. Planning tasks are usually defined with non-negative operator costs and therefore it appears natural to demand the same for the distributed costs. We argue that this requirement is not necessary and demonstrate the benefit of using general cost partitioning. We show that LP heuristics for operator-counting constraints are cost-partitioned heuristics and that the state equation heuristic computes a cost partitioning over atomic projections. We also introduce a new family of potential heuristics and show their relationship to general cost partitioning.


classical planning;cost-optimal planning;cost partitioning;abstraction heuristics;operator-counting constraints;potential heuristics

Full Text: PDF