Generalized Planning: Synthesizing Plans That Work for Multiple Environments
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.
Cite
Text
Hu and De Giacomo. "Generalized Planning: Synthesizing Plans That Work for Multiple Environments." International Joint Conference on Artificial Intelligence, 2011. doi:10.5591/978-1-57735-516-8/IJCAI11-159Markdown
[Hu and De Giacomo. "Generalized Planning: Synthesizing Plans That Work for Multiple Environments." International Joint Conference on Artificial Intelligence, 2011.](https://mlanthology.org/ijcai/2011/hu2011ijcai-generalized/) doi:10.5591/978-1-57735-516-8/IJCAI11-159BibTeX
@inproceedings{hu2011ijcai-generalized,
title = {{Generalized Planning: Synthesizing Plans That Work for Multiple Environments}},
author = {Hu, Yuxiao and De Giacomo, Giuseppe},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2011},
pages = {918-923},
doi = {10.5591/978-1-57735-516-8/IJCAI11-159},
url = {https://mlanthology.org/ijcai/2011/hu2011ijcai-generalized/}
}