Proceedings

A Critical Look at Critics in HTN Planning

Download BibTeX Cite

Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence. Planning. Pages 1592-1597.

© 1995 International Joint Conferences on Artificial Intelligence

Abstract

Detecting interactions and resolving conflicts is one of the key issues for generative planning systems. Hierarchical Task Network (HTN) planning systems use critics for this purpose. Critics have provided extra efficiency and flexibility to HTN planning systems, but their procedural -and sometimes domain-specificnature has not been amenable to analytical studies. As a result, little work is available on the correctness or efficiency of critics . This paper describes a principled approach to handling conflicts, as implemented in UMCP 1 , an HTN planning system. Critics in UMCP have desirable properties such as systematicity, and the preservation of soundness and completeness.

  1. [Allen et al. , 1990] Allen , J .; Hendler, J . and Tate, A. editors. Readings in Planning. Morgan-Kaufmann , San Mateo, CA, 1990.
  2. [Chapman, 1987] Chapman, D. Planning for conjunc- tive goals. Artificial Intelligence, 32:333-378 , 1987.
  3. [Collins and Pryor, 1992] Collins, G. and Pryor, L. Achieving the functionality of filter conditions in a partial order planner In Proc. AAAI-92, 1992, pp. 375-380.
  4. [Dean, 1983] Dean, T . Time map maintenance. Techni- cal Report 289, Yale University, October 1983.
  5. [Drummond, 1985] Drummond, M. Refining and Ex- tending the Procedural Net. In Proc. IJCAI-85, 1985. IJCAI
  6. [Erol et al., 1994a] Erol, K.; Hendler, J. and N au, D. Semantics for Hierarchical Task Network Plan- ning. CS-TR-3239, UMIACS-TR-94-31 , ISR-TR- 95-9 , University of Maryland, March 1994.
  7. [Erol et al. , 1994b] Erol, K.; Hendler, J . and Nau, D. Complexity results for hierarchical task-network planning. To appear in Annals of Mathematics and Artificial Intelligence Also available as Technical re- port CS-TR-3240, UMIACS-TR-94-32 , ISR-TR-95- 10 Computer Science Dept. , University of Mary- land, March 1994.
  8. [Erol, 1995] Erol, K. HTN Planning: Formalization , Analysis, and Implementation. Ph.D . Dissertation, Computer Science Dept ., University of Maryland, 1995. In preparation.
  9. [Fikes and Nilsson, 1971] Fikes, R. E. and Nilsson , N. J . STRIPS : a new approach to the application of the- orem proving to problem solving . Artificial Intelli- gence, 2(3/4):189-208, 1971. IJCAI
  10. [Kambhampati and Hendler , 1992] Kambhampati , S. and Hendler, J. "A Validation Structure Based 1698 PLANNING Theory of Plan Modification and Reuse" Artificial Intelligence , May, 1992.
  11. [Kambhampati, 1992] Kambhampati, S. "On the utility of systematicity: understanding trade-offs between redundancy and commitment in partial-ordering planning," unpublished manuscript, Dec ., 1992.
  12. [Kambhampati et al., 1995] Kambhampati, S.; Knoblock, C. and Yang, Q. Planning as refinement search: A unified framework for evaluating design tradeoffs in partial order planning . To appear in Ar- tificial Intelligence, Special Issue on Planning. [Kanal and Kumar, 1988] Kanal , L. and Kumar, V. Search in Artificial Intelligence, Springer-Verlag, 1988.
  13. [McAllester and Rosenblitt, 1991] McAllester, D. and Rosenblitt, D. Systematic nonlinear planning. In Proc. AAAI-91, 1991.
  14. [Minton et al., 1991] Minton, S.; Bresina, J . and Drum- mond, M. Commitment strategies in planning. In Proc. IJCAI-91, 1991.
  15. [Sacerdoti, 1977] Sacerdoti, E. D. A Structure for Plans and Behavior, Elsevier-North Holland. 1977.
  16. [Sussman , 1990] Sussman , G.J ., HACKER: a compu- tational model of skill acquisition, MIT AI Lab Memo 1973, also in Allen, 1990, Readings in Plan- ning. Morgan Kaufmann.
  17. [Tate et al., 1990] Tate, A.; Hendler, J . and Drummond, D. AI planning: Systems and techniques. AI Magazine , (UMIACS-TR-90-21, CS-TR-2408) :61- 77, Summer 1990
  18. [Tate, 1977] Tate, A. Generating Project Networks In Proc. IJCAI-77, 1977. pp . 888-893 . IJCAI
  19. [Tate et al., 1994] Tate, A.; Drabble, B. and Dalton, J. The Use of Condition Types to Restrict Search in an AI Planner . Proc. AAAI-94. pp . 1129-1134.
  20. [Vere, 1983] Vere, S. A. Planning in Time: Windows and Durations for Activities and Goals . IEEE Transactions on Pattern Analysis and Machine In- telligence, PAMI-5(3) :246-247, 1983.
  21. [Wilkins, 1988] Wilkins, D. Practical Planning: Extend- ing the classical AI planning paradigm, Morgan- Kaufmann , CA. 1988.
  22. [Yang, 1990] Yang, Q. Formalizing planning knowledge for hierarchical planning Computational Intelli- gence Vol.6 ., 12-24, 1990.
  23. [Yang et al., 1993] Yang, Q.; Nau, D.S .; and Hendler, J . Merging separately generated plans with re- stricted interactions. Computational Intelligence, 9(1), February 1993.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards