SHOP and M-SHOP: Planning With Ordered Task Decomposition

: SHOP (Simple Hierarchical Ordered Planner) and M-SHOP (Multi-task-list SHOP) are HTN planning algorithms with the following characteristics. SHOP and M-SHOP plan for tasks in the same order that they will later be executed. This avoids some task interaction issues that arise in other HTN planners, making the planning algorithms relatively simple. This also makes it easy to prove soundness and completeness results. Since SHOP and M-SHOP know the complete world-state at each step of the planning process, they can use highly expressive domain representations. For example, they can do planning problems that require Horn-clause inferencing, complex numeric computations, and calls to external programs. In our tests, SHOP and M-SHOP were several orders of magnitude faster than Blackbox, IPP, and UMCP, and were several times as fast as TLplan. The approach is powerful enough to be used in complex real-world planning problems. For example, we are using a Java implementation of SHOP as part of the HICAP plan-authoring system for Noncombatant Evacuation Operations (NEOs). In this paper we describe SHOP and M-SHOP, present soundness and completeness results for them, and compare them experimentally to Blackbox, IPP, TLplan, and UMCP. The results suggest that planners that generate totally ordered plans starting from the initial state can scale up to complex planning problems better than planners that use partially ordered plans.