טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentVitaly Mirkis
SubjectSTRIPS Planning with No Negative Effects
DepartmentDepartment of Industrial Engineering and Management
Supervisor Full Professor Domshlak Carmel
Full Thesis textFull thesis text - English Version


Abstract

The field of automated, domain-independent planning seeks to build algorithms enabling a system to synthesize a course of action that will achieve certain goals. The automatic derivation of heuristic functions from problem descriptions in declarative action languages has been one of the key developments in recent planning research. Such heuristic functions are used to estimate the distance from search states to their nearest goal states, and search algorithms can use these estimates to guide the search.

So far, the major impact on developing heuristics for domain-independent STRIPS planning should probably be attributed to exploiting the ignoring-delete-effects relaxation of the problem. While computing the optimal cost h+ for problems with no delete effects is NP-hard, approximations for this problem has led to introducing both quite informative heuristics such as hadd, hff, and the admissible heuristic hmax. However, a few questions of theoretical and practical interest with respect to the ignoring-delete-effects relaxation remain open. In particular, in this work we consider two such open questions, notably (1) If optimal solutions are required, can we formulate a non-trivial admissible approximation of h+ other than hmax? And (2) If near-optimal solutions are acceptable, are hadd and hff the most informative approximations possible for h+?

Targeting these two questions, here we introduce a novel generalizing perspective on estimating h+. Inspired by works on cost-based abduction on weighted and-or dags, the suggested cost-sharing framework is based on a parametric cost propagation over schematically constructed relaxed planning graphs. We begin with introducing the framework, and show that hmax, hadd and hff can be casted as its instances. Next we consider the two aforementioned open questions with respect to approximating h+. We show that there is an admissible alternative to hmax within the cost-sharing framework, and this heuristic, hcs, has been successfully used in probabilistic reasoning for more than a decade. However, what is good for "typical" problems of probabilistic reasoning turns out not to be so for "typical" problems of classical planning.

Next, putting the admissibility aside, we show that various instances of the cost-sharing framework can be more informative than hadd and hff with respect to the optimal solution cost. In particular, this can be obtained by propagating more complicated (than single scalars) pieces of information about the estimated cost of the sub-goals. We present and discuss one such framework instance, hspmax, and empirically demonstrate that it leads to discovering solutions of higher quality than hadd and hff while expanding significantly less search nodes than hmax