Planning algorithms typically require a symbolic representation of the options to act. Relying on models created manually by experts can be problematic given their availability, knowledge, and associated cost. Instead symbolic domain models can be learned automatically from examples. The task of domain learning is then to find an action model that can explain given observed plan executions, so-called traces. It allows us to automate the identification of actions’ preconditions and effects.
While previous research has put forth various techniques and covers multiple planning formalisms, the theoretical foundations of domain learning are still in their infancy. We investigate several settings of domain learning - including the cases where the state is fully observable and not observable at all. Our main emphasis will be on the assumption of rationality on the part of the agent generating the plans we use for learning. We argue that without any rationality assumption, almost nothing can be learned about the actions’ preconditions and effects. If we however assume that the given traces are justified in the sense that either no single action or no set of actions can be removed without violating correctness of the plan, useful action models can be learned. We study the computational complexity of the resulting task and show that it ranges from polynomial to Sigma-P-2-completeness.