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 taskinteraction 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