Generalized Planning: Non-Deterministic Abstractions and Trajectory Constraints
This work addresses the challenge of creating general policies for families of problems in AI planning, offering a method to remove termination conditions and handle global constraints, which is incremental but potentially impactful for automated planning systems.
The paper tackles the problem of generalized planning by addressing the termination condition needed for abstract policies to solve concrete problems, showing that global structure missed by local abstractions can be captured using trajectory constraints, often expressed as LTL formulas, which reduces generalized planning to LTL synthesis or non-deterministic planning for certain problem classes.
We study the characterization and computation of general policies for families of problems that share a structure characterized by a common reduction into a single abstract problem. Policies $μ$ that solve the abstract problem P have been shown to solve all problems Q that reduce to P provided that $μ$ terminates in Q. In this work, we shed light on why this termination condition is needed and how it can be removed. The key observation is that the abstract problem P captures the common structure among the concrete problems Q that is local (Markovian) but misses common structure that is global. We show how such global structure can be captured by means of trajectory constraints that in many cases can be expressed as LTL formulas, thus reducing generalized planning to LTL synthesis. Moreover, for a broad class of problems that involve integer variables that can be increased or decreased, trajectory constraints can be compiled away, reducing generalized planning to fully observable non-deterministic planning.