Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [25 references]  Display  Hide  Download

https://hal.inria.fr/hal-00765030
Contributor : Olivier Buffet <>
Submitted on : Friday, December 14, 2012 - 9:19:21 AM
Last modification on : Wednesday, November 27, 2019 - 4:20:15 PM
Long-term archiving on: : Sunday, December 18, 2016 - 1:01:04 AM

File

icaps12c.pdf
Files produced by the author(s)

Identifiers

  • 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. ⟨hal-00765030⟩

Share

Metrics

Record views

368

Files downloads

335