Title:	Expressing and exploiting the common subgoal structure of classical planning domains using sketches
DNr:	SNIC 2021/22-193
Project Type:	SNIC Small Compute
Principal Investigator:	Dominik Drexler <dominik.drexler@liu.se>
Affiliation:	Linköpings universitet
Duration:	2021-03-10 – 2021-08-09
Classification:	10201
Keywords:

Abstract

In this work, we address the limitations of pure width-based methods like SIW by making use of a simple but powerful language for expressing problem decompositions introduced recently by Bonet and Geffner: policy sketches. A policy sketch $R$ is made up of a set of boolean and numerical features, and a set of sketch rules $C \mapsto E$ expresses how the values of these features are supposed to change. Like general policies, policy sketches are general, i.e., not tailored to specific instances of a domain, but unlike policies, the changes captured by means of sketch rules do not need to be achieved in a single step; they are instead possible subgoals to achieve. We show that many planning domains that cannot be solved by SIW are provable solvable in low polynomial time by means of the SIW_R algorithm, the version of SIW that makes use of user-provided policy sketches. Policy sketches are thus shown to be a powerful language for expressing domain-specific control language in a simple and compact way, and a convenient alternative to other languages such as HTNs or temporal logics where it is possible to express general decompositions of problems into subproblems, while proving key properties about them such as their complexity and width.