Skip to Main content Skip to Navigation
New interface
Conference papers

The Landmark-based Meta Best-First Search Algorithm for Classical Planning.

Abstract : In this paper, we revisit the idea of splitting a planning problem into subproblems hopefully easier to solve with the help of landmark 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 explore 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 exists, 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 planner 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download
Contributor : Alain Broc Connect in order to contact the contributor
Submitted on : Friday, September 5, 2014 - 10:25:35 AM
Last modification on : Tuesday, March 16, 2021 - 3:44:16 PM
Long-term archiving on: : Saturday, December 6, 2014 - 10:57:26 AM


Files produced by the author(s)


  • HAL Id : hal-01061111, version 1



S. Vernhes, G. Infantes, V. Vidal. The Landmark-based Meta Best-First Search Algorithm for Classical Planning.. Sixth Starting AI Researchers' Symposium (STAIRS'2012 at ECAIS'2012), Aug 2012, MONTPELLIER, France. ⟨hal-01061111⟩



Record views


Files downloads