Action Model Learning with Guarantees
This work addresses the challenge of automated action model learning for planning systems, offering a theoretical framework with convergence guarantees, though it is incremental in building upon existing learning-by-search paradigms.
The paper tackles the problem of learning action models with full observability by developing a theory based on version spaces and an online algorithm that maintains all consistent solutions, focusing on sound and complete approximations. The authors prove convergence to the true model with sufficient examples and demonstrate the approach's effectiveness across various planning domains.
This paper studies the problem of action model learning with full observability. Following the learning by search paradigm by Mitchell, we develop a theory for action model learning based on version spaces that interprets the task as search for hypothesis that are consistent with the learning examples. Our theoretical findings are instantiated in an online algorithm that maintains a compact representation of all solutions of the problem. Among these range of solutions, we bring attention to actions models approximating the actual transition system from below (sound models) and from above (complete models). We show how to manipulate the output of our learning algorithm to build deterministic and non-deterministic formulations of the sound and complete models and prove that, given enough examples, both formulations converge into the very same true model. Our experiments reveal their usefulness over a range of planning domains.