SHOP: Simple Hierarchical Ordered Planner

Abstract

SHOP (Simple Hierarchical Ordered Planner) is a domain-independent HTN\nPlanning system with the following characteristics.\n* SHOP plans for tasks in the same order that they will later be executed.\nThis avoids some of the goal-interaction issues that arise in other HTN\nplanners, thus making the planning algorithm relatively simple.\n* The planning algorithm is sound and complete over a large class of \nproblems.\n* Since SHOP knows the complete world-state at each step of the planning\nprocess, it can use highly expressive domain representations. For example,\nit can do planning problems that require complex numeric computations.\n* In our tests, SHOP solved problems several orders of magnitude faster\nthan Blackbox and TLplan. This occured even though SHOP is written in\nLisp and the other planners are written in C. (Also\ncross-referenced as UMIACS-TR 99-04)