Landmark-based meta best-first search algorithm: First parallelization attempt and evaluation

Abstract. In this paper, we revisit the idea of splitting a planning prob-lem into subproblems hopefully easier to solve with the help of land-mark analysis. This technique initially proposed in the first approaches related to landmarks in classical planning has been outperformed by landmark-based heuristics and has not been paid much attention over the last years. We believe that it is still a promising research direction, particularly for devising distributed search algorithms that could ex-plore different landmark orderings in parallel. To this end, we propose a new method for problem splitting based on landmarks, which has three advantages over the original technique: it is complete (if a solution ex-ists, the algorithm finds it), it uses the precedence relations over the landmarks in a more flexible way (the orderings are explored by way of a best-first search algorithm), and finally it can be easily performed in parallel (by e.g. following the hash-based distribution principle). We lay in this paper the foundations of a meta best-first search algorithm, which explores the landmark orderings and can use any embedded plan-ner to solve each subproblem. It opens up avenues for future research: among them are new heuristics for guiding the meta search towards the most promising orderings, different policies for expanding nodes of the meta search, influence of the embedded subplanner, and parallelization strategies of the meta search