Show simple item record

SHOP and M-SHOP: Planning with Ordered Task Decomposition

dc.contributor.authorNau, Danaen_US
dc.contributor.authorCao, Yueen_US
dc.contributor.authorLotem, Amnonen_US
dc.contributor.authorMunoz-Avila, Hectoren_US
dc.description.abstractSHOP (Simple Hierarchical Ordered Planner) and M-SHOP (Multi-task-list SHOP) are 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.en_US
dc.format.extent1979078 bytes
dc.relation.ispartofseriesUM Computer Science Department; CS-TR-4157en_US
dc.titleSHOP and M-SHOP: Planning with Ordered Task Decompositionen_US
dc.typeTechnical Reporten_US
dc.relation.isAvailableAtDigital Repository at the University of Marylanden_US
dc.relation.isAvailableAtUniversity of Maryland (College Park, Md.)en_US
dc.relation.isAvailableAtTech Reports in Computer Science and Engineeringen_US
dc.relation.isAvailableAtComputer Science Department Technical Reportsen_US

Files in this item


This item appears in the following Collection(s)

Show simple item record