Abstract
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 nondeterministic planning