Resource-Constrained Planning: A Monte Carlo Random Walk Approach

Hootan Nakhost 1 Joerg Hoffmann 2, 3 Martin Müller 4
2 MAIA - Autonomous intelligent machine
Inria Nancy - Grand Est, LORIA - AIS - Department of Complex Systems, Artificial Intelligence & Robotics
Abstract : The need to economize limited resources, such as fuel or money, is a ubiquitous feature of planning problems. If the resources cannot be replenished, the planner must make do with the initial supply. It is then of paramount importance how constrained the problem is, i.e., whether and to which extent the initial resource supply exceeds the minimum need. While there is a large body of literature on numeric planning and planning with resources, such resource constrainedness has only been scantily investigated. We herein start to address this in more detail. We generalize the previous notion of resource constrainedness, characterized through a numeric problem feature C ≥ 1, to the case of multiple resources. We implement an extended benchmark suite controlling C. We conduct a large-scale study of the current state of the art as a function of C, highlighting which techniques contribute to success. We introduce two new techniques on top of a recent Monte Carlo Random Walk method, resulting in a planner that, in these benchmarks, outperforms previous planners when resources are scarce (C close to 1). We investigate the parameters influencing the performance of that planner, and we show that one of the two new techniques works well also on the regular IPC benchmarks.
Type de document :
Communication dans un congrès
22nd International Conference on Automated Planning and Scheduling (ICAPS), Jun 2012, Itabaia, Brazil. 2012
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00765030
Contributeur : Olivier Buffet <>
Soumis le : vendredi 14 décembre 2012 - 09:19:21
Dernière modification le : jeudi 11 janvier 2018 - 06:25:23
Document(s) archivé(s) le : dimanche 18 décembre 2016 - 01:01:04

Fichier

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

Identifiants

  • HAL Id : hal-00765030, version 1

Collections

Citation

Hootan Nakhost, Joerg Hoffmann, Martin Müller. Resource-Constrained Planning: A Monte Carlo Random Walk Approach. 22nd International Conference on Automated Planning and Scheduling (ICAPS), Jun 2012, Itabaia, Brazil. 2012. 〈hal-00765030〉

Partager

Métriques

Consultations de la notice

265

Téléchargements de fichiers

182