Learning Lifted Action Models from Traces of Incomplete Actions and States

Consider the problem of learning a lifted STRIPS model of the sliding-tile puzzle

from random state-action traces where the states represent the location of the tiles only,

and the actions are the labels up, down, left, and right, with no arguments.

Two challenges are involved in this problem.

First, the states are not full STRIPS states, as some predicates are missing, like

the atoms representing the position of the ``blank''. Second, the actions are not full STRIPS either,

as they do not reveal all the objects involved in the actions effects and preconditions.

Previous approaches have addressed different

versions of this model learning problem, but most assume that

actions in the traces are full STRIPS actions or that the domain predicates

are all observable. The new setting considered in this work is more ``realistic'', as

the atoms observed convey the state of the world but not full STRIPS states, and

the actions reveal the arguments needed for selecting the action but

not the ones needed for modeling it in STRIPS. For formulating and addressing

the learning problem, we introduce a variant of STRIPS, which we call STRIPS+,

where certain STRIPS action arguments can be left implicit in preconditions which can also

involve a limited form of existential quantification. The learning problem becomes the problem

of learning STRIPS+ models from STRIPS+ state-action traces. For this, the proposed learning algorithm, called

SYNTH, constructs a stratified sequence (conjunction) of precondition expressions or ``queries'' for each action,

that denote unique objects in the state and ground the implicit action arguments in STRIPS+.

The correctness and completeness of SYNTH is established, and its scalability is tested

on state-action traces obtained from STRIPS+ models derived from existing STRIPS domains.