Resource-Constrained Planning: A Monte Carlo Random Walk Approach

Abstract

The need to economize limited resources, such as fuel or money, is aubiquitous feature of planning problems. If the resources cannot bereplenished, the planner must make do with the initial supply. It isthen of paramount importance how constrained the problem is,i.e., whether and to which extent the initial resource supply exceedsthe minimum need. While there is a large body of literature on numericplanning and planning with resources, such resource constrainednesshas only been scantily investigated. We herein start to address thisin more detail. We generalize the previous notion of resourceconstrainedness, characterized through a numeric problem feature C≥1, to the case of multiple resources. We implement an extendedbenchmark suite controlling C. We conduct a large-scale study of thecurrent state of the art as a function of C, highlighting whichtechniques contribute to success. We introduce two new techniques ontop of a recent Monte Carlo Random Walk method, resulting in a plannerthat, in these benchmarks, outperforms previous planners whenresources are scarce (C close to 1). We investigate the parametersinfluencing the performance of that planner, and we show that one ofthe two new techniques works well also on the regular IPC benchmarks.