An Evolutionary Metaheuristic for Domain-Independent Satisficing Planning

Jacques Bibai 1, 2 Pierre Savéant 1 Marc Schoenauer 2, 3 Vidal Vincent 4
2 TAO - Machine Learning and Optimisation
LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
Abstract : DAEX is a metaheuristic designed to improve the plan quality and the scalability of an encapsulated planning system. DAEX is based on a state decomposition strategy, driven by an evolutionary algorithm, which benefits from the use of a classical planning heuristic to maintain an ordering of atoms within the individuals. The proof of concept is achieved by embedding the domain-independent satisficing YAHSP planner and using the critical path h1 heuristic. Experiments with the resulting algorithm are performed on a selection of IPC benchmarks from classical, cost-based and temporal domains. Under the experimental conditions of the IPC, and in particular with a universal parameter setting common to all domains, DAEYAHSP is compared to the best planner for each type of domain. Results show that DAEYAHSP performs very well both on coverage and quality metrics. It is particularly noticeable that DAEX improves a lot on plan quality when compared to YAHSP, which is known to provide largely suboptimal solutions, making it competitive with state-of-the-art planners. This article gives a full account of the algorithm, reports on the experiments and provides some insights on the algorithm behavior.
Type de document :
Communication dans un congrès
Ronen Brafman and Héctor Geffner and Jörg Hoffmann and Henry Kautz. 20th International Conference on Automated Planning and Scheduling-ICAPS2010, May 2010, Toronto, Canada. AAAI Press, pp.15-25, 2010
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00456167
Contributeur : Marc Schoenauer <>
Soumis le : samedi 13 février 2010 - 20:02:22
Dernière modification le : jeudi 5 avril 2018 - 12:30:12
Document(s) archivé(s) le : jeudi 23 septembre 2010 - 11:49:22

Fichier

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

Identifiants

  • HAL Id : inria-00456167, version 2

Collections

Citation

Jacques Bibai, Pierre Savéant, Marc Schoenauer, Vidal Vincent. An Evolutionary Metaheuristic for Domain-Independent Satisficing Planning. Ronen Brafman and Héctor Geffner and Jörg Hoffmann and Henry Kautz. 20th International Conference on Automated Planning and Scheduling-ICAPS2010, May 2010, Toronto, Canada. AAAI Press, pp.15-25, 2010. 〈inria-00456167v2〉

Partager

Métriques

Consultations de la notice

271

Téléchargements de fichiers

840