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.
Type de document :
Communication dans un congrès
Sixth Starting AI Researchers' Symposium (STAIRS'2012 at ECAIS'2012), Aug 2012, MONTPELLIER, France
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger

https://hal-onera.archives-ouvertes.fr/hal-01061111
Contributeur : Alain Broc <>
Soumis le : vendredi 5 septembre 2014 - 10:25:35
Dernière modification le : mercredi 28 mars 2018 - 14:16:10
Document(s) archivé(s) le : samedi 6 décembre 2014 - 10:57:26

Fichier

DCSD13003.1401195677.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01061111, version 1

Collections

Citation

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〉

Partager

Métriques

Consultations de la notice

139

Téléchargements de fichiers

204