On the Expressive Power of Planning Formalisms

Conditional Effects and Boolean Preconditions in the STRIPS Formalism
  • Bernhard Nebel
Part of the The Springer International Series in Engineering and Computer Science book series (SECS, volume 597)


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.


Action planning STRIPS conditional effects Boolean preconditions expressiveness computational complexity 


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 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
  2. Bäckström, C. (1995). Expressive equivalence of planning formalisms. Artificial Intelligence, 76(1–2): 17–34.CrossRefGoogle Scholar
  3. Bylander, T. (1994). The computational complexity of propositional STRIPS planning. Artificial Intelligence, 69(1–2): 165–204.MathSciNetzbMATHCrossRefGoogle Scholar
  4. Cadoli, M. and Donini, F. M. (1997). A survey on knowledge compilation. AI Communications, 10(3,4): 137–150.Google Scholar
  5. Fikes, R. E. and Nilsson, N. (1971). STRIPS: A new approach to the application of theorem proving to problem solving. Artificial Intelligence, 2:189–208.zbMATHCrossRefGoogle Scholar
  6. Furst, M., Saxe, J. B., and Sipser, M. (1984). Parity, circuits, and the polynomial-time hierarchy. Mathematical Systems Theory, 17(1): 13–27.MathSciNetzbMATHCrossRefGoogle Scholar
  7. Garey, M. R. and Johnson, D. S. (1979). Computers and Intractability—A Guide to the Theory of NP-Completeness. Freeman, San Francisco, CA.zbMATHGoogle Scholar
  8. 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
  9. Kambhampati, S., Parker, E., and Lambrecht, E. (1997). Understanding and extending Graphplan. In Steel and Alami, 1997, pages 260–272.Google Scholar
  10. Karp, R. M. and Lipton, R. J. (1980). Some connections between nonuniform and uniform complexity classes. In Conference Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing (STOC-80), pages 302–309, Los Angeles, California.CrossRefGoogle Scholar
  11. 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
  12. 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
  13. 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
  14. 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
  15. Nebel, B. (1999a). Compilation schemes: A theoretical tool for assessing the expressive power of planning formalisms. In Burgard, W., Cremers, A. B., and Christaller, T., editors, KI-99: Advances in Artificial Intelligence, pages 183–194, Bonn, Germany. Springer-Verlag.CrossRefGoogle Scholar
  16. 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
  17. Papadimitriou, C. H. (1994). Computational Complexity. Addison-Wesley, Reading, MA.zbMATHGoogle Scholar
  18. 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
  19. 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
  20. Webber, B. L. and Nilsson, N. J., editors (1981). Readings in Artificial Intelligence. Tioga, Palo Alto, CA.zbMATHGoogle Scholar

Copyright information

© Springer Science+Business Media New York 2000

Authors and Affiliations

  • Bernhard Nebel
    • 1
  1. 1.Institut für InformatikAlbert-Ludwigs-UniversitätFreiburgGermany

Personalised recommendations