In this work, we study the runtime distribution of satisficing planning in ensembles of random planning problems and in multiple runs of a randomized heuristic search on a single planning instance. Using common heuristic functions (such as FF) and six benchmark problem domains from the IPC, we find a heavy-tailed behavior, similar to that found in CSP and SAT. We investigate two notions of constrainedness, often used in the modeling of planning problems, and show that the heavy-tailed behavior tends to appear in relatively relaxed problems, where the required effort is, on average, low. Finally, we show that as with randomized restarts in CSP and SAT solving, recent search enhancements that incorporate randomness in the search process can help mitigate the effect of the heavy tail.

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.