Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Although task reduction (HTN) planning historically preceded partial order (PO) planning, and is believed to be more general than the latter, very little comparative analysis of the two planning formalisms has been done. Part of the reason for this has been the lack of systematic understanding of the functionalities provided by HTN planning over and above that of partial order planning. In this paper I will describe a generalized algorithm template for partial order planning based on refinement search, and extend it to cover HTN planning. I will use this framework as a basis to (i) discuss the similarities and differences between the HTN and the partial order planning methods, (ii) critically examine the claims regarding the efficiency and expressiveness of HTN planning, and (iii) shed light on several of the less understood features of HTN planning.

REFERENCES

• 1: Anthony Barrett , Daniel S. Weld, Partial-order planning: evaluating possible efficiency gains, Artificial Intelligence, v.67 n.1, p.71-112, May 1994 [doi>10.1016/0004-3702(94)90012-4]
• 2: A. Barrett and D. Weld. Schema Parsing: Hierarchical Planning for Expressive Languages. In <i>Proc. AAAI-94.</i>
• 3: David Chapman, Planning for conjunctive goals, Artificial Intelligence, v.32 n.3, p.333-377, July 1987 [doi>10.1016/0004-3702(87)90092-0]
• 4: M. Drummond. On precondition achievement and the computational economics of automatic planning. In <i>Proc. European Workshop on Planning Systems,</i> 1994.
• 5: G. Collins and L. Pryor. Achieving the functionality of filter conditions in partial order planner. In <i>Proc. 10th AAAI,</i> 1992.
• 6: K. Erol, D. Nau and J. Hendler. Toward a general framework for hierarchical task-network planning. In <i>Proc. of AAAI Spring Symp. on Foundations of Automatic Planning.</i> 1993.
• 7: Kutluhan Erol , James Hendler , Dana S. Nau, HTN planning: complexity and expressivity, Proceedings of the twelfth national conference on Artificial intelligence (vol. 2), p.1123-1128, October 1994, Seattle, Washington, United States
• 8: K. Erol, J. Hendler and D. Nau. UMCP: A sound and complete procedure for Hierarchical Task-network planning. In <i>Proc. AIPS-94.</i>
• 9: Keith Golden , Oren Etzioni , Daniel Weld, Omnipotence without omniscience: efficient sensor management for planning, Proceedings of the twelfth national conference on Artificial intelligence (vol. 2), p.1048-1054, October 1994, Seattle, Washington, United States
• 10: R. Fikes and N. Nilsson. STRIPS: A new approach to the application of theorem proving to problem solving. In <i>Readings in Planning.</i> Morgan Kaufmann, 1990.
• 11: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 12: Subbarao Kambhampati, Multi-contributor causal structures for planning: a formalization and evaluation, Artificial Intelligence, v.69 n.1-2, p.235-278, Sept. 1994 [doi>10.1016/0004-3702(94)90083-3]
• 13: S. Kambhampati. Refinement search as a unifying framework for analyzing planning algorithms. In <i>Proc. 4th Intl. Conf. on Principles of Knowledge Representation and Reasoning (KR-94),</i> May 1994.
• 14: S. Kambhampati. Design Tradeoffs in Partial Order (Plan Space) Planning. In <i>Proc. 2nd Intl. Conf. on AI Planning Systems (AIPS-94),</i> June 1994.
• 15: Subbarao Kambhampati , Craig A. Knoblock , Qiang Yang, Planning as refinement search: a unified framework for evaluating design tradeoffs in partial-order planning, Artificial Intelligence, v.76 n.1-2, p.167-238, July 1995 [doi>10.1016/0004-3702(94)00076-D]
• 16: C. Knoblock and Q. Yang. A Comparison of the SNLP and TWEAK planning algorithms. In Proc. of AAAI Spring Symp. on Foundations of Automatic Planning. March, 1993.
• 17: David E. Wilkins, Practical planning: extending the classical AI planning paradigm, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 18: D. McDermott. Regression Planning. <i>Intl. Jour. Intelligent Systems,</i> 6:357--416, 1991.
• 19: D. McDermott. Planning and Acting. In <i>Readings in Planning,</i> Morgan Kaufmann, San Mateo (1990)
• 20: D. McAllester and D. Rosenblitt. Systematic Nonlinear Planning. In <i>Proc. 9th AAAI,</i> 1991.
• 21: D. McAllester. Private Communication. August 1994.
• 22: S. Minton, M. Drummond, J. Bresina and A. Philips. Total Order vs. Partial Order Planning: Factors Influencing Performance In <i>Proc. KR-92,</i> 1992.
• 23: E.P.D. Pednault. Synthesizing Plans that contain actions with Context-Dependent Effects. <i>Computational Intelligence,</i> Vol. 4, 356--372 (1988).
• 24: J. S. Penberthy and D. Weld. UCPOP: A Sound, Complete, Partial Order Planner for ADL. In <i>Proc. KR-92,</i> 1992.
• 25: J. Scott Penberthy, Planning with continuous change, University of Washington, Seattle, WA, 1993
• 26: E. Sacerdoti. <i>A structure for Plans and Behavior</i> Elsevier, North-Holland, New York (1977).
• 27: A. Tate. Generating Project Networks. In <i>Proceedings of IJCAI-77,</i> pages 888--893, Boston, MA, 1977.
• 28: Ken Currie , Austin Tate, O-Plan: the open planning architecture, Artificial Intelligence, v.52 n.1, p.49-86, Nov. 1991 [doi>10.1016/0004-3702(91)90024-E]
• 29: S. Vere. Planning in Time: Windows and Durations for Activities and Goals. <i>IEEE Trans. on Pattern Analysis and Machine Intell.</i> Vol 5., pp 246--267 (1983).
• 30: D. Wilkins. <i>Practical Planning.</i> Morgan Kaufmann (1988).
• 31: Qiang Yang, Formalizing planning knowledge for hierarchical planning, Computational Intelligence, v.6 n.1, p.12-24, Feb. 1990 [doi>10.1111/j.1467-8640.1990.tb00126.x]
• 32: R. M. Young, M. E. Pollack and J. D. Moore. Decomposition and Causality in Partial-Order Planning. In <i>Proc. 2nd Intl. Conf. on AI Planning Systems,</i> 1994.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Plan execution, formation, and generation

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

General Terms:
Algorithms, Design, Performance, Theory