SHOP2

SHOP2 is a Hierarchical Task Network (HTN) planner. Rather than having a set of goals to achieve (as in classical planning), SHOP2 instead has a partially ordered set of tasks to perform. To solve planning problems in some domain, SHOP2 needs a domain-specific knowledge base of methods, each of which gives a way to decompose a task into a partially ordered set of subtasks (provided that the method's preconditions are satisfied). To create plans, SHOP2 does problem reduction: it decomposes tasks recursively into subtasks until it reaches primitive tasks that can be performed directly by planning operators.

Unlike most HTN planners, SHOP2 always builds plans forward from the initial state: given several tasks to decompose, SHOP2 plans for them in the same order that they will be executed. Thus at each point in its planning process, SHOP2 has already planned every action that will occur beforehand, so SHOP2 knows what the current state will be. This allows SHOP2's precondition-evaluation mechanism to be quite powerful: the preconditions of SHOP2's methods and operators can include logical inferences, complex numeric computations, and calls to external programs.

SHOP2's main advantage over its predecessor, SHOP, is that while SHOP required its tasks to be totally ordered, SHOP2 works with partially ordered sets of tasks. In principle, both SHOP and SHOP2 are Turing-complete - but since SHOP2 can interleave subtasks of different tasks, some planning domains can be represented more easily in SHOP2 than in SHOP. For more information, see http://www.cs.umd.edu/projects/shop.