Home page Description Download Acknowledgments
Automated  Planning University of Maryland		Description of the SHOP Project

In HTN planning, the planning system begins with an initial state-of-the-world and with the objective of creating a plan to perform a set of tasks (abstract representations of things that need to be done). HTN planning is done by problem reduction: the planner recursively decomposes tasks into subtasks, stopping when it reaches primitive tasks that can be performed directly by planning operators. In order to tell the planner how to decompose nonprimitive tasks into subtasks, it needs to have a set of methods, where each method is a schema for decomposing a particular kind of task into a set of subtasks (provided that some set of preconditions is satisfied). For each task, there may be more than one applicable method, and thus more than one way to decompose the task into subtasks. The planner may have to try several of these alternative decompositions before finding one that is solvable at a lower level. Unlike classical planning, HTN planning is Turing-complete.

An ordered task decomposition planner is an HTN planner that plans for tasks in the same order that they will be executed. This reduces the complexity of reasoning by removing a great deal of uncertainty about the world, which makes it easy to incorporate substantial expressive power into the planning algorithm. In addition to the usual HTN methods and operators, our planners can make use of axioms, can do mixed symbolic/numeric conditions, and can do external function calls.

Our first planning systems to use ordered task decomposition were domain-specific, i.e., they were tailor-made for specific application domains. These included EDAPS, a system for integrated product design and manufacturing planning, and Bridge Baron, a bridge-playing computer program that won the 1997 world championship of computer bridge and is a successful commercial product.

Our first domain-independent implementation of ordered task decomposition was SHOP (Simple Hierarchical Ordered Planner). SHOP and its successors (the most recent ones are SHOP2 and JSHOP2) can be configured to work in many different planning domains.

In the 2002 International Planning Competition, SHOP2 solved problems in every planning domain in the competition, for a total of nearly 1000 planning problems. SHOP2 received one of the top four prizes in the competition.

Our most recent planner is JSHOP2, a Java implementation of SHOP2 (which is written in Lisp). In addition to being in Java, JSHOP2 uses a new planner compilation technique to synthesize domain-dependent planners from SHOP2 domain descriptions. This way, JSHOP2 can do a variety of optimizations to speed up execution.

For more information, see the download page and the publications listed below. If you still have questions after that, send email to the following address:

Publications

1. D.S. Nau, S.J.J. Smith, and K. Erol. "Control Strategies in HTN Planning: Theory versus Practice." In AAAI-98/IAAI-98 Proceedings, pp. 1127-1133, 1998. Overviews of Ordered Task Decomposition, EDAPS, and Bridge Baron.

2. D. Nau, Y. Cao, A. Lotem, and H. Muñoz-Avila. "SHOP: Simple Hierarchical Ordered Planner." In IJCAI-99, pp. 968-973, 1999. Describes SHOP.

3. D.S. Nau. "Ordered Task Decomposition: Theory and Applications," Part 1 and Part 2. PLANET International Summer School on AI Planning, October 2000. Viewgraphs describing Ordered Task Decomposition.

4. D.S. Nau, Y. Cao, A. Lotem, and H. Muñoz-Avila. "SHOP and M-SHOP: Planning with Ordered Task Decomposition." Tech. Report CS TR 4157, University of Maryland, College Park, MD, June, 2000. Gives details about SHOP and M-SHOP.

5. H. Muñoz-Avila, D.W. Aha, D.S. Nau, R. Weber, L. Breslow, and F. Yaman. "SiN: Integrating Case-based Reasoning with Task Decomposition." In IJCAI-2001. Seattle, August, 2001. Describes how JSHOP is used in HICAP.

6. D. Nau, H. Muñoz-Avila, Y. Cao, A. Lotem, and S. Mitchell. "Total-Order Planning with Partially Ordered Subtasks." In IJCAI-2001. Seattle, August, 2001. Our first paper on SHOP2.

7. O. Ilghami, D. S. Nau, H. Muñoz-Avila, and D. W. Aha. CaMeL: Learning methods for HTN planning. AIPS-02, 2002. Describes a way to automatically learn some of the information needed in HTNs.

8. J. Dix, H. Munoz-Avila, D. Nau, and L. Zhang. "IMPACTing SHOP: Putting an AI Planner into a Multi-Agent Environment." Annals of Mathematics and AI 37:4, pp. 381-407, 2003. Describes A-SHOP, an agentized version of JSHOP.

9. D. Nau, T.-C. Au, O. Ilghami, U. Kuter, W. Murdock, D. Wu, and F.Yaman."SHOP2: An HTN Planning System." JAIR, volume 20, pp. 379-404, 2003. Describes features of SHOP2 that helped it excel in the 2002 International Planning Competition.

10. D. Wu, B. Parsia, E. Sirin, J. Hendler, and D. Nau. Automating DAML-S web services composition using SHOP2. ISWC2003 , 2003. Describes the use of SHOP2 to execute DAML-S web-service descriptions.

11. O. Ilghami and D. S. Nau. A general approach to synthesize problem-specific planners. Tech. Rep. CS-TR-4597, UMIACS-TR-2004-40, University of Maryland, October 2003. Describes the planner-compilation technique used in JSHOP2.

12. U. Kuter and D. Nau. Forward-chaining planning in nondeterministic domains. AAAI-04 Proceedings, 2004. Describes how to adapt SHOP2 and several other planners to work in nondeterministic planning domains.

13. D. Nau, T.-C. Au, O. Ilghami, U. Kuter, H. Muñoz-Avila, J. W. Murdock, D. Wu, and F. Yaman. Applications of SHOP and SHOP2. IEEE Intelligent Systems, 2005 (to appear). An earlier version is available as Tech. Rep. CS-TR-4604, UMIACS-TR-2004-46. Describes some of the applications that people have used SHOP and SHOP2 for.

14. U. Kuter, D. Nau, M. Pistore, and P. Traverso. A hierarchical task-network planner based on symbolic model checking. ICAPS-05, pp. 300-309. Further work on adapting SHOP2 to work in nondeterministic problem domains.

15. U. Kuter and D. Nau. Using domain-configurable search control for probabilistic planning. AAAI-05, July 2005. Describes how to adapt SHOP2 and several other planners to work in probabilistic planning domains such as MDPs.

16. D. Nau. May all your plans succeed! AAAI-05, July 2005. An invited talk giving an overview of automated planning.

17. O. Ilghami, H. Muñoz-Avila, D. S. Nau, and D. W. Aha. Learning approximate preconditions for methods in hierarchical plans. ICML-05, Aug. 2005. An extension of the work described in [7] above.

18. O. Ilghami, D. S. Nau, H. Muñoz-Avila, and D. W. Aha. Learning preconditions for planning from plan traces and HTN structure. Computational Intelligence 21(4):388–413, Nov. 2005. Gives the details of the work described in [7] and [17].

19. U. Kuter, E. Sirin, D. Nau, B. Parsia, and J. Hendler. Information gathering during planning for web service composition. Journal of Web Semantics 3(2-3):183–205, 2005. Extension of SHOP2 to gather information from the web in order to do web-service composition.

20. T.-C. Au, U. Kuter, and D. Nau. Web service composition with volatile information. ISWC-05, 2005. An extension of SHOP2 to do web service composition in environments when the world is changing while the planning is going on.