Exploiting landmarks for hybrid planning

Abstract

Very recently, the well-known concept of landmarks has been adapted from the classical planning setting to hierarchical planning. It was shown how a pre-processing step that extracts local landmarks from a planning domain and problem description can be used in order to prune the search space that is to be explored before the actual search is performed. This pruning technique eliminates all branches of the task decomposition tree, for which can be proven that they will never lead to a solution. In this paper, we investigate this technique in more detail and extend it by introducing search strategies which use these local landmarks in order to guide the planning process more effectively towards a solution. Our empirical evaluation shows that the pre-processing step dramatically improves performance because dead ends can be detected much earlier than without pruning and that our search strategies using the local landmarks outperform many other possible search strategies.