On the Expressive Power of Planning Formalisms
- 379 Downloads
The notion of “expressive power” is often used in the literature on planning. However, it is usually only used in an informal way. In this paper, we will formalize this notion using the “compilability framework” and analyze the expressive power of some variants of STRIPS allowing for conditional effects and arbitrary Boolean formulae in preconditions. One interesting consequence of this analysis is that we are able to confirm a conjecture by Bäckström that preconditions in conjunctive normal form add to the expressive power of propositional STRIPS. Further, we will show that STRIPS with conditional effects is incomparable to STRIPS with Boolean formulae as preconditions. Finally, we show that preconditions in conjunctive normal form do not add any expressive power once we have conditional effects.
KeywordsAction planning STRIPS conditional effects Boolean preconditions expressiveness computational complexity
Unable to display preview. Download preview PDF.
- Anderson, C. R., Smith, D. E., and Weld, D. S. (1998). Conditional effects in Graphplan. In Proceedings of the 4th International Conference on Artificial Intelligence Planning Systems (AIPS-98), pages 44–53. AAAI Press, Menlo Park.Google Scholar
- Cadoli, M. and Donini, F. M. (1997). A survey on knowledge compilation. AI Communications, 10(3,4): 137–150.Google Scholar
- Gazen, B. C. and Knoblock, C. (1997). Combining the expressiveness of UCPOP with the efficiency of Graphplan. In Steel and Alami, 1997, pages 221–233.Google Scholar
- Kambhampati, S., Parker, E., and Lambrecht, E. (1997). Understanding and extending Graphplan. In Steel and Alami, 1997, pages 260–272.Google Scholar
- Kautz, H. A. and Selman, B. (1992). Forming concepts for fast inference. In Proceedings of the 10th National Conference of the American Association for Artificial Intelligence (AAAI-92), pages 786–793, San Jose, CA. MIT Press.Google Scholar
- Koehler, J., Nebel, B., Hoffmann, J., and Dimopoulos, Y. (1997). Extending planning graphs to an ADL subset. In Steel and Alami, 1997, pages 273–285.Google Scholar
- McCarthy, J. and Hayes, P. J. (1969). Some philosophical problems from the standpoint of artificial intelligence. In Meitzer, B. and Michie, D., editors, Machine Intelligence, volume 4, pages 463–502. Edinburgh University Press, Edinburgh, UK. Also published in Webber and Nilsson, 1981.Google Scholar
- Nebel, B. (1998). On the compilability and expressive power of propositional planning formalisms. Technical Report 101, Albert-Ludwigs-Universität, Institut für Informatik, Freiburg, Germany.Google Scholar
- Nebel, B. (1999b). What is the expressive power of disjunctive preconditions? In Biundo, S. and Fox, M., editors, Recent Advances in AI Planning, 5th European Conference on Planning (ECP’99), Durham, UK. Springer-Verlag. To appear.Google Scholar
- Pednault, E. P. (1989). ADL: Exploring the middle ground between STRIPS and the situation calculus. In Brachman, R., Levesque, H. J., and Reiter, R., editors, Principles of Knowledge Representation and Reasoning: Proceedings of the 1st International Conference (KR-89), pages 324–331, Toronto, ON. Morgan Kaufmann.Google Scholar
- Steel, S. and Alami, R., editors (1997). Recent Advances in AI Planning. 4th European Conference on Planning (ECP’91), volume 1348 of Lecture Notes in Artificial Intelligence, Toulouse, France. Springer-Verlag.Google Scholar