  Symbolic planning can provide an intuitive interface for non-expert users to
operate autonomous robots by abstracting away much of the low-level
programming. However, symbolic planners assume that the initially provided
abstract domain and problem descriptions are closed and complete. This means
that they are fundamentally unable to adapt to changes in the environment or
task that are not captured by the initial description. We propose a method that
allows an agent to automatically extend its skill set, and thus the abstract
description, upon encountering such a situation. We introduce strategies for
generalizing from previous experience, completing sequences of key actions and
discovering preconditions to ensure the efficiency of our skill sequence
exploration scheme. The resulting system is evaluated in simulation on object
rearrangement tasks. Compared to a Monte Carlo Tree Search baseline, our
strategies for efficient search have on average a 29% higher success rate at a
68% faster runtime.
