Generalized Planning with Positive and Negative Examples
  Generalized planning aims at computing an algorithm-like structure
(generalized plan) that solves a set of multiple planning instances. In this
paper we define negative examples for generalized planning as planning
instances that must not be solved by a generalized plan. With this regard the
paper extends the notion of validation of a generalized plan as the problem of
verifying that a given generalized plan solves the set of input positives
instances while it fails to solve a given input set of negative examples. This
notion of plan validation allows us to define quantitative metrics to asses the
generalization capacity of generalized plans. The paper also shows how to
incorporate this new notion of plan validation into a compilation for plan
synthesis that takes both positive and negative instances as input. Experiments
show that incorporating negative examples can accelerate plan synthesis in
several domains and leverage quantitative metrics to evaluate the
generalization capacity of the synthesized plans.
