M.Sc Student | Vitaly Mirkis |
---|---|

Subject | STRIPS Planning with No Negative Effects |

Department | Department of Industrial Engineering and Management |

Supervisor | Full Professor Domshlak Carmel |

Full Thesis text |

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 *h*add, *h*^{ff}, and the admissible heuristic *h*max. 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 *h*max? And (2) If near-optimal solutions are acceptable, are *h*add and *h*^{ff} 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 *h*max, *h*add and *h*^{ff} 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 *h*max within the cost-sharing
framework, and this heuristic, *h*cs, 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 *h*add and *h*^{ff} 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, *h*spmax, and empirically demonstrate that it leads to discovering solutions of
higher quality than *h*add and *h*^{ff} while expanding
significantly less search nodes than *h*max