• Calendar

January 26, Thursday
12:00 – 13:00

The field of automated, domain-independent planning seeks to build general-purpose algorithms enabling a system to synthesize a course of action that will achieve certain goals. Such algorithms perform reachability analysis in large-scale state models that are implicitly described in a concise manner via some intuitive declarative language. And though planning problems have been studied since the early days of Artificial Intelligence research, recent developments (and, in particular, recent developments in planning as heuristic search) have dramatically advanced the field, and also substantially contributed to some related fields such as software/hardware verification, control, information integration, etc. The difference between various algorithms for planning as heuristic search is mainly in the heuristic functions they define and use. Most typically, an (admissible) heuristic function for domain-independent planning is defined as the (optimal) cost of achieving the goals in an over-approximating abstraction of the planning problem in hand. Such an abstraction is obtained by relaxing certain constraints that are present in the specification of the real problem, and the desire is to obtain a provably poly-time solvable, yet informative abstract problem. The main questions are thus: What constraints should we relax to obtain such an effective over-approximating abstraction? How should we combine information provided by multiple such abstractions? In this talk we consider both these questions, and present some recent formal and empirical results that help answering these questions (sometimes even to optimality). Specifically, Considering Q1, we introduce a generalization of the pattern-database (PDB) homomorphism abstractions to what we called implicit abstractions. The basic idea is in abstracting the problem in hand into provably tractable fragments of optimal planning, alleviating by that the constraint of PDBs to use projections of only low dimensionality. We then introduce concrete instance of this framework called fork-decomposition, and show both formally and empirically that the admissible heuristics induced by the latter abstractions provide state-of-the-art worst-case informativeness guarantees on several standard domains. Considering Q2, we describe a procedure that takes a classical planning task, a forward-search state, and a set of abstraction-based admissible heuristics, and derives an optimal additive composition of these heuristics with respect to the given state. Most importantly, we show that this procedure is polynomial-time for arbitrary sets of all known to us abstraction-based heuristics such as PDBs, constrained PDBs, merge-and-shrink abstractions, fork-decomposition implicit abstractions, and implicit abstractions based on tractable constraint optimization. The talk is based on a joint work with Prof. Carmel Domshlak.