Cost optimal planning with multi-valued landmarks

Article type: Research Article

Authors: Zhang, Lei | Wang, Chong-Jun^{; *} | Xie, Jun-Yuan

Affiliations: State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, China. E-mails: zhanglei.com@gmail.com, chjwang@nju.edu.cn, jyxie@nju.edu.cn

Correspondence: [*] Corresponding author: Chong-Jun Wang, State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210046, China. E-mail: chjwang@nju.edu.cn.

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 hlpml which extracts and exploits multi-valued landmarks using a linear programming solver. hlpml is guaranteed to be admissible and can be computed in polynomial time. Experimental evaluation on benchmark domains shows hlpml 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.

Keywords: Heuristic search based planning, landmark heuristic, cost optimal planning

DOI: 10.3233/AIC-140622

Journal: AI Communications, vol. 28, no. 3, pp. 579-590, 2015