---
title: "Generalized Planning: Synthesizing Plans that Work for Multiple Environments"
authors:
  - "Yuxiao Hu"
  - "Giuseppe De Giacomo"
doi: "10.5591/978-1-57735-516-8/IJCAI11-159"
url: "https://ijcai.org/proceedings/2011/159"
pdf: "https://ijcai.org/proceedings/2011/0159.pdf"
venue: "Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence"
year: 2011
pages: "918-922"
track: ""
keywords:
---

# Generalized Planning: Synthesizing Plans that Work for Multiple Environments

Yuxiao Hu, Giuseppe De Giacomo

*Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence*, pages 918-922. DOI: [10.5591/978-1-57735-516-8/IJCAI11-159](https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-159)

## Abstract

We give a formal definition of generalized planning that is independent of any representation formalism. We assume that our generalized plans must work on a set of deterministic environments, which are essentially unrelated to each other. We prove that generalized planning for a finite set of environments is always decidable and EXPSPACE-complete. Our proof is constructive and gives us a sound, complete and complexity-wise optimal technique. We also consider infinite sets of environments, and show that generalized planning for the infinite one-dimensional problems, known in the literature to be recursively enumerable when restricted to finite-state plans, is EXPSPACE-decidable without sequence functions, and solvable by generalized planning for finite sets.