# Generalized Planning with Positive and Negative Examples

arXiv: https://arxiv.org/abs/1911.09365 · HTML: https://mlsanity.com/paper/1911.09365/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Nov 2019.

## Built on by (most cited first, 5 of 5)

- [Generalized Planning as Heuristic Search](https://mlsanity.com/paper/2103.14434/) (2021)
- [Generalized Planning as Heuristic Search: A new planning search-space that leverages pointers over objects](https://mlsanity.com/paper/2301.11087/) (2023)
- [Hierarchical Decomposition and Analysis for Generalized Planning](https://mlsanity.com/paper/2212.02823/) (2022)
- [Computing Programs for Generalized Planning as Heuristic Search](https://mlsanity.com/paper/2205.06259/) (2022)
- [Representation and Synthesis of C++ Programs for Generalized Planning](https://mlsanity.com/paper/2206.14480/) (2022)

## Abstract (arXiv)

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.