Cost optimal planning with multi-valued landmarks

Abstract

Abstract

Landmark based heuristics are among the most accurate current known admissible heuristics for cost optimal planning. A disjunctive action landmark can be seen as a form of at-least-one constraint on the actions it contains. In many domains, there are many critical propositions which have to be established for a number of times. Previous landmarks are too weak 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. Because exact lower bounds of general multi-valued action landmarks are intractable to extract and exploit, we introduce multi-valued proposition landmarks from which multi-valued action landmarks can be efficiently induced. Finally, we devise a linear programming based multi-valued landmark heuristic ${\mathit{h}}^{\mathrm{lpml}}$ which extracts and exploits multi-valued landmarks using a linear programming solver. ${\mathit{h}}^{\mathrm{lpml}}$ is guaranteed to be admissible and can be computed in polynomial time. Experimental evaluation on benchmark domains shows ${\mathit{h}}^{\mathrm{lpml}}$ beats state-of-the-art admissible heuristic in terms of heuristic accuracy and achieves better overall coverage performance at the cost of using more CPU time.