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

Recognizing the agent’s goals incrementally: planning graph as a basis

  • Research Article
  • Published:
Frontiers of Computer Science in China Aims and scope Submit manuscript

Abstract

Plan recognition, the inverse problem of plan synthesis, is important wherever a system is expected to produce a kind of cooperative or competitive behavior. Most plan recognizers, however, suffer the problem of acquisition and hand-coding a larger plan library. This paper is aims to show that modern planning techniques can help build plan recognition systems without suffering such problems. Specifically, we show that the planning graph, which is an important component of the classical planning system Graph-plan, can be used as an implicit, dynamic planning library to represent actions, plans and goals. We also show that modern plan generating technology can be used to find valid plans in this framework. In this sense, this method can be regarded as a bridge that connects these two research fields. Empirical and theoretical results also show that the method is efficient and scalable.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Ghallab M, Nau D, Traverso P. Automated Planning: Theory and Practice. Morgan Kaufmann Publishers, 2004

  2. Bauer M. Integrating Probabilistic Reasoning into Plan Recognition. In: Proceedings of the 11th European Conference on Artificial Intelligence. Chichester/London/New York: Wiley, 1994, 620–624.

    Google Scholar 

  3. Hong J. Goal Recognition through Goal Graph Analysis. Journal of Artificial Intelligence Research, 2001, 15(1): 1–30

    Article  MATH  Google Scholar 

  4. Kautz H. A formal theory of plan recognition. Dissertation for the Doctoral Degree. Rochester: University of Rochester, 1987

    Google Scholar 

  5. Kautz H, Allen J. Generalized plan recognition In: Proceedings of National Conference on Artificial Intelligence. AAAI Press, 1986, 32–37

  6. Jiang Y H, Ma N. A plan recognition algorithm based on plan knowledge graph. Journal of Software, 2001, 13(1): 686–692

    MathSciNet  Google Scholar 

  7. Lesh N. Scalable and adaptive goal recognition. Dissertation for the Doctoral Degree. University of Washington, 1998

  8. Lesh N, et al. Scaling up goal recognition. In: Proceedings of the 5th Int. Conf. on Principles of Knowledge Representation and Reasoning. San Francisco: Morgan Kaufmann, 1996, 178–189

    Google Scholar 

  9. Bauer M. Acquisition of abstract plan descriptions for plan recognition. In: Proceedings of National Conference on Artificial Intelligence. AAAI Press, 1998, 936–941

  10. Albrecht D W, et al. Bayesian model for keyhole plan recognition in an adventure game. User Modeling and User-Adapted Interaction. 1998, 8(1–2): 5–47

    Article  Google Scholar 

  11. Blum A L, Furst M L. Fast planning though planning graph analysis. Artificial Intelligence, 1997, 90(1–2): 281–300

    Article  MATH  Google Scholar 

  12. Hoffmann, J, Nebel B. The FF planning system: Fast plan generation through heuristic search. Journal of Artificial Intelligent Research, 2001, 14(1): 253–302

    MATH  Google Scholar 

  13. Hoffmann J. Where Ignoring Delete Lists Works: Local Search Topology in Planning Benchmarks Journal of Artificial Intelligence Research, 2005, 24(1): 685–758

    MATH  Google Scholar 

  14. Helmert M. The Fast Downward Planning System. Journal of Artificial Intelligence Research, 2006, 26(1): 191–246

    Google Scholar 

  15. Kautz H, Selman B. Unifying SAT-based and Graph-based Planning. In: Proceedings of International joint conference of Artificial Intelligence (IJCAI-99). San Francisco: Morgan Kaufmann, 1999, 318–325

    Google Scholar 

  16. Kautz H. Deconstructing Planning as Satisfiability. In: Proceedings of the Twenty-first National Conference on Artificial Intelligence (AAAI-06). AAAI Press, 2006, 320–323

  17. Gerevini A, Saetti A, Serina I. Planning through Stochastic Local Search and Temporal Action Graphs. Journal of Artificial Intelligence Research, 2003, 20(1): 239–290

    MATH  Google Scholar 

  18. Gerevini A, Saetti A, Serina I. An Approach to Temporal Planning and Scheduling in Domains with Predicatable Exogenous Events. Journal of Artificial Intelligence Research, 2006, 25(1): 187–231

    Google Scholar 

  19. Blaylock N, Allen J. Corpus-based, Statistical Goal Recognition. In: Proceedings of International joint conference of Artificial Intelligence (IJCAI-2003). San Francisco: Morgan Kaufmann, 2003, 1303–1308

    Google Scholar 

  20. Hong J. Graph construction and analysis as a paradigm for plan recognition In: Proceedings of National Conference on Artificial Intelligence. AAAI Press, 2000, 774–779

  21. Daniel W. Recent Advances in AI Planning. AI Magazine, 1999, 20(2): 93–123

    MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. College of Computer Science, Jilin University, Changchun, 130012, China

    Sun Jigui & Yin Minghao

  2. Key Laboratory of Symbol Computation and Knowledge Engineering of Ministry of Education, Changchun, 130012, China

    Sun Jigui & Yin Minghao

  3. College of Computer, Northeast Normal University, Changchun, 130024, China

    Yin Minghao

Authors
  1. Sun Jigui
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yin Minghao
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yin Minghao.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Sun, J., Yin, M. Recognizing the agent’s goals incrementally: planning graph as a basis. Front. Comput. Sc. China 1, 26–36 (2007). https://doi.org/10.1007/s11704-007-0004-5

Download citation

  • Received:

  • Accepted:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11704-007-0004-5

Keywords

Search

Navigation