Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Ignoring irrelevant facts and operators in plan generation

  • Conference paper
  • First Online:
Recent Advances in AI Planning (ECP 1997)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 1348))

Included in the following conference series:

Abstract

It is traditional wisdom that one should start from the goals when generating a plan in order to focus the plan generation process on potentially relevant actions. The GRAPHPLAN system, however, which is the most efficient planning system nowadays, builds a “planning graph” in a forward-chaining manner. Although this strategy seems to work well, it may possibly lead to problems if the planning task description contains irrelevant information. Although some irrelevant information can be filtered out by GRAPHPLAN, most cases of irrelevance are not noticed.

In this paper, we analyze the effects arising from “irrelevant” information to planning task descriptions for different types of planners. Based on that, we propose a family of heuristics that select relevant information by minimizing the number of initial facts that are used when approximating a plan by backchaining from the goals ignoring any conflicts. These heuristics, although not solution-preserving, turn out to be very useful for guiding the planning process, as shown by applying the heuristics to a large number of examples from the literature.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. C. Bäckström. Equivalence and tractability results for SAS+ planning. In B. Nebel, W. Swartout, and C. Rich, editors, Principles of Knowledge Representation and Reasoning: Proceedings of the 3rd International Conference (KR-92), pages 126–137, Cambridge, MA, Oct. 1992. Morgan Kaufmann.

    Google Scholar 

  2. A. L. Blum and M. L. Furst. Fast planning through planning graph analysis. Artificial Intelligence, 90(1-2):279–298, 1997.

    Google Scholar 

  3. T. Bylander. The computational complexity of propositional STRIPS planning. Artificial Intelligence, 69(1-2):165–204, 1994.

    Google Scholar 

  4. T. A. Estlin and R. J. Mooney. Multi-strategy learning of search control for partial order planning. In Proceedings of the 13th National Conference of the American Association for Artificial Intelligence (AAAI-96), Portland, OR, July 1996. MIT Press.

    Google Scholar 

  5. R. E. Fikes and N. Nilsson. STRIPS: A new approach to the application of theorem proving to problem solving. Artificial Intelligence, 2:189–208, 1971.

    Google Scholar 

  6. A. Gerevini and L. Schubert. Accelerating partial-order planners: Some techniques for effective search control and pruning. Journal of Artificial Intelligence Research, 5:95–137, 1996.

    Google Scholar 

  7. H. A. Kautz and B. Selman. Pushing the envelope: Planning, propositional logic, and stochastic search. In Proceedings of the 13th National Conference of the American Association for Artificial Intelligence (AAAI-96), pages 1194–1201, Portland, OR, July 1996. MIT Press.

    Google Scholar 

  8. J. Koehler, B. Nebel, J. Hoffmann, and Y. Dimopoulos. Extending planning graphs to an ADL subset. In Proc. European Conference on Planning 1997, Toulouse, France, September 1997.

    Google Scholar 

  9. D. McDermott. A heuristic estimator for means-ends analysis in planning. In Proceedings of the 3rd International Conference on Artificial Intelligence Planning Systems (AIPS-96), pages 142–149. AAAI Press, Menlo Park, 1996.

    Google Scholar 

  10. D. McDermott. Using regression-match graphs to control search in planning. Manuscript submitted for publication, 1997.

    Google Scholar 

  11. J. S. Penberthy and D. S. Weld. UCPOP: A sound, complete, partial order planner for ADL. In B. Nebel, W. Swartout, and C. Rich, editors, Principles of Knowledge Representation and Reasoning: Proceedings of the 3rd International Conference (KR-92), pages 103–114, Cambridge, MA, Oct. 1992. Morgan Kaufmann.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institut für Informatik, Albert-Ludwigs-Universität, D-79100, Freiburg, Germany

    Bernhard Nebel, Yannis Dimopoulos & Jana Koehler

Authors
  1. Bernhard Nebel
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yannis Dimopoulos
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jana Koehler
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Sam Steel Rachid Alami

Rights and permissions

Reprints and permissions

Copyright information

© 1997 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Nebel, B., Dimopoulos, Y., Koehler, J. (1997). Ignoring irrelevant facts and operators in plan generation. In: Steel, S., Alami, R. (eds) Recent Advances in AI Planning. ECP 1997. Lecture Notes in Computer Science, vol 1348. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-63912-8_97

Download citation

  • DOI: https://doi.org/10.1007/3-540-63912-8_97

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-63912-1

  • Online ISBN: 978-3-540-69665-0

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation