Enhancing Numeric-SAM for Learning with Few Observations
Argaman Mordoch Shahaf S. Shperberg Roni Stern Berndan Juba
A significant challenge in applying planning technology to real-world
problems lies in obtaining a planning model that accurately represents the
problem's dynamics. Numeric Safe Action Models Learning (N-SAM) is a recently
proposed algorithm that addresses this challenge. It is an algorithm designed
to learn the preconditions and effects of actions from observations in domains
that may involve both discrete and continuous state variables. N-SAM has
several attractive properties. It runs in polynomial time and is guaranteed to
output an action model that is safe, in the sense that plans generated by it
are applicable and will achieve their intended goals. To preserve this safety
guarantee, N-SAM must observe a substantial number of examples for each action
before it is included in the learned action model. We address this limitation
of N-SAM and propose N-SAM*, an enhanced version of N-SAM that always returns
an action model where every observed action is applicable at least in some
state, even if it was only observed once. N-SAM* does so without compromising
the safety of the returned action model. We prove that N-SAM* is optimal in
terms of sample complexity compared to any other algorithm that guarantees
safety. An empirical study on a set of benchmark domains shows that the action
models returned by N-SAM* enable solving significantly more problems compared
to the action models returned by N-SAM.