Generalized Planning: Synthesizing Plans that Work for Multiple Environments

Hu, Yuxiao; De Giacomo, Giuseppe

doi:10.5591/978-1-57735-516-8/IJCAI11-159

Generalized Planning: Synthesizing Plans that Work for Multiple Environments

Yuxiao Hu, Giuseppe De Giacomo

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 918-922.

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.

Yuxiao Hu, and Giuseppe De Giacomo. 2011. Generalized Planning: Synthesizing Plans that Work for Multiple Environments. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 918–922. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-159

@inproceedings{ijcai2011p159,
  title     = {Generalized Planning: Synthesizing Plans that Work for Multiple Environments},
  author    = {Hu, Yuxiao and De Giacomo, Giuseppe},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {918--922},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-159},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-159},
}

TY  - CPAPER
TI  - Generalized Planning: Synthesizing Plans that Work for Multiple Environments
AU  - Hu, Yuxiao
AU  - De Giacomo, Giuseppe
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 918
EP  - 922
DO  - 10.5591/978-1-57735-516-8/IJCAI11-159
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-159
ER  -