Learning General Policies from Small Examples Without Supervision
This work addresses the problem of learning general policies for planning domains, which is relevant for researchers and practitioners in automated planning, by offering an alternative approach that simplifies the learning process.
This paper proposes a new method for learning general policies that solve multiple instances of a planning domain without requiring sample plans or a QNP planner. It frames the problem as a combinatorial optimization task, specifically a Weighted Max-SAT problem, to find a small subset of features that separate 'good' from 'bad' state transitions and goals from non-goals, yielding general policies for several benchmark domains.
Generalized planning is concerned with the computation of general policies that solve multiple instances of a planning domain all at once. It has been recently shown that these policies can be computed in two steps: first, a suitable abstraction in the form of a qualitative numerical planning problem (QNP) is learned from sample plans, then the general policies are obtained from the learned QNP using a planner. In this work, we introduce an alternative approach for computing more expressive general policies which does not require sample plans or a QNP planner. The new formulation is very simple and can be cast in terms that are more standard in machine learning: a large but finite pool of features is defined from the predicates in the planning examples using a general grammar, and a small subset of features is sought for separating "good" from "bad" state transitions, and goals from non-goals. The problems of finding such a "separating surface" while labeling the transitions as "good" or "bad" are jointly addressed as a single combinatorial optimization problem expressed as a Weighted Max-SAT problem. The advantage of looking for the simplest policy in the given feature space that solves the given examples, possibly non-optimally, is that many domains have no general, compact policies that are optimal. The approach yields general policies for a number of benchmark domains.