Cost Optimal Planning with LP-Based Multi-Valued Landmark Heuristic

Landmark based heuristics are among the most accurate current known admissible heuristics for cost optimal planning. Disjunctive action landmarks can be considered as at-least-one constraints on the actions they contains. In many planning domains, there are many critical propositions which have to be established for a number of times. Previous landmarks fail to express this kind of general cardinality constraints. In this paper, we propose to generalize landmarks to multi-valued landmarks to model general cardinality constraints in cost optimal planning. We show existence of complete multi-valued landmark sets by explicitly constructing complete multi-valued action landmark sets for general planning tasks. However, it's computationally intractable to extract and exploit exact lower bounds of general multi-valued action landmarks. We devise a linear programming based multi-valued landmark heuristic h l pml which extracts and exploits multi-valued landmarks using a linear programming solver. The heuristic h l pml is guaranteed to be admissible and can be computed in polynomial time. Experimental evaluation on benchmark domains shows h l pml beats state-of-theart admissible heuristic in terms of heuristic accuracy and achieves better overall coverage performance at the cost of using more CPU time.